Need a discount on popular programming courses? Find them here. View offers

C and Data Structures and Algorithms


Disclosure: Hackr.io is supported by its audience. When you purchase through links on our site, we may earn an affiliate commission.



Quick Sort in C

Posted in C , Data Structures and Algorithms
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:

Leave a comment

Your email will not be published
Cancel
Anand A
Anand A 10 Points

Is quick sort and partition sort same or different

Nieves Stackhouse
Nieves Stackhouse

What is the best way to choose a pivot element in Quicksort?

Thurman Alicea
Thurman Alicea

For the fastest quicksort, the best way to choose a pivot element is to choose 2 pivot elements (dual pivot-quicksort) or 3-pivot elements (3-pivot quicksort).

Jennefer Lombardi
Jennefer Lombardi

What are the real time applications of quick sort?

Darrick Emanuel
Darrick Emanuel

• Defense
• Medical monitoring
• Life support in aircraft and space crafts
• Monitoring and control in industrial and research plants
• Handling dangerous materials
• Control for aircraft etc

Lu Wentworth
Lu Wentworth

What are the advantages and disadvantages of quicksort?

Dominique Somers
Dominique Somers

Advantages:
• High performance
• In-place sorting algorithm
• No extra memory required
• Quick sort is better than other sorting algorithms
• High efficiency
• Faster than merge sort.

Disadvantages:
• Unstable
• Average efficiency in worst case scenario

Kristle Rosado
Kristle Rosado

Which is faster: quick sort or bubble sort, and why?

Carmine Garris
Carmine Garris

Quick sort is faster than bubble sort. Bubble sort has average case complexity of O(n^2) while Quick sort has O(n log n). Bubble sort is actually fast for small data sets like 10 elements or may be even for 100 elements.

Donita Gamble
Donita Gamble

How can I find the median of two sorted arrays?

Dillon Bolen
Dillon Bolen

Median is at index (n-1)/2, if number of elements in array is N.
Let’s understand this by an example:
Two sorted arrays are here-
ar1[] = {1,12,15,26,38}
ar2[] = {2,13,17,30,45}
Explanation:
After merging two arrays we get:
{1,2,12,13,15,17,26,30,38,45}
Middle elements are – 15 and 17
Median of two elements is (15+17)/2
Which is equal to 16

joe
joe

Thank you,
Some of you on here are MATH brilliant.
After too many years in Systems & Networks misc code copy and compile.
Thinking about switch to SoftEng.
There are way too many smarter younger faster brains in the field today.

I am very pleasantly surprised people are still learning MATH.

Matthew Phelan
Matthew Phelan

What will be the complexity of quick sort if array is already sorted?

Hong Loveless
Hong Loveless

The reason behind this is randomized version has O(n logn) expected total number of comparisons. The deterministic version doesn't enjoy this property, as is widely known. the distribution on input order does not matter anymore so this can be a great idea to use. When the data is too large then it’s an amazing algorithm to be used. Quick sort is optimal as it has more than linear growth at least in average case.

Gail Quintero
Gail Quintero

This will be the worst case complexity O(n^2) of quicksort. This happens when input array is already sorted or reverse sorted and either first or last element is picked as the pivot.

Shantell Donaldson
Shantell Donaldson

How does randomized quick sort perform better than the standard quick sort algorithm? Why should anybody care about a sorting method that is not optimal?

Sharda Halcomb
Sharda Halcomb

What is the program of quick sort which has it's median as it's pivot?

Alphonso Longoria
Alphonso Longoria

This will be the best case of quick sort in which partition process always picks the middle element as pivot. Recurrence for best case is O(n log n).

Lara Mccreary
Lara Mccreary

Is quick sort an in-place algorithm?

Willian Crider
Willian Crider

In-place idea is about space efficiency. Yes, Quick sort is an in-place algorithm. There is no need to allocate additional memory in the heap memory.