0
こんにちはすべて私はC++に新しく、検索とソートのアルゴリズムに没頭していて、自分で作成しようと決めました。クイックソートの実装
int main()
{
// Announce the program
cout << "\nImplementing the QuickSort Algorithm\n";
// Declare useful values
const char BLANK = ' ';
size_t i = 0;
// Initialize our test data arrays
const size_t SIZE1 = 10;
int data1[]= {34, 33, 9, 45, 1, -1, 9, -18, 75, 100 };
const size_t SIZE2 = 15; // Number of elements in the array to be sorted
int data2[]= {100, 99, 98, 97, 96, 95, 94, 93, 92, 91, 90, 89, 88, 87, 86 };
const size_t SIZE3 = 1000;
int data3[SIZE3];
// Initialize the third array to random int values
for (i = 0; i < SIZE3; i++)
data3[i] = rand();
// Beginning of quick sort tests
// Sort the arrays and print the result with two blanks after each number
quicksort(data1, SIZE1);
cout << "\nSorted First Array: " << endl;
for (i = 0; i < SIZE1; i++)
cout << data1[i] << BLANK << BLANK;
cout << endl;
quicksort(data2, SIZE2);
cout << "\nSorted Second Array: " << endl;
for (i = 0; i < SIZE2; i++)
cout << data2[i] << BLANK << BLANK;
cout << endl;
// On the large third array, just print the first ten and last ten values
quicksort(data3, SIZE3);
cout << "\nSorted Third Array (first ten): " << endl;
for (i = 0; i < 10; i++)
cout << data3[i] << BLANK << BLANK;
cout << endl;
cout << "Sorted Third Array (last ten): " << endl;
for (i = SIZE3 - 10; i < SIZE3; i++)
cout << data3[i] << BLANK << BLANK;
cout << endl << endl;
system("Pause");
return EXIT_SUCCESS;
}
と私は、関数の定義開始している：私は私のmainテストが書かれている
void quicksort(int data[ ], size_t n);
// Precondition: data is an array with at least n components.
// Postcondition: The elements of data have been rearranged so
// that data[0] <= data[1] <= ... <= data[n-1].
void partition(int data[ ], size_t n, size_t& pivot_index);
// Precondition: n > 1, and data is an array (or subarray)
// with at least n elements.
// Postcondition: The function has selected some "pivot value"
// that occurs in data[0]..data[n-1]. The elements of data
// have then been rearranged, and the pivot index set so that:
// -- data[pivot_index] is equal to the pivot;
// -- Each item before data[pivot_index] is <= the pivot;
// -- Each item after data[pivot_index] is > the pivot.
void setPivot(int data[ ], size_t n);
// Precondition: n > 1 and data is an array or subarray
// Postcondition: data[0] holds the selected pivot value
// The original value of data[0] has been swapped with the selected pivot value
：ここに私のプロトタイプはある
void quicksort(int data[ ], size_t n)
// Library facilities used: cstdlib
{
size_t pivot_index; // Array index for the pivot element
size_t n1; // Number of elements before the pivot element
size_t n2; // Number of elements after the pivot element
if (n > 1)
{
// Partition the array, and set the pivot index.
partition(data, n, pivot_index);
// Compute the sizes of the subarrays.
n1 = pivot_index;
n2 = n - n1 - 1;
// Recursive calls will now sort the subarrays.
quicksort(data, n1);
quicksort((data + pivot_index + 1), n2);
}
}
void partition(int data[ ], size_t n, size_t& pivot_index)
// Library facilities used: algorithm, cstdlib
{
assert(n > 1);
setPivot(data, n);
}
void setPivot(int data[ ], size_t n)
// Library facilties used: algorithm, cstdlib
// This function chooses a pivot value as the median of three
// randomly selected values. The selected pivot is swapped with
// data[0] so that the pivot value is in the first position of the array
{
assert(n > 1);
}
私の質問は、最良の方法だろう何をスピードに関してvoid partition(int data[], size_t n, size_t& pivot_indexとvoid setPivot(int data[], size_t n)を終了しますか？
'std :: partition'を試してください。 –