【アルゴリズム(JS実装)】Quick Sort - 医学生わくばの欲張り技術ブログ

　どうも、わくばです！

　E資格の申し込みを完了しました。2万は高いなあww

　もともとなんでE資格を受けようと思ったかというと、プログラミングの勉強を始めたとき背水の陣を敷くのが目的だったんですよね。挫折者多いですし。個人的に挫折する自信があったので笑

　当時、医学と親和性高いものってことで人工知能やデータサイエンスの領域に的を絞っていたので、E資格がもってこいだったんです。

　なんて消極的な受験動機なんだ(笑)

　勉強過程でアプリ開発の方に興味がそれまして、いまやE資格は「早く終わらせたいタスク」みたいな位置づけになってしまいました。10万近く使ったので、貧乏大学生としてはなんとしても意味あるものとして終えたいわけです(笑)

　無駄話はさておき今日のアルゴリズムはQuick Sortです。基本的にめっちゃ早いらしいです。

この動画がクイックソートの優秀さ見るのに非常に良いです:

www.youtube.com

とりあえずコードはこんな感じになりました。

const quickSort = array => {
    
    //一つの区画内でピボットを中心に大小を振り分ける関数
    const partition = (array, left, right ) => {
        //今回はピボットを中央地で定める。基準は何でも良い。
        const pivot = array[Math.floor((right + left) / 2)]; 
        let i = left; 
        let j = right; 

        while (i <= j) {
            //左からスタートしてピボットより大きい値を探す
            while (array[i]< pivot) { 
                i++;
            }
            //右からスタートしてピボットより小さい値を探す
            while (array[j]> pivot) { 
                j--;
            }
            //iとjがすれ違っていなければスワップ。
            if (i <= j) { 
                [array[i],array[j]] = [array[j],array[i]]; 
                i++;
                j--;
            }
        }
        /**
        ここで返しているのは次の分割をどこで区切るかという話。
        i,jは交換不要になった地点で止まるので
        iだろうがjだろうがpivotとの大小関係は正しい
        故に返すのはぶっちゃけjでも可。
        **/
        return i; 
    } 

    //partition関数を再帰的に繰り返す関数
    const quick = (array, left, right ) => {
        let index; 
        if (array.length > 1) {
            //次の分割の基点 
            index = partition(array, left, right); 
            if (left < index - 1) { 
                //左分割で再帰処理
                quick(array, left, index - 1 );
            }
            if (index < right) { 
                //右分割でも再帰処理
                quick(array, index, right ); 
            }
        }
        return array; 
    }; 
    
  return quick(array, 0, array.length - 1 );
};

let array = [5,4,3,6,7,8,22,7,8,99,0,7,8,0,2,7,266,8,90,5,344,2,34,5,6778,7]

console.log(quickSort(array))

>>>[
     0,  0,   2,   2,    3,  4,  5,
     5,  5,   6,   7,    7,  7,  7,
     7,  8,   8,   8,    8, 22, 34,
     90, 99, 266, 344, 6778
    ]