Similar to merge sort, quick sort in C is a divide and conquer algorithm developed by Tony Hoare in 1959. The name comes from the fact that quicksort in C is faster than all the other standard sorting algorithms. The quickness is the result of its approach. The quicksort algorithm starts by picking a pivot element and then subdivides the array. It then puts the smaller elements on the left side of the pivot and the larger ones on the right side. The partition of arrays continues until each array is left with a single element. These arrays are then combined to create and display the sorted array. Due to this approach, the quicksort in C is also referred to as the “Partition Exchange” sort algorithm.
Partition is a key process in the functioning of the quicksort algorithm. The algorithm takes the pivot element and keeps partitioning the array. It then positions the pivot element at the right position on the sorted array while keeping all the smaller elements on the left and larger elements on the right side of the pivot.
Pseudocode for Quick Sort in C
The pseudocode for the quicksort algorithm in C is:
/* Considering l as the first and h as the last index */
quickSort(array[], l, h)
{
if (l < h)
{
/* Considering pi as the index of the pivot element */
pi = partition(array, l, h);
quickSort(array, l, pi - 1);
quickSort(array, pi + 1, h);
}
}
Partition() Function for QuickSort in C
The partition() function, as mentioned earlier, divides and subdivides an array for sorting it using the selected pivot element. Quick sort in C can pick different pivot elements, such as:
- Always the first element of the array
- Always the last element of the array
- Any random element from the array
- Always the median of the array
After dividing the array, the partition algorithm traverses through it and keeps track of smaller elements using a pointer; whenever a smaller element is found, the algorithm swaps the current element with the smaller one. If the element is not smaller, the algorithm ignores it.
Pseudocode for Partition() in C
The following is the pseudocode for partition() algorithm in C when the last element of the array is the pivot element.
partition (array[], low, high)
{
pivot = array[high];
i = (low - 1) // Indicates the index of the smaller element and the right position of the pivot
for (j = low; j <= high- 1; j++){
// Swap if current element is smaller than the pivot
if (array[j] < pivot)
{
i++;
swap array[i] and array[j]
}
}
swap array[i + 1] and array[high])
return (i + 1)
}
Working of QuickSort in C
Depending on the pivot selected, the quicksort in C will work as below:
- Once the pivot is selected, the elements smaller than the pivot are placed to its left, and the higher ones are put to the right. This helps to select the correct position for the pivot element in the array.
- The array is then further divided, with the pivot being the last element of the first subarray and the rest being the second subarray.
- Again the leftmost element of both the subarrays are chosen as a pivot, and the first two steps are repeated until the divided array is left with a single element.
- In the end, the subarrays with a single element are combined to form the final sorted array.
Implementing QuickSort in C
Here, we will be implementing quicksort in C by taking the first/low element as the pivot element. We will ask the user to select the array’s length and then the values of the elements in the array. Next, we will use the partition() function and define the first element as the pivot to divide and subdivide the array for sorting it. In the end, we will use the printf() library function to display the array sorted using quicksort in C.
Example:
#include<stdio.h>
/* Declaring an array, first element as low, and last element as high */
void quicksort(int array[25],int low,int high){
int x, y, p, temp;
if(low<high){
p=low;
x=low;
y=high;
while(x<y){
while(array[x]<=array[p]&&x<high)
x++;
while(array[y]>array[p])
y--;
if(x<y){
temp=array[x];
array[x]=array[y];
array[y]=temp;
}
}
temp=array[p];
array[p]=array[y];
array[y]=temp;
quicksort(array,low,y-1);
quicksort(array,y+1,high);
}
}
int main(){
int x, count, array[25];
printf("How many elements should the array have? (Max. - 25): ");
scanf("%d",&count);
printf("Enter %d elements for the array: ", count);
for(x=0;x<count;x++)
scanf("%d",&array[x]);
quicksort(array,0,count-1);
printf("After implementing quicksort the sorted order is: ");
for(x=0;x<count;x++)
printf(" %d",array[x]);
return 0;
}
Output:
Time and Space Complexity for QuickSort in C
Time Complexity
The average time taken by a quicksort algorithm can be calculated as below:
T(n) = T(k) + T(n-k-1) + \theta(n)
The time complexity of the quicksort in C for various cases is:
- Best case scenario: This case occurs when the selected pivot is always middle or closest to the middle element of the array. The time complexity for such a scenario is O(n*log n).
- Worst case scenario: This is the scenario where the proper position of the selected pivot is always the first or last element of the array. In this case, one of the divided arrays will have no element, and the other will have (n-1) elements, where n is the total number of elements of the array. Hence, the sorting and partition will occur in only one of the arrays. The time complexity for this case will be O(n²).
- Average case scenario: This case occurs when the pivot is not the middle element or the farthest element of the array. The time complexity here will be O(n*log n).
Space Complexity
The space complexity for the quicksort algorithm in C is:
O(log n)
What Is 3-Way QuickSort in C?
While performing a simple quick sort in C, we select a pivot and then complete the partitions around it. But what about situations when the pivot occurs multiple times. Suppose there’s an array arr with the elements 6, 7, 8, 7, 5, 2, 6, 7, 9, 7, 3, 4, 7, and the pivot element is 7. There are multiple instances of 7. Hence, a simple quicksort won’t be the best solution here. In such a scenario, 3-way quicksort is helpful. In 3-way quicksort, the array is divided into three parts:
- Elements less than the pivot
- Elements greater than the pivot
- Elements equal to the pivot
Dividing the array into three parts will help optimize quicksort in C and provide results quickly.
What Are the Applications of QuickSort in C?
The C quicksort can be used for various real-life solutions. Some of the most common quicksort applications include:
- Numerical computations: Several efficiency algorithms use priority queues and sorting for higher calculation accuracy.
- Commercial computing: Numerous organizations use sorting of data like profiles, IDs, accounts, location, transaction history, etc.
- Information search: You can use this to search a piece of particular information from enormous data quickly.
Alternative Options to QuickSort in C
C programming allows sorting through various other algorithms as well. Some alternatives to quicksort in C are:
- Merge sort
- Bubble sort
- Selection sort
- Insertion sort
- Bucket sort
Conclusion
In this article, you have learned about quicksort in C. This sorting algorithm will help you quickly sort an array or even a list as it is almost twice or thrice as faster when compared to other sorting algorithms in C. You can now use quicksort in C with the partition() function to sort an array and create a complex program using it where sorting is required.
You can take our Post Graduate Program in Full Stack Web Development to excel in the field of software development. Overall development requires mastery of multiple programming languages and tools. Our courses are designed to provide you the skills you need to become proficient and a sought-after developer.