Quick Sort in C

Like merge sort in C, quick sorting in C also follows the principle of decrease and conquer — or, as it is often called, divide and conquer. The quicksort algorithm is a sorting algorithm that works by selecting a pivot point, and thereafter partitioning the number set, or array, around the pivot point.

Also known as partition-exchange sort, quicksort was developed by Tony Hoare, a British computer scientist, in 1959. Since its publishing in 1961, quicksort has become one of the top choices in sorting algorithms. 

In this guide, we’ll explain the algorithm with an example quick sort program in C. You’ll also learn how quick sort fares against other sorting algorithms and the scenarios in which quicksort works best.

What is the Quick Sort Program in C?

The main process in a quicksort algorithm is partitioning. If x is the pivot in an array, then the main intent of the sorting process is to put x at the right position in a sorted array, such that smaller elements precede x and greater elements follow it.

Once the pivot element has been selected, the elements smaller than the pivot element are placed before it, and the greater ones after. There are several variations of the quick sort algorithm, depending on what kind of element (or number) is selected as the pivot:

• The first element as the pivot
• The last element as the pivot
• A random element as the pivot
• Median as the pivot

A Quick Sort Program in C

The quicksort code in C is quite simple and you should be able to implement it in under 10 minutes once you’ve wrapped your head around the logic. 

The following code demonstrates quick sorting in C quite clearly. It asks the user to input a number of elements (up to 25) that requires sorting and then presents those elements in the sorted order:

#include<stdio.h>

void quicksort(int number[25],int first,int last){

int i, j, pivot, temp;

if(first<last){

pivot=first;

i=first;

j=last;

while(i<j){

while(number[i]<=number[pivot]&&i<last)

i++;

while(number[j]>number[pivot])

j--;

if(i<j){

temp=number[i];

number[i]=number[j];

number[j]=temp;

}

}

temp=number[pivot];

number[pivot]=number[j];

number[j]=temp;

quicksort(number,first,j-1);

quicksort(number,j+1,last);

}

}

int main(){

int i, count, number[25];

printf("Enter some elements (Max. - 25): ");

scanf("%d",&count);

printf("Enter %d elements: ", count);

for(i=0;i<count;i++)

scanf("%d",&number[i]);

quicksort(number,0,count-1);

printf("The Sorted Order is: ");

for(i=0;i<count;i++)

printf(" %d",number[i]);

return 0;

}

Sample Output:

Enter some elements (Max. - 25): 5

Enter 5 elements: 5 22 -19 63 1

The Sorted Order is: -19 1 5 22 63

How Does Quick Sorting Work?

The following steps break down the quicksort algorithm in C:

1. We start with the main function. Before the quicksort is called, the user inputs the number of elements to be sorted and then the elements themselves. 
2. We store the 25 numbers (the array’s elements) in the array number, and represent the first and last element with the variables first and last. We then call the quicksort function, which moves the algorithm onto the next step.
3. If the first element is smaller than the last element, it sets the pivot to the first element.
4. It calls a while loop to increment i and decrement j depending on their relation to the pivot. In simpler terms, this checks whether elements lower/higher than the pivot and divides the whole array into two sub-arrays; this is the partition step.
5. The quicksort then recursively calls itself to sort the two sub-arrays accordingly until the whole array is sorted.
6. The sorted array is printed.

Another Quicksort Example

Here is another C program that demonstrates quick sorting. In this case, we’ll have the  last element be the pivot and we won’t take any input.

#include<stdio.h>

void
swap (int *a, int *b)
{

  int t = *a;

  *a = *b;

  *b = t;

}

int
partition (int arr[], int low, int high)
{

  int pivot = arr[high];

  int i = (low - 1);

  for (int j = low; j <= high - 1; j++)

    {

      if (arr[j] <= pivot)

	{

	  i++;

	  swap (&arr[i], &arr[j]);

	}

    }

  swap (&arr[i + 1], &arr[high]);

  return (i + 1);

}

void
quickSort (int arr[], int low, int high)
{

  if (low < high)

    {

      int pi = partition (arr, low, high);

      quickSort (arr, low, pi - 1);

      quickSort (arr, pi + 1, high);

    }

}

void
printArray (int arr[], int size)
{

  int i;

  for (i = 0; i < size; i++)

    printf ("%d ", arr[i]);

  printf ("\n");

}

int
main ()
{

  int arr[10] = { 9, 15, 10, 12, 23, 4, 48, 11, 12, 6 };

  int n = sizeof (arr) / sizeof (arr[0]);

  quickSort (arr, 0, n - 1);

  printf ("The sorted array is: \n");

  printArray (arr, n);

  return 0;

}

Output:

The sorted array is:

-8 5 9 11 17 22

Program Explanation 

In this example, we use the last element as the pivot. You’ll notice that, in this case, the swapping and partition procedures are written in their own functions, as opposed to all in the same quicksort function. This helps readability and reusability. 

This is how the quick sort algorithm proceeds when we use the last element as a pivot:

1. We define the array to be sorted. We pass the parameters of array size, the first and last element to the quicksort algorithm
2. The algorithm checks if the first element is indeed lower than the last element. If yes, it passes the array, first and last element to the partition function.
3. The partition function sets the pivot element to the last element in the array and sets a variable i that increments and is used for partitioning the elements into sub-arrays.
4. With the partition in place, the quicksort function recursively calls itself to sort the two sub-arrays, and by extension, the whole array.
5. The sorted array is printed.

Data Structures & Algorithms using C++, C and Python - 2023

The Complexity of the Quicksort Algorithm

The time required by the quicksort algorithm for sorting a total of n numbers is represented by the following equation:

T(n) = T(k) + T(n-k-1) + (n) → (i)

T(k) and T(n-k-1) represent the two recursive calls in the quicksort algorithm. The last term (n) represents the partition process, while k is representative of the total count of the numbers present in the set that is smaller than the pivot.

Note that the total time taken by a quicksort algorithm to complete is dependent on the input array as well as the partition strategy deployed.

There are 3 different cases for the efficiency of the quicksort algorithm:

• Worst case: When the partition process always picks either the smallest or the greatest element as the pivot, it is considered to be the worst case for a quicksort algorithm. For instance, in our quick sort in C program, where the last element is selected as the pivot point, the worst case occurs if the array is already sorted.
  The equation (i) gets transformed for the worst case of quick sort as follows:T(n) = T(0) + T(n-1) + (n). It can be written as: T(n) = T(n-1) + (n) This gives T(n) the worst case of O(n^2)
• Average case: Any case of quicksort that doesn’t belong to either the worst case or the best case is an average case.
  In order to carry out average case analysis of quicksort, we need to consider all possible permutations of the given array and then calculate the time taken by each. Obviously, it is a very complex process.
  A way around this problem is to consider the average case when the partitioning process puts (n/9) elements in one set and (9n/10) elements in the other one.
  Therefore, the equation (i) gets transformed into T(n) = T(n/9) + T(9n/10) + (n)
  The solution to this recurrence relation is T(n) = (n log n). Here,the average case of T(n) is O(n log n)
• Best case: The best case of quicksort occurs when the partitioning process always picks the middle element as the pivot. Here, the equation (i) becomes T(n) = 2T(n/2) + (n). Using case 2 of Master Theorem,T(n) = (n log n). Thus,the best case for T(n) is O (n log n)

Quicksort vs. Other Sorting Algorithms

Quicksort’s time complexity of O(n2) in the worst case is clearly worse than that of other popular sorting algorithms, namely merge sort and heap sort. However, in practice, quick sort is faster than other algorithms.

When carefully implemented, quicksort can be as much as two to three times faster than merge sort and heap sort. This is so because the inner loop of quicksort algorithm allows being effectively implemented on most system architectures for most forms of real-world data.

Quicksort can also be implemented in different ways simply by changing the choice of the pivot. This makes it unlikely that the worst case will occur. Having said that, merge sort is the better option when dealing with a lot of the data that is stored externally.

Although bubble sort is not a direct competitor to quicksort, it can be considered for scenarios where simplicity is the main priority. This is due to the simplistic nature of bubble sort as opposed to quicksort, which is more complex.

When compared to selection sort, quicksort is pretty much identical. The main difference, however, lies in the fact that quicksort is not a stable sort. 

When is the Quick Sort Algorithm Used?

The quick sort algorithm is one of the faster algorithms and is used when a stable sort isn’t needed. It does not require any extra storage memory, and finds applications in information searching, operational research and event-driven simulation. It is also tail recursive, which is optimized by the compiler.

Try the Quick Sorting in C Yourself

You’ve just learned how to write a quick sort program in C. The concept of sorting is a fundamental part of programming, and hence, it is very important to understand it thoroughly.

You’ve seen two different examples of a quick sort program in C, but it is best understood through practice. Go ahead and try it yourself, and try to understand the workings of the code line by line.

You can also consult other resources and some of the  to understand sorting concepts even better, further polishing your programming skills.

Learn More About C and C++ Today!

People are also reading:

• Merge Sort in C
• Bubble Sort in C
• Best C Courses 
• Get the Difference between C vs C++
• C Interview Questions & Answers