## C and Data Structures and Algorithms

Disclosure: This post contains affiliate links. I may earn commission from any sales made or actions taken as a result from users clicking the links on this page.

# Quick Sort in C

Posted in C, Data Structures and Algorithms Similar to merge sort in C, quicksort in C 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.

## The Quicksort Process

Once the partitioning is done, the group of elements smaller than the pivot element is placed before it, and the remaining, greater ones, after it. 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

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.

## Quick Sort in C Program

The following code demonstrates the quick sort in C process. 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,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;
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

#### Another Quick Sort in C Program

Here is another C program that demonstrates quick sorting. It takes the last element of the number set as the pivot and doesn’t ask for 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[] = ;
int n = sizeof(arr)/sizeof(arr);
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

#### Analysis of Quicksort Algorithm (Time Complexity)

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) represents 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.

We’ll calculate the efficiency of the quicksort algorithm for 3 different cases:

• 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 of a quicksort algorithm.
In the aforementioned quick sort in C program, for instance, 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 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)Hence,T(n)worst case = O(n2)
• 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 permutation of the given array (set of elements) and then calculate time taken by each of the permutations. 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, equation (i) gets transformed into,T(n) = T(n/9) + T(9n/10) + (n)
Solution to abovementioned recurrence relation will be,T(n) = (n log n)Hence,T(n)average-case = O(n log n)
• Best Case – The best case of quicksort occurs when the partitioning process always picks the middle element as the pivot. Hence, equation (i) becomes,T(n) = 2T(n/2) + (n)Using case 2 of Master Theorem,T(n) = (n log n)Hence,T(n)best-case = O(n log n)

#### Quicksort vs. The World (A Comparison with other sorting algorithms)

The worst case time complexity pertaining to quicksort is O(n2). Clearly, this is worse than that offered by other popular sorting algorithms, mainly merge sort and heap sort. Amazingly, quicksort is faster in practice than its competitors.

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

Moreover, quicksort can be implemented in different ways, simply by changing the choice of the pivot. And so, the worst case occurs very rarely for any given data. Nonetheless, merge sort is the better option when the data is humongous and stored on some external storage source.

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

When compared to selection sort, quicksort is pretty much identical. The main difference, however, lies in the fact that inefficient implementations, quicksort is not a stable sort. Put it simply, unlike selection sort, quicksort doesn’t always go for worst-case partition.

Program Completion!

So, that was all about quicksort in C. The concept of sorting is one of the fundamental aspects of programming, hence, very important to have good knowledge about it.

The programs that are detailed in the article for the implementation of a quicksort algorithm are two of the several possibilities. Leaning it is best when experimented on your own.

So, go and try it for yourself! You can consult other resources and some of the best C (and C++) books to understand the concept even better and further polish your programming skills as well.

If you have some interesting way of implementing the quicksort algorithm, please brag about it in the comments. The community would love to hear it from you. A Computer Science graduate interested in mixing up imagination and knowledge into enticing words. Been in the big bad world of content writing since 2014. In his free time, Akhil likes to play cards, do guitar jam, and write weird fiction. View all posts by the Author

Your email will not be published Nieves Stackhouse

What is the best way to choose a pivot element in Quicksort? 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

What are the real time applications of quick sort? 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 Dominique Somers

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

• Unstable
• Average efficiency in worst case scenario Which is faster: quick sort or bubble sort, and why? 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

How can I find the median of two sorted arrays? 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

Thank you,
Some of you on here are MATH brilliant.
After too many years in Systems & Networks misc code copy and compile.
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

What will be the complexity of quick sort if array is already sorted? 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

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

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

What is the program of quick sort which has it's median as it's pivot? 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

Is quick sort an in-place algorithm? 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. Marlin Mccallum

How does quick sort work? Jamar Hyland

Quick sort works on divide and conquer technique. It picks an element as pivot from the given list or array and partition the given array around the picked pivot element. Then data is compared with this pivot element, if it is smaller then put before pivot and if it is greater than pivot, it will be placed after pivot.