正しいソート・アルゴリズムが重複値をソートされていない順序で表示される順序でソートする必要があることをどこかで読んでいます(私はどこに覚えていないのか謝罪)。
例:
5(A)、2、4、5(B)、6、5(C)、1、3
5(A / B / C):ここで、A、B、及びCは、単に5インチの順序を示すために使用される。
5(A):5つのうち3つのうちの最初の5 "
5(B):3つの5のうち2番目の5 "
5(C):5つのうち3つの5つ
ソート後、上記のリストは以下のようになります。
1、2、3、4、5(A)、5(B)、5(C)、6
しかしQuicksortは以下のソートされたシーケンスを与えます:
1、2、3、4、5(C)、5(A)、5(B)、6
コード:
void sort(int[] array, int startIndex, int endIndex){
int right = endIndex;
int pivot = array[(startIndex+endIndex)/2];
int left = startIndex;
int temp;
while(left <= right){
while(array[right] > pivot){
right--;
}
while(array[left] < pivot){
left++;
}
if(left <= right){
temp = array[right];
array[right] = array[left];
array[left] = temp;
left++;
right--;
}
}
if(startIndex < right) {
sort(array, startIndex, right);
}
if(endIndex > left) {
sort(array, left, endIndex);
}
}
この動作は正しいですか?そうでなければ、重複要素の順序がソートされていないシーケンスと同じである正しい出力を得るために何ができるでしょうか。
編集:
重複要素の相対的な順序を維持するアルゴリズムが呼び出されます 「安定ソート」 コメントでDukelingによって知らされるように。
回答:
回答№1は1クイックソートは安定したアルゴリズムではありません。ソート順を保持したい場合は、安定したアルゴリズムを使用してください。 Mergesortは安定したソートアルゴリズムです。