Fact checked by In this article, I'm going to cover quick sort in C, including what it is, how to write a quicksort program in C, and the Big-O complexity of the quicksort algorithm.
But what is quick sort in C?
If you want the TL-DR: the quicksort algorithm is a fast, divide-and-conquer algorithm that partitions an array around a pivot and then recursively sorts the partitions.
Sounds good, if not a little complicated.
No problem, here's the ELI5: the quicksort algorithm is a lot like organizing a group of kids in a playground by height: you pick one kid (the pivot), have shorter kids go to one side and taller kids to the other, and then do the same for each smaller group until everyone is in order.
But why do you need to know how to write a quick sort program in C? Well, would it help if I told you that quicksort happens to be one of the most popular algorithms for computer science classes, not to mention technical interviews for aspiring C developers?
I'd even say that learning to write a quicksort algorithm is like a rite of passage for all developers. I still remember trying to wrap my head around the idea during my undergraduate studies!
So, if you're ready, let's dive in to learn about quicksort before jumping into coding examples of how to implement quick sort in C.
What Is The Quick Sort Algorithm in C?
So, what is a quick sort algorithm anyway?
Also known as partition-exchange sort, quicksort was developed by Tony Hoare, a British computer scientist, in 1959.
Since publishing his ideas in 1961, quicksort has become one of the top choices for fast array sorting algorithms.
But how does it work? Great question! Let's start with an overview of the actual algorithm.
- Divide and Conquer: Quicksort is a fast, efficient sorting algorithm, that uses a divide-and-conquer strategy to sort an array.
- Picking a Pivot: It starts by selecting a 'pivot' element from the array.
- Partitioning: The array is then partitioned into two parts – elements less than the pivot are moved before it, and elements greater than the pivot are moved after it.
- Recursive Sorting: This partitioning creates a "partial order." The algorithm then recursively applies the same process to the sub-arrays formed by the partition.
- Efficiency: When implemented well, it can be about two or three times faster than its main competitors, merge sort and heapsort.
- Average Complexity: Its average time complexity is O(n log n), but in the worst case, it can degrade to O(n²), especially if the pivot is chosen poorly.
As you can probably tell, the main process in a quicksort algorithm is the partitioning phase.
I think it helps to use a visual example to explain how this works because it can be a little confusing if you're new to C or the concept of recursive algorithms.
So, let's consider a scenario where we need to organize a group of kids in a playground by their height. This group of kid is our array of elements.
To achieve our goal, we'll start by picking one kid, and we'll make them our pivot.
The next step is to ask all kids who are shorter than our pivot to stand on one side, while those who are taller will stand on the other side.
At this stage, we have a partially sorted group of kids, but unless we manage to pick the kid in the middle of the group and all the other kids are already sorted in height order, we need to do more sorting.
That's where recursion comes in, as we'll have to keep repeating this process for each partition (group) of kids on either side of the pivot.
So, we'll select the group of shorter or taller kids, pick a new pivot in that group, and then ask the shorter kids to move to one side and the taller kids to move to the other side.
If we started with the shorter group, we'd then move on to the taller group on the other side of our original pivot and do the same thing.
The net result is that we've now partially sorted our kids even more.
And as you've probably guessed, we'll keep repeating this process until all the kids are fully sorted by height.
But here's a question: how do we choose our pivots?
Well, we have a few options, but it is important to know that the method we choose is crucial for achieving optimal performance:
- Middle Element: A simple and common approach is choosing the array's middle element or sub-array as the pivot. This method is easy to implement but may not always provide a good partition, especially for sorted or nearly sorted data.
- First or Last Element: Choosing the first or last element as the pivot is another straightforward method. However, like the middle element strategy, it can lead to poor performance in certain cases, such as when the array is already sorted.
- Median-of-Three: A more robust approach is the median-of-three method, where you choose the median of the first, middle, and last elements of the array as the pivot. This method offers a better chance of hitting a good partition, especially for arrays with diverse elements.
- Random Pivot: Selecting a random element as the pivot can also be effective. It ensures that the algorithm's average-case performance is maintained, reducing the likelihood of worst-case scenarios (like sorting an already sorted array).
- "Ninther" Method: This is a more refined version of the median-of-three, where you take the median of three sets of three elements (first, middle, last), and then take the median of the three medians. This method is particularly useful for larger arrays.
For the most part, I'd say that the median-of-three or random pivot methods provide a good balance between simplicity and efficiency.
It's also important to remember that if we make our pivot method overly complex, this might not offer a significant performance benefit for the extra complexity it introduces.
How To Write A Quick Sort Program in C
We know what the quicksort algorithm is, so why don't we write a quicksort program in C?
Now, like all algorithms, we can choose any language we like to implement them, whether that's Python, Java, or, in our case, C. If you're not sure you have the skills you need to code this in C, consider taking a C course to get the basics under your belt.
Remember that I said we have multiple options for selecting a pivot element?
Let's use this as a chance to create two versions of the quick sort in C, starting with the middle element as our pivot.
Source Code:
/*
Hackr.io: Quick sort in C
Using Middle Element as Pivot
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void quicksortMiddle(int arr[], int low, int high) {
if (low < high) {
int pivot = arr[(low + high) / 2]; // Selecting the middle element as the pivot
int i = low;
int j = high;
int temp;
while (i <= j) {
while (arr[i] < pivot) i++; // Moving elements smaller than pivot to the left
while (arr[j] > pivot) j--; // Moving elements greater than pivot to the right
if (i <= j) {
temp = arr[i]; // Swapping elements
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
}
// Recursively sort the two partitions
if (low < j) quicksortMiddle(arr, low, j);
if (i < high) quicksortMiddle(arr, i, high);
}
}
// Utility function to print array
void printArray(int arr[], int size)
{
for (int i = 0; i < size; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
int main()
{
int array1[] = {34, 7, 23, 32, 5, 62};
int n = sizeof(array1) / sizeof(array1[0]);
printf("Original Array: \n");
printArray(array1, n);
// Using the Middle Element as Pivot
quicksortMiddle(array1, 0, n - 1);
printf("Sorted with Middle Element as Pivot: \n");
printArray(array1, n);
return 0;
}Output:
Original Array:
34 7 23 32 5 62
Sorted with Middle Element as Pivot:
5 7 23 32 34 62
How Does This Quick Sort Algorithm Work?
So, what's happening here, and how does this quick-sort implementation work?
I think it's a good idea to break this down, as it always helps to truly grasp what's happening so you're ready to tackle any challenging questions that might crop up in interviews or C certification exams.
Quicksort Function: This function takes three parameters: the array to be sorted and two integers to represent the start and end indices of the current subarray segment.
Pivot Selection: We use the start and end indices to find the middle element by summing and dividing them by 2.
Partitioning Process: This section of our Quicksort algorithm is crucial for partitioning the array around the pivot. Let's break down what happens inside these loops:
- Outer Loop (while (i <= j)): This continues as long as i is less than or equal to j. The idea here is to ensure that the partitioning process is performed within the bounds of the current array segment that we’re sorting. Note that i starts from the lowest index of the segment, and j starts from the highest. This loop will continue until the indices meet or cross over.
- First Inner Loop (while (arr[i] < pivot) i++;): This loop increments i as long as the element at that index is less than the pivot. This allows us to skip any elements to the left side of the pivot that are already smaller than it. The loop will stop when an element greater than or equal to the pivot is found or when i reaches j.
- Second Inner Loop (while (arr[j] > pivot) j--;): This loop decrements j as long as the element at that index] is greater than the pivot. This also allows us to skip elements on the right of the pivot that are already greater than it. This loop stops when an element less than or equal to the pivot is found or when j reaches i.
Swapping Process: This section of our quick sort program handles the actual element swapping. Let's break down what happens inside these conditional blocks:
- (if (i <= j)): This is the main conditional check, and we use it to see whether the indices i and j have crossed over or not. If i is less than or equal to j, we know that there are elements on either side of the pivot that are out of place that need to be swapped.
- Swapping Elements:
- temp = arr[i]; When the value at index i is greater than or equal to the pivot, but it’s on the left side of the pivot, we store it in a temporary variable.
- arr[i] = arr[j]; We then move the value at index j (which is less than or equal to the pivot and on the right side of the pivot) to index i.
- arr[j] = temp; We retrieve our temporary variable value that was originally at index i and place it at index j.
In general, this swapping process effectively moves elements that are greater than the pivot to the right and elements that are less than the pivot to the left.
After a swap is completed, we increment i and decrement j. By incrementing i, we can move the pointer forward and skip over the element we just placed in the correct partition. Similarly, by decrementing j, we can move this pointer backward for the same reason.
After we’ve made this swapping update, the i and j indices are ready for the next iteration of the partitioning process and the various while loops we described previously.
Recursive Calls: Remember that quicksort is recursive, so we must make recursive calls for our two partitions. This allows us to sort them independently.
Base Case: Like any recursive algorithm, we need a base case to signal when to terminate and return the results up the call stack. In this case, our recursion has a base case when the lowest index value is greater than or equal to the highest. Put simply, when our subarrays have 0 or 1 elements, we can signal that no further sorting is needed.
Note that I've also included a simple utility function to output the array and its elements both pre and post-sorting.
This is a very simple function that uses a for loop to iterate over and output the elements within the unsorted and sorted array versions.
Another Way To Write A Quicksort Algorithm
In this example, we'll switch things up and use the 'median of three' method to find our pivot element. This means we'll need to adjust our previous code to include a new utility function that we use to find our pivot.
Source Code:
/*
Hackr.io: Quick sort in C
Using Median of Three as Pivot
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int medianOfThree(int x, int y, int z)
{
if ((x < y && y < z) || (z < y && y < x))
return y;
else if ((y < x && x < z) || (z < x && x < y))
return x;
else
return z;
}
void quicksortMedianOfThree(int arr[], int low, int high)
{
if (low < high)
{
int pivotIndex = medianOfThree(low, (low + high) / 2, high);
int pivot = arr[pivotIndex];
int i = low, j = high;
int temp;
while (i <= j)
{
while (arr[i] < pivot)
i++;
while (arr[j] > pivot)
j--;
if (i <= j)
{
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
}
if (low < j)
quicksortMedianOfThree(arr, low, j);
if (i < high)
quicksortMedianOfThree(arr, i, high);
}
}
// Utility function to print array
void printArray(int arr[], int size)
{
for (int i = 0; i < size; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
int main()
{
int array2[] = {34, 7, 23, 32, 5, 62};
int n = sizeof(array2) / sizeof(array2[0]);
printf("Original Array: \n");
printArray(array2, n);
// Using the Median of Three as Pivot
quicksortMedianOfThree(array2, 0, n - 1);
printf("Sorted with Median of Three as Pivot: \n");
printArray(array2, n);
return 0;
}Output:
Original Array:
34 7 23 32 5 62
Sorted with Middle Element as Pivot:
5 7 23 32 34 62
How Does The Quick Sort Program Work?
So, what's happening here, and how does this quick-sort implementation differ from our previous version?
You should be able to see that the underlying quicksort algorithm is largely unchanged.
The main difference is the inclusion of our new utility function to find the pivot element with the median of threes.
Let's break this down:
The goal of our new utility function is to find the median among three given values x, y, and z.
This is easy enough to find, as the median is simply the middle value when the three numbers are sorted in ascending order.
So, our new function uses the following logic to find the median:
- If y is between x and z (either x < y < z or z < y < x), then y is the median.
- If x is between y and z (either y < x < z or z < x < y), then x is the median.
- If neither x nor y is the median, then z must be the median.
But how do we choose the three values to pass to our new function? This is, after all, the key to our pivot selection.
Well, we pass in three values: the lowest index in the current array segment, the highest index in the current segment, and then the middle element.
The median value of these three values is then used to select our pivot value.
Remember, the idea with this method is to choose a pivot that is more representative of the array's contents, potentially leading to a more balanced partition and improved performance.
This is especially helpful when the array might be partially sorted or have underlying number patterns.
The rest of the quicksort algorithm remains unchanged, so there's no need to cover that again. The main change here is that we're using a slightly more complex method to find pivots during the sorting process.
Note also that the array printing utility function is also unchanged, and this simply lets us print out the array both pre and post-sorting.
Now we've created two versions of the quicksort algorithm, why don't you have a go at creating another version using a random pivot selection?
New To Programming With C? Check Out This C Programming Course For Beginners
Time Complexity Of The Quicksort Algorithm
If you've spent time learning about data structures and algorithms, you'll probably notice that we're often concerned with Big-O notation to find the time and space complexity as the problem grows very large in size.
So, let's follow the tradition and figure out the time complexity of the quicksort algorithm.
To begin, we can describe the quicksort algorithm's efficiency for sorting an array of n elements with a generalized expression..
Remember that quick sort depends on recursion and partitioning, so we’ll need an expression that represents these aspects when deriving the general time complexity.
T(n) = T(k) + T(n-k-1) + O(n)
Let’s break down what this expression shows:
- T(n): the total time to sort n elements
- T(k) and T(n-k-1): The time taken to sort the two partitions created after choosing a pivot. Note that k is the number of elements in the partition that are smaller than the pivot, which means that n-k-1 is the number of elements in the partition larger than the pivot (excluding the pivot).
- O(n): This accounts for the time taken to partition the array around the pivot, and as we can see, this typically takes linear time.
Great, let’s now take a look at how we can apply this equation to different scenarios, as these will affect the overall time complexity of the quick sort algorithm.
Worst-Case:
- This is when the pivot is the smallest or largest element, as it leads to highly unbalanced partitions. For example, if the array is already sorted and the last element is chosen as the pivot.
- The equation in this case tends towards T(n) = T(0) + T(n-1) + O(n), simplifying to T(n) = T(n-1) + O(n).
- The time complexity in this scenario is O(n²), as each partition operation only excludes one element at a time.
Average-Case:
- This assumes a more balanced partitioning, though not perfect. The pivot typically divides the array into parts that aren't equal but don't represent the extreme imbalance of the worst case.
- Even though exact partition sizes vary, the average case is often approximated to provide a time complexity of O(n log n), considering that the partitions are reasonably balanced on average.
Best-Case:
- Occurs when the pivot consistently divides the array into two nearly equal halves.
- This scenario is very unlikely unless specific strategies are employed to choose the pivot.
- The best-case time complexity is O(n log n), similar to the average case, but it assumes nearly perfect partitioning in each step.
As you can see, the quicksort's performance largely depends on the pivot selection strategy.
While the worst case can lead to quadratic time complexity O(n²), if we can use an effective pivot selection strategy, we can typically achieve log-linear time complexity with O(n log n).
Quicksort vs. Other Sorting Algorithms
Sure, quicksort is a widely used sorting algorithm that's known for its efficiency, but how does it stack up against other popular sorting methods?
Let's take a closer look, shall we?
Quicksort vs. Merge Sort
Time Complexity
- Quicksort: Average and best case O(n log n), worst case O(n²).
- Merge Sort: Always O(n log n) in all cases.
Comparison
While quicksort has a worst-case time complexity of O(n²), it's generally faster than merge sort in practice due to better cache performance and lower constant factors in the average case.
That said, merge sort algorithms have a consistent log-linear time complexity of O(n log n), making them more predictable and a better choice for data sets where worst-case performance is a significant concern, such as in real-time systems.
Quicksort vs. Heap Sort
Time Complexity
- Quicksort: Average and best case O(n log n), worst case O(n²).
- Heap Sort: Always O(n log n).
Comparison
Much like merge sort, heap sort also offers log-linear time complexity of O(n log n), but quicksort typically outperforms due to better cache usage.
That said, heap sort does have the advantage of being an in-place algorithm with guaranteed worst-case performance of O(n log n), which also makes it more reliable for data sets where memory usage is a critical factor.
Quicksort vs. Bubble Sort
Time Complexity
- Quicksort: Average and best case O(n log n), worst case O(n²).
- Bubble Sort: Worst and average case O(n²), best case O(n).
Comparison
It's fair to say that bubble sort is significantly slower than quicksort due to a quadratic time complexity in both the average and worst cases.
For me, bubble sort's main advantage is its simplicity and ease of implementation, which is why it's always super popular for small data sets or for educational purposes. Yep, if you've taken any CS classes or learned about data structure and algorithms, you've almost certainly written a bubble sort algorithm!
Quicksort vs. Selection Sort
Time Complexity
- Quicksort: Average and best case O(n log n), worst case O(n²).
- Selection Sort: Always O(n²).
Comparison
Selection sort has a time complexity of O(n²) in all cases, making it less efficient than quicksort for larger datasets.
But despite its obvious speed advantage, quicksort differs from selection sort when it comes to stability.
That's because quicksort is typically unstable due to its partitioning approach that can alter the relative order of equal elements, while selection sort can maintain their original order, making it stable.
So, in summary, while quicksort's worst-case time complexity of O(n²) can be a drawback, its average-case performance often makes it faster than merge sort and heap sort for most real-world data.
But, its variability in performance makes merge sort a more predictable choice in scenarios where worst-case performance is critical.
Simpler algorithms like bubble sort and selection sort, while less efficient for large datasets, offer ease of implementation and stability.
Wrapping Up: Quick Sort Algorithm
You should now understand the quicksort algorithm, including how to code quick sort in C with different pivot strategies.
I've also covered the quicksort algorithm's time complexity, how the pivot affects performance, and how quicksort compares with other popular sorting algorithms. This is all great information to have in your locker if you plan to take technical interviews for coding jobs.
I hope you enjoyed this exploration of quick sort in C, and feel free to leave a comment below!
Happy coding!
Enjoyed learning about quick sort and ready to boost your skills in C? Check out:
Udemy's Top-Rated Course To Master Data Structures & Algorithms With C and C++
