ページ 11

クイックソートのアルゴリズム

Posted: 2014年3月24日(月) 15:25
by c言語のアルゴリズムを勉強中
クイックソートで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: クイックソートのアルゴリズム

Posted: 2014年3月24日(月) 16:00
by 初級者
私だったら、どういう動きをするのか、
とりあえず実験してみます。

Re: クイックソートのアルゴリズム

Posted: 2014年3月24日(月) 20:52
by かずま
c言語のアルゴリズムを勉強中 さんが書きました: a( a1( 10 ) a2( 10 ) )b(b1( 10 )b2( 10 ))
a1,a2,b1,b2にも10が含まれたことにします。
10 が 4個以上あればね。

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に設定することができなくなります。
c言語のアルゴリズムを勉強中 さんが書きました: ≦や≧じゃだめなのですか?
だめじゃありませんが、交換対象にならない 10 はそこに残るので、
やはり、a は 10以下、b は 10以上になります。

Re: クイックソートのアルゴリズム

Posted: 2014年3月25日(火) 12:38
by かずま
c言語のアルゴリズムを勉強中 さんが書きました: ≦や≧じゃだめなのですか?
実際のコードを示してもらえないと何とも言えませんが、元のコードが
while (a < pivot) i++;
の場合、このループは必ず終了しますが、
while (a <= pivot) i++;
だと、i が右端を超えないようにコードの追加が必要になると思います。

Re: クイックソートのアルゴリズム

Posted: 2014年3月26日(水) 00:21
by Dixq (管理人)
クイックソートの動きを学べるソフトを作ったことがあるので紹介します。
http://dixq.net/sort.html

Re: クイックソートのアルゴリズム

Posted: 2014年3月26日(水) 08:31
by もち
まず分からないのが何故始めにpivot=10とした時に二回目の走査もpivot=10で行おうとしているのですか?そういうことだよね?僕が何か勘違いしてたらすいません