質問
一般的なランダムクイックソートから以下のrandomQuickSort1(target, left, right)
とrandomQuickSort2(target, left, right)
を作りました。
randomQuickSort1(target, left, right)
では数秒で終わるものの、randomQuickSort2(target, left, right)
では時間がかかる配列を探しています。
用意されたクイックソート
partition(target, left, right)
は pivot
より大きい数字を左側に、小さい数字を右側に寄せて分割する関数です。
randomQuickSort1(target, left, right)
は分割部分の左右のうち短い方からソートしていく関数ですが、randomQuickSort2(target, left, right)
は分割部分の左側からソートしていく関数です。
C
1int partition(int* target, int left, int right) { 2 // ******************変更点****************** 3 int random = right - 1; 4 // ******************変更点****************** 5 // Exchange target[right] and target[random]. 6 int tmp = target[right]; target[right] = target[random]; target[random] = tmp; 7 int pivot = target[right]; 8 int i = left-1; // i scans the array from the left. 9 int j = right; // j scans the array from the right. 10 for (;;) { 11 // Move from the left until hitting a value no less than the pivot. 12 for(i++; target[i] < pivot; i++){} 13 // Move from the right until hitting a value no greater than the pivot. 14 for(j--; pivot < target[j] && i < j; j--){} 15 if (i >= j) break; 16 // Exchange target[i] and target[j]. 17 tmp = target[i]; target[i] = target[j]; target[j] = tmp; 18 } 19 // Exchange target[i] and target[right]. 20 tmp = target[i]; target[i] = target[right]; target[right] = tmp; 21 return i; 22} 23 24void randomQuickSort1(int* target, int aLeft, int aRight) { 25 int left = aLeft; int right = aRight; 26 while (left < right) { 27 int i = partition(target, left, right); 28 if( i - left <= right - i ){ // The left interval is shorter. 29 randomQuickSort1(target, left, i-1); 30 left=i+1; 31 }else{ // The right interval is shorter. 32 randomQuickSort1(target, i+1, right); 33 right=i-1; 34 } 35 } 36} 37 38void randomQuickSort2(int* target, int aLeft, int right) { 39 int left = aLeft; 40 while (left < right) { 41 int i = partition(target, left, right); 42 randomQuickSort2(target, left, i-1); 43 left = i+1; 44 } 45}
一般的なランダムクイックソート
C
1// 変更前のpartition関数 2int partition(int* target, int left, int right) { 3 // Select a number between left and right at random. 4 int random = left + rand() % (right - left + 1); 5 // Exchange target[right] and target[random]. 6 int tmp = target[right]; target[right] = target[random]; target[random] = tmp; 7 int pivot = target[right]; 8 int i = left-1; // i scans the array from the left. 9 int j = right; // j scans the array from the right. 10 for (;;) { 11 // Move from the left until hitting a value no less than the pivot. 12 for(i++; target[i] < pivot; i++){} 13 // Move from the right until hitting a value no greater than the pivot. 14 for(j--; pivot < target[j] && i < j; j--){} 15 if (i >= j) break; 16 // Exchange target[i] and target[j]. 17 tmp = target[i]; target[i] = target[j]; target[j] = tmp; 18 } 19 // Exchange target[i] and target[right]. 20 tmp = target[i]; target[i] = target[right]; target[right] = tmp; 21 return i; 22} 23 24void randomQuickSort(int* target, int left, int right ) { 25 if (left < right) { 26 int i = partition(target, left, right); // i: Position of the pivot. 27 randomQuickSort1(target, left, i - 1); 28 randomQuickSort1(target, i + 1, right); 29 } 30}
試したこと
昇順にソート済み配列、降順にソート済み配列を試しましたが、両者の関数に実行時間の差はありませんでした。
回答1件
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。