//Quick Sort
#include <iostream.h>
const int INPUT_SIZE = 10;
void print(int *input)
{
for ( int i = 0; i < INPUT_SIZE; i++ )
cout << input[i] << " ";
cout << endl;
}
int partition(int* input, int p, int r)
{
int pivot = input[r];
while ( p < r )
{
while ( input[p] < pivot )
p++;
while ( input[r] > pivot )
r--;
if ( input[p] == input[r] )
p++;
else if ( p < r )
{
int tmp = input[p];
input[p] = input[r];
input[r] = tmp;
}
}
return r;
}
void quicksort(int* input, int p, int r)
{
if ( p < r )
{
int j = partition(input, p, r);
quicksort(input, p, j-1);
quicksort(input, j+1, r);
}
}
int main()
{
int input[INPUT_SIZE] = {5, 7, 8, 1, 3, 2, 9, 4, 10, 6};
cout << "Input: ";
print(input);
quicksort(input, 0, 9);
cout << "Output: ";
print(input);
return 0;
}
|
Output:
No comments:
Post a Comment