Quick Sort in C Code with Algorithm using Recursion and Code Reducing Techniques :
Example for Quick Sort Program in C using Recursion with Algorithm is given below :-
Quicksort is a divide and conquer algorithm. Quicksort first divides a large list into two smaller sub-lists: the low elements and the high elements. Quicksort can then recursively sort the sub-lists. Pick an element, called a pivot, from the list. Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation. Recursively sort the sub-list of lesser elements and the sub-list of greater elements. The base case of the recursion are lists of size zero or one, which never need to be sorted.
#include<stdio.h>
#include<conio.h>
void quick_Sort( int [], int, int ); /* function prototype declaration */
void main()
{
int a[ 100 ], n, i;
clrscr();
printf( "Enter the Number array elements to be sorted :" );
scanf( "%d", &n );
printf( "Enter array elements :\n" );
for ( i = 0; i < n ; scanf( "%d", &a[ i ] ), i++ ); /* use ; to end FOR LOOP, as one statement contains inside the LOOP */
quick_Sort( a, 0, n – 1 ); /* UDF calls here */
printf( "The Sorted Array is given below\n" );
for ( i = 0 ; i < n ; printf( "%d\t", a[ i ] ), i++ ); /* did as above, printf() can also be put out side FOR LOOP as usual */
getch();
}
void quick_Sort( int a[], int low, int high ) /* UDF defines here */
{
int l, h, key, temp, t;
key = a[ low ];
l = low;
h = high;
while ( low < high )
{
if ( a[ low ] < key )
{
low = low + 1;
}
else
{
if ( a[ high ] > key )
{
high = high – 1;
}
else
{
temp = a[ low ];
a[ low ] = a[ high ];
a[ high ] = temp;
}
}
}
t = key;
key = a[ high ];
a[ high ] = t;
if ( l < high )
{
quick_Sort( a, 0, high – 1 );
}
if ( low < h )
{
quick_Sort( a, high + 1, n – 1 );
}
}