Recursive Quicksort Algorithm written in C language [with example step-by-step]

Quicksort is a sorting algorithm developed by C. A. R. Hoare that, on average, makes O(nlogn) (big O notation) comparisons to sort n items. In the worst case, it makes O(n2) comparisons, though if implemented correctly this behavior is rare. 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 that minimize the probability of requiring quadratic time. Additionally, quicksort tends to make excellent usage of the memory hierarchy, taking perfect advantage of virtual memory and available caches. Although quicksort is usually not implemented as an in-place sort, it is possible to create such an implementation.
Quicksort (also known as “partition-exchange sort”) is a comparison sort and, in efficient implementations, is not a stable sort.

Quicksort sorts by employing a divide and conquer strategy to divide a list into two sub-lists.
The steps are:
1. Pick an element, called a pivot, from the list.
2. 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.
3. 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.

This is the version of Recursive Quicksort Algorithm written in C language:

int partizione(int a[], int i, int j)
{
	int temp;
	int x;

	x=a[(i+j)/2];
	while ((i<j)&&(a[i]<=x)) i++;
	while(a[j]>x) j--;
	while(i<j)
		   {
			   temp=a[i]; a[i]=a[j]; a[j]=temp;
			   i++; j--;
			   while (a[i]<=x) i++;
			   while (a[j]>x) j--;
		   }
		   return j;
}

void quicksort_ric (int a[], int l, int r)
{
	int m;
	m=partizione(a, l, r);
	if (l<r)
 {
	if ((m-l+1)<(r-m))
	{
		quicksort_ric (a, l, m);
		quicksort_ric (a, m+1, r);
	}

	else {
		quicksort_ric (a, m+1, r);
		quicksort_ric (a, l, m);
	}

 }
}

• Full example of quicksort on a random set of numbers. The shaded element is the pivot. It is always chosen as the last element of the partition. However, always choosing the last element in the partition as the pivot in this way results in poor performance (O(n2)) on already sorted lists, or lists of identical elements. Since sub-lists of sorted / identical elements crop up a lot towards the end of a sorting procedure on a large set, versions of the quicksort algorithm which choose the pivot as the middle element run much more quickly than the algorithm described in this diagram on large sets of numbers. •

One thought on “Recursive Quicksort Algorithm written in C language [with example step-by-step]

Leave a Reply to sathya Cancel reply

Your email address will not be published. Required fields are marked *