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

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
c言語のアルゴリズムを勉強中

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

#1

投稿記事 by c言語のアルゴリズムを勉強中 » 6年前

クイックソートで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が一緒にならないと思うのですが、どうなんでしょう?
≦や≧じゃだめなのですか?

初級者
記事: 200
登録日時: 9年前

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

#2

投稿記事 by 初級者 » 6年前

私だったら、どういう動きをするのか、
とりあえず実験してみます。

かずま

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

#3

投稿記事 by かずま » 6年前

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: クイックソートのアルゴリズム

#4

投稿記事 by かずま » 6年前

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

アバター
Dixq (管理人)
管理人
記事: 1661
登録日時: 9年前
住所: 北海道札幌市
連絡を取る:

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

#5

投稿記事 by Dixq (管理人) » 6年前

クイックソートの動きを学べるソフトを作ったことがあるので紹介します。
http://dixq.net/sort.html

もち

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

#6

投稿記事 by もち » 6年前

まず分からないのが何故始めにpivot=10とした時に二回目の走査もpivot=10で行おうとしているのですか?そういうことだよね?僕が何か勘違いしてたらすいません

閉鎖

“C言語何でも質問掲示板” へ戻る