Jay Abhani
Senior Web Development Instructor at almaBetter
Learn the efficient sorting algorithm, Quick Sort in C with detailed implementation, pseudocode, optimizations, and practical applications for enhanced performance.
Sorting is a fundamental operation in computer science, and one of the most efficient sorting algorithms is Quick Sort. This article delves into the intricacies of Quick Sort in C, providing a detailed understanding of the algorithm, its implementation, and its advantages.
Quick Sort is a highly efficient sorting algorithm that employs the divide-and-conquer strategy. It was developed by Tony Hoare in 1959 and has since become one of the most widely used sorting algorithms due to its superior performance in practical applications. The primary idea behind Quick Sort is to partition the array into smaller sub-arrays, sort these sub-arrays, and then combine them to form the final sorted array.
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 process can be broken down into the following steps:
Quick Sort Visualization
QUICKSORT(arr, low, high)
if low < high then
pivotIndex = PARTITION(arr, low, high)
QUICKSORT(arr, low, pivotIndex - 1)
QUICKSORT(arr, pivotIndex + 1, high)
PARTITION(arr, low, high)
pivot = arr[high]
i = low - 1
for j = low to high - 1 do
if arr[j] <= pivot then
i = i + 1
SWAP(arr[i], arr[j])
SWAP(arr[i + 1], arr[high])
return i + 1
SWAP(a, b)
temp = a
a = b
b = temp
Initialization:
Partitioning:
Element Comparison and Swapping:
Final Pivot Placement:
Recursive Sorting:
Let's walk through an example to see how the pseudocode translates into action. Consider the array: [10, 7, 8, 9, 1, 5].
After these steps, the array is sorted: [1, 5, 7, 8, 9, 10].
#include <stdio.h>
// Function to swap two elements
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
// Partition function
int partition(int arr[], int low, int high) {
int pivot = arr[high]; // pivot
int i = (low - 1); // Index of smaller element
for (int j = low; j <= high - 1; j++) {
// If current element is smaller than or equal to pivot
if (arr[j] <= pivot) {
i++; // increment index of smaller element
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}
// The main function that implements QuickSort
void quickSort(int arr[], int low, int high) {
if (low < high) {
// pi is partitioning index, arr[p] is now at right place
int pi = partition(arr, low, high);
// Separately sort elements before partition and after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
// Function to print an array
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
// Driver program to test above functions
int main() {
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
printf("Sorted array: ");
printArray(arr, n);
return 0;
}
Explanation
Swap Function: This utility function swaps two elements in the array.
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
The swap function uses a temporary variable to swap the values of two integers. This function is crucial in the partitioning process to move elements around the pivot.
Partition Function: This function takes the last element as the pivot, places the pivot at its correct position in the sorted array, and places all smaller elements to the left of the pivot and all greater elements to the right.
int partition(int arr[], int low, int high) {
int pivot = arr[high]; // pivot
int i = (low - 1); // Index of smaller element
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);
}
The partition function is where the array is rearranged. It places the pivot element in its correct position and ensures all elements less than the pivot are on its left and all elements greater are on its right.
QuickSort Function: This is the main function that implements the Quick Sort algorithm. It recursively calls itself to sort the sub-arrays.
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);
}
}
The quickSort function calls the partition function to get the pivot index and then recursively sorts the sub-arrays before and after the pivot.
PrintArray Function: This utility function prints the array.
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
The printArray function is a simple loop that prints each element of the array.
Main Function: This is the driver function that initializes the array, calls the quickSort function, and prints the sorted array.
int main() {
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
printf("Sorted array: ");
printArray(arr, n);
return 0;
}
The main function initializes the array, calculates its size, and calls quickSort to sort the array. Finally, it prints the sorted array.
Learn more with our latest blogs “History of C Language” and “Bubble Sort in C”
Quick Sort is known for its efficiency and is often faster in practice than other O(n log n) algorithms like Merge Sort and Heap Sort. However, its performance depends on the choice of the pivot.
The efficiency of Quick Sort largely depends on the choice of the pivot. Here are some common strategies for choosing the pivot:
Efficient for Large Datasets: Quick Sort is one of the fastest sorting algorithms for large datasets.
In-Place Sorting: Quick Sort does not require additional storage space, making it more memory-efficient than Merge Sort.
Divide-and-Conquer Approach: The divide-and-conquer strategy allows for efficient parallelization, which can further enhance performance on modern multi-core processors.
Unstable Sorting: Quick Sort is not a stable sort, meaning that equal elements may not retain their relative order. However, this can be mitigated with modifications to the partitioning scheme.
Worst-Case Performance: Its worst-case time complexity is O(n^2), which can be mitigated by using randomized or median-of-three pivot selection techniques.
Quick Sort in C is a highly efficient sorting algorithm that uses a divide-and-conquer approach to partition and sort arrays. This article has provided a comprehensive look at Quick Sort, including its theoretical basis, pseudocode, implementation in C, and example walkthrough.
Quick Sort is widely applicable across various domains, such as databases, file systems, e-commerce, searching algorithms, data analysis, and more. Its performance can be optimized by choosing a good pivot and employing simpler sorting algorithms for small sub-arrays.
Understanding and implementing Quick Sort can significantly enhance your ability to efficiently sort data, making it an essential tool in your programming arsenal.
Enroll in our full stack web development course with a pay after placement opportunity to enhance your skills and secure your future!
Related Articles
Top Tutorials