1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55
|
// quick sort // descending
#include <iostream>
using namespace std;
int partition(int ar[], int top, int bottom) // simpler version of above link
{
int i = top;
int j = bottom;
while (i < j)
{
while (ar[top] > ar[j])
j--;
while (ar[top] < ar[i])
i++;
if (i < j)
std::swap(ar[i],ar[j]); // swap
}
return j; // returns pivot subscript
}
void QuickSort(int arr[], int top, int bottom)
{
// top = subscript of beginning of array
// bottom = subscript of end of array
if (top < bottom)
{
int middle = partition(arr, top, bottom); // middle = pivot
QuickSort(arr, top, middle); // sort first section
QuickSort(arr, middle+1, bottom); // sort second section
}
return;
}
int main()
{
int ar[] = {2,9,1,3,5,7,8,6,4,0};
int SIZE = 10;
cout << "Input: ";
for ( int i = 0; i < SIZE; i++ )
cout << ar[i] << " ";
cout << "\n\n";
QuickSort(ar, 0, SIZE-1);
cout << "Output: ";
for ( int i = 0; i < SIZE; i++ )
cout << ar[i] << " ";
cout << "\n\n";
return 0;
}
|