Quick Sort in C Guide [With Code]

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 #include #include 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…


Source link