Quick Sort Uncovered: Efficient Sorting with Detailed C Implementation
Dive into Quick Sort, with step-by-step guides, C code insights, and complexities explained simply.
Introduction to Quick Sort
Quick Sort is a highly efficient sorting algorithm and is based on the divide-and-conquer strategy similar to Merge Sort. However, it is often preferred because it performs better in practice on most datasets, due to its superior locality of reference and cache performance. This blog will provide an in-depth analysis of Quick Sort, from its conceptual framework to its actual implementation in the C programming language.
Understanding the Quick Sort Algorithm
Quick Sort operates by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively. This ability to sort in place makes Quick Sort particularly space-efficient and fast for arrays.
Pseudo Code for Quick Sort
To help conceptualize Quick Sort, let's start with a simple pseudo code:
quickSort(arr, low, high) {
if (low < high) {
// pi is partitioning index, arr[pi] is now at right place
pi = partition(arr, low, high);
quickSort(arr, low, pi - 1); // Before pi
quickSort(arr, pi + 1, high); // After pi
}
}
partition(arr, low, high) {
pivot = arr[high];
i = (low - 1); // Index of smaller element
for (j = low; j <= high - 1; j++) {
// If current element is smaller than the pivot
if (arr[j] < pivot) {
i++; // increment index of smaller element
swap arr[i] with arr[j];
}
}
swap arr[i + 1] with arr[high]);
return (i + 1);
}
Step-by-Step Explanation
- Choose a Pivot: The choice of pivot can be the key to the algorithm's efficiency. Common methods include choosing the last element, the first element, the median, or a random element.
- Partitioning: Rearrange the array so that elements less than the pivot come before it and elements greater come after it. After partitioning, the pivot is in its final position.
- Recursive Sort: Apply the same logic recursively to the sub-arrays formed by splitting the array around the pivot.
Implementation in C
Below is a commented implementation of Quick Sort in C:
#include <stdio.h>
// Function to swap two elements
void swap(int* a, int* b) {
int t = *a;
*a = *b;
*b = t;
}
// Function to perform the partition
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);
}
// Function to implement Quick Sort
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);
}
}
// Driver code to test the Quick Sort function
int main() {
int arr[] = {10, 80, 30, 90, 40, 50, 70};
int n = sizeof(arr)/sizeof(arr[0]);
quickSort(arr, 0, n - 1);
printf("Sorted array: \n");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}
Explanation of the C Code
- Swap Function: A helper function to swap two elements.
- Partition Function: Arranges the elements around the pivot and returns the index of the pivot element in the sorted array.
- Quick Sort Function: Recursively sorts the sub-arrays.
Time and Space Complexity
Time Complexity
- Best Case: O(n log n)
- Average Case: O(n log n)
- Worst Case: O(n²), occurs when the smallest or largest element is always picked as the pivot.
Space Complexity
- Space Complexity: O(log n), due to the stack space used by recursive calls.
Usage of Quick Sort
Quick Sort is particularly useful in systems where space complexity is a concern, and it's widely used in libraries and systems due to its average case efficiency. It's well-suited for large datasets and often used in conjunction with hybrid sorting algorithms.
Conclusion
Quick Sort is a cornerstone of sorting algorithms due to its efficiency and simplicity. Understanding its implementation and behavior provides a solid foundation in sorting algorithms, essential for any aspiring programmer. This guide aims to demystify Quick Sort and provide a ready reference for implementation, making it an invaluable resource for practical and educational purposes.