//WAP to implement Quick Sort.
#include<stdio.h>#include<conio.h>
void swap (int a[], int left, int right) // function for swapping
{
int temp;
temp=a[left];
a[left]=a[right];
a[right]=temp;
}
// Sorting logic
void quicksort( int a[], int low, int high ) // function for performing quick sort
{
int pivot;
if ( high > low )// Termination condition!
{
pivot = partition( a, low, high );
quicksort( a, low, pivot-1 );
quicksort( a, pivot+1, high );
}
int pivot;
if ( high > low )// Termination condition!
{
pivot = partition( a, low, high );
quicksort( a, low, pivot-1 );
quicksort( a, pivot+1, high );
}
} //end Quick sort
int partition( int a[], int low, int high ) // Partition function
{
int left, right, pivot_item, pivot = left = low;
pivot_item = a[low];
right = high;
while ( left < right )
{
while( a[left] <= pivot_item ) // Move left while item < pivot
{
while( a[left] <= pivot_item ) // Move left while item < pivot
left++;
while( a[right] > pivot_item ) // Move right while item > pivot
while( a[right] > pivot_item ) // Move right while item > pivot
right--;
if ( left < right )
swap(a,left,right);
}
if ( left < right )
swap(a,left,right);
}
a[low] = a[right]; // right is final position for the pivot
a[right] = pivot_item;
return right;
a[right] = pivot_item;
return right;
}//end partition
void printarray(int a[], int); // void quicksort(int a[], int, int);
void printarray(int a[], int); // void quicksort(int a[], int, int);
int main()
{
int a[50], i, n;
printf("\nEnter no. of elements: ");
scanf("%d", &n); //inputting array size
printf("\nEnter the elements: \n");
for (i=0; i<n; i++)
scanf ("%d", &a[i]); // inputting array elements
quicksort(a,0,n-1);
printf("\nSorted elements: \n");
printarray(a,n); // printing sorted array
getch(); // for holding the console screen
{
int a[50], i, n;
printf("\nEnter no. of elements: ");
scanf("%d", &n); //inputting array size
printf("\nEnter the elements: \n");
for (i=0; i<n; i++)
scanf ("%d", &a[i]); // inputting array elements
quicksort(a,0,n-1);
printf("\nSorted elements: \n");
printarray(a,n); // printing sorted array
getch(); // for holding the console screen
} // end main
void printarray(int a[], int n) // function for printing array
{
int i;
for (i=0; i<n; i++)
printf(" %d ", a[i]);
printf("\n");
} // end printarray
void printarray(int a[], int n) // function for printing array
{
int i;
for (i=0; i<n; i++)
printf(" %d ", a[i]);
printf("\n");
} // end printarray