#include<stdio.h>
int partition(int a[], int left, int right, int n)
{
int piv, i, j, temp;
piv = left;
i = piv + 1;
j = right;
while(i<=j)
{
while(a[piv] < a[j] && piv < j)
{
j--;
}
if(a[piv] > a[j] && piv < j)
{
temp = a[piv];
a[piv] = a[j];
a[j] = temp;
piv = j;
j--;
}
while(a[i] < a[piv] && i < piv)
{
i++;
}
if(a[i] > a[piv] && i < piv)
{
temp = a[piv];
a[piv] = a[i];
a[i] = temp;
piv = i;
i++;
}
}
return piv;
}
void QuickSort(int a[], int left, int right, int n)
{
if(left < right)
{
int ind = partition(a, left, right, n);
/*printf("ind = %d\n", ind);
for(int i=0;i<n;i++)
printf("%d ", a[i]);
printf("\n");*/
QuickSort(a, left, ind-1, n);
QuickSort(a, ind+1, right, n);
}
}
int main()
{
int i, n, numbers[100];
scanf("%d", &n);
for(i=0;i<n;i++)
scanf("%d", &numbers[i]);
QuickSort(numbers, 0, n-1, n);
printf("Sorted Output:\n");
for(i=0;i<n;i++)
printf("%d ", numbers[i]);
printf("\n");
return 0;
}
/*
Sample Input:
10 /*Number of integers*/
12 33 44 55 555 66 77 88 99 100
Sample Output:
Sorted Output:
12 33 44 55 66 77 88 99 100 555
*/
Attention: Quicksort time complexity has been discussed in this topic.
Tags:
C