クイックソートにおけるデータ列のソートの仕方について
はじめまして。
アルゴリズム初心者でクイックソートでつまづいております。
{5,3,2,6,4,1,3,7}というデータ列で、真ん中の4を基準値(ピボット)とした場合(6と4の間にパーテーションを設けた場合、)どのように(昇順)ソートされていくか順を追ってご説明頂けますと幸いです。
※自分で試した場合、なぜか昇順でソートすることができませんでした。(1が最左端に来ず、並び順が{3,3,2,1,:4,6,5,7}となりました。)
どうぞよろしくお願いいたします。
疑似コードは以下の通りです。
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
ソートの記述例は以下のとおりです。
前提: ← []を一つ目の要素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となったのでループ終了。