

はじめまして。  
アルゴリズム初心者でクイックソートでつまづいております。

{5,3,2,6,4,1,3,7}というデータ列で、真ん中の4を基準値（ピボット）とした場合（6と4の間にパーテーションを設けた場合、）どのように(昇順)ソートされていくか順を追ってご説明頂けますと幸いです。  
※自分で試した場合、なぜか昇順でソートすることができませんでした。（１が最左端に来ず、並び順が{3,3,2,1,:4,6,5,7}となりました。）

どうぞよろしくお願いいたします。

疑似コードは以下の通りです。

[code]

    QUICKSORT(,,)
    1 if <
    2      then  ← PARTITION(, ,)
    3               QUICKSORT(,,)
    4               QUICKSORT(, +1,)
    
    PARTITION(,,)
    1  ← []
    2  ←  -1
    3  ← +1
    4 while TRUE
    5          do repeat  ← -1
    6                until [] ≤ 
    7                repeat  ← +1
    8                until [] ≥ 
    9                if < 
    10                   then 値を交換する [] ← []
    11                   else return 
    
[/code]

ソートの記述例は以下のとおりです。  
前提： ← []を一つ目の要素5とした。

step1 (i)5,3,2,6,:4,1,3,7(j) #:はパーテーションを意味する。

step2 **5(i)** ,3,2,6,:4,1, **3(j)** ,7 # iがjより小さいのでj--

step3 **3(i)** ,3,2,6,:4,1, **5(j)** ,7 # i>jなのでiとjをswap

step4 3,3,2, **6(i)** ,:4,1, **5(j)** ,7 # a[i]≥5となるまでi++

step5 3,3,2, **6(i)** ,:4, **1(j)** ,5,7 # iがjより小さいのでj--

step6 3,3,2, **1(i)** ,:4, **6(j)** ,5,7 # i>jなのでiとjをswap

step7 3,3,2, **1(i)** ,: **4(j)** ,6,5,7 # iがjより小さいのでj--

step8 3,3,2,1,: **4(j)** , **6(i)** ,5,7 # a[i]≥5となるまでi++

j>iとなったのでループ終了。


CC BY-SA 4.0
2018-09-04T21:41:53.560
48087
2018-09-05T14:01:14.860
2018-09-05T14:01:14.860
26303
26303
question
アルゴリズム
クイックソートにおけるデータ列のソートの仕方について