クイックソートのアルゴリズム
Posted: 2014年3月24日(月) 15:25
クイックソートで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が一緒にならないと思うのですが、どうなんでしょう?
≦や≧じゃだめなのですか?
例を上げます。
整数が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が一緒にならないと思うのですが、どうなんでしょう?
≦や≧じゃだめなのですか?