クイックソートでpivotと要素を比較するとき、<,や>を使うのは何故ですか?この場合、pivotと同じ要素を比較したら偽になって交換対象になって整列できなくないですか?
例を上げます。
整数がL個ある整列されてない配列があるとします。この配列を初めにpivot 10を区切りに左配列と右配列にわけます。
このとき、aの長さa配列、bの長さb配列に分配できたとして、pivotと同じ10がそれぞれに含まれました。
a( 10 ) b( 10 )
同じようにa,bをそれぞれpivot10を区切りにします。
a( a1( 10 ) a2( 10 ) )b(b1( 10 )b2( 10 ))
a1,a2,b1,b2にも10が含まれたことにします。
これらはpivotを10に設定する限り起こりえることで、こうなるとa1の10とb2の間にa2,b1があるため
10が一緒にならないと思うのですが、どうなんでしょう?
≦や≧じゃだめなのですか?
クイックソートのアルゴリズム
Re: クイックソートのアルゴリズム
10 が 4個以上あればね。c言語のアルゴリズムを勉強中 さんが書きました: a( a1( 10 ) a2( 10 ) )b(b1( 10 )b2( 10 ))
a1,a2,b1,b2にも10が含まれたことにします。
a は 10以下、b は 10以上。
a を pivot = 10 で分割すると、a1 は 10以下 a2 は 10だけ。
b を pivot = 10 で分割すると、b1 は 10だけ b2 は 10以上。
a1 <= 10 = a2 = b1 <= b2
ソートできています。
そのうち、10がなくなって、pivot を 10に設定することができなくなります。
だめじゃありませんが、交換対象にならない 10 はそこに残るので、c言語のアルゴリズムを勉強中 さんが書きました: ≦や≧じゃだめなのですか?
やはり、a は 10以下、b は 10以上になります。
Re: クイックソートのアルゴリズム
実際のコードを示してもらえないと何とも言えませんが、元のコードがc言語のアルゴリズムを勉強中 さんが書きました: ≦や≧じゃだめなのですか?
while (a < pivot) i++;
の場合、このループは必ず終了しますが、
while (a <= pivot) i++;
だと、i が右端を超えないようにコードの追加が必要になると思います。
- Dixq (管理人)
- 管理人
- 記事: 1661
- 登録日時: 13年前
- 住所: 北海道札幌市
- 連絡を取る:
Re: クイックソートのアルゴリズム
クイックソートの動きを学べるソフトを作ったことがあるので紹介します。
http://dixq.net/sort.html
http://dixq.net/sort.html
Re: クイックソートのアルゴリズム
まず分からないのが何故始めにpivot=10とした時に二回目の走査もpivot=10で行おうとしているのですか?そういうことだよね?僕が何か勘違いしてたらすいません