Quicksort is a well-known sorting algorithm developed by C. A. R. Hoare that, on average, makes O(nlogn) (big O notation) comparisons to sort n items. However, in the worst case, it makes O(n2) comparisons.
Typically, quicksort is significantly faster in practice than other O(nlogn) algorithms, because its inner loop can be efficiently implemented on most architectures, and in most real-world data, it is possible to make design choices which minimize the probability of requiring quadratic time.
Program:
#include < iostream.h >
#include < stdio.h >
#include < conio.h >
void print(int a[]) {
for (int i = 0; i < 10; i++) {
cout << a[i] << “-”;
}
cout << endl;
}
int partition(int a[], int p, int r) {
int x = a[r];
int j = p – 1;
for (int i = p; i < r; i++) {
if (x <= a[i]) {
j = j + 1;
int temp = a[j];
a[j] = a[i];
a[i] = temp;
}
}
a[r] = a[j + 1];
a[j + 1] = x;
return (j + 1);
}
void quickSort(int a[], int p, int r) {
if (p < r) {
int q = partition(a, p, r);
quickSort(a, p, q – 1);
quickSort(a, q + 1, r);
}
}
void main() {
int a[] = {
1, 9, 0, 5, 6, 7, 8, 2, 4, 3};
quickSort(a, 0, 9);
print(a);
getch();
}
if you find any bug in the above program. let us know about it. Please post your complaint at pctech@gadgetcage.com.
