Quick Sort in C
Have you ever wondered how large datasets are sorted efficiently in programming? Quick Sort in C is the answer, utilizing a divide-and-conquer strategy to sort arrays rapidly by partitioning them around a pivot and recursively sorting the partitions. Let's read more!
Quick Sort is a widely used sorting algorithm that follows the divide-and-conquer approach. It's known for its efficiency in sorting large datasets and is commonly used in various applications due to its good average-case performance. Quick Sort is used in scenarios where average-case performance is important. It's particularly effective for large datasets. However, in cases where worst-case performance is critical, other algorithms like Merge Sort or Heap Sort might be preferred due to their consistent O(n log n) performance.
Read LaterHow Does Quick Sort Work?
Quick Sort is the epitome of divide-and-conquer strategies in sorting algorithms. It operates on the principle of selecting a 'pivot' and then partitioning the array around this pivot.
- Pivot Selection: Choose an element from the array as the pivot.
- Partitioning: Reorder the array so that all elements with values less than the pivot come before it, while all elements with values greater than the pivot come after it.
- Divide and Conquer: Recursively apply the above steps to the sub-arrays of elements with smaller and larger values.
The beauty of Quick Sort lies in its ability to perform sorting as it partitions, leading to efficient use of time and resources.
Illustration
Imagine Quick Sort as a game of chess:
- The pivot is the strategic move that defines the game.
- Each partitioning is like a tactical play, dividing the board and conquering each section.
- The recursive nature of Quick Sort is like planning multiple moves ahead, each one setting up for the next.
Best-suited Data Structures and Algorithms courses for you
Learn Data Structures and Algorithms with these high-rated online courses
Quick Sort Algorithm
Step 1: Initialize two pointers, i and j, at the beginning and end of the array (excluding the pivot).
Step 2: Increment i until you find an element greater than or equal to the pivot.
Step 3: Decrement j until you find an element less than or equal to the pivot.
Step 4: If i is less than j, swap the elements at i and j.
Step 5: Repeat steps 2-4 until i and j cross each other.
Step 6: Swap the pivot element with the element at j. This places the pivot in its final position, dividing the array into two partitioned subarrays.
Step 7: Apply Quick Sort to the sub-arrays (Continue recursion until each sub-array becomes sorted)
Initial Array
We start with an unsorted array [10, 70, 40, 90, 50]. In Quick Sort, we select a 'pivot' element from the array, which we will use to divide the array into two parts. Elements less than the pivot go to the left, and elements greater than the pivot go to the right.
Step 1: Choosing a Pivot:
The first step in Quick Sort is to choose a pivot element. In this case we select 50 as our pivot element. The pivot can be chosen in different ways - either the first element, the last element, a random element, or the median among a few elements from the array.
Step 2: Partitioning:
We reorder the array so that all elements less than the pivot come before it and all elements greater than the pivot go after it. In the images, we can see that 70 and 40 are in place because they are less than the pivot, and we are moving 50 to the position just after the pivot because it is the next smallest element after the pivot.
Step 3: Sorting the Subarrays:
After partitioning, we have two subarrays around the pivot. We then apply the same Quick Sort process recursively to these subarrays. The subarray [10, 40] is already sorted because it contains all elements less than the pivot and only has two elements. For the subarray [90, 70, 50], we need to select a new pivot, partition this subarray, and continue the process.
Step 4: Final Sorted Array:
After sorting both subarrays and placing the pivot in its correct position, we combine the elements to form the sorted array [10, 40, 50, 70, 90]. Quick Sort doesn't literally combine arrays like Merge Sort; instead, the elements are sorted in place.
The process of selecting a pivot and partitioning the array is repeated recursively on the subarrays, and this recursion continues until all the subarrays are sorted.
Dry Run
| Step |
Array |
i |
j |
Pivot Element |
Subarrays |
| 1 |
[10, 70, 40, 90, 50] |
0 |
4 |
50 |
Full Array |
| 2 |
[10, 40, 90, 70, 50] |
1 |
3 |
50 |
Full Array |
| 3 |
[10, 40, 50, 70, 90] |
2 |
2 |
50 |
[10, 40] (50) [70, 90] |
| 4 |
[10, 40] (50) [70, 90] |
- |
- |
50 |
- |
| 5 |
[10, 40] |
0 |
1 |
40 |
[10] (40) |
| 6 |
[10, 40] |
1 |
0 |
40 |
- |
| 7 |
[10, 40) |
- |
- |
40 |
- |
| 8 |
[90, 70] |
0 |
1 |
90 |
(90)[70] |
| 9 |
[70, 90] |
1 |
0 |
90 |
- |
| 10 |
[70, 90] |
- |
- |
90 |
- |
Pseudo Code
Before we code, let's outline our strategy with pseudo-code:
function quickSort(array, low, high)
if low < high
pivotIndex = partition(array, low, high)
quickSort(array, low, pivotIndex - 1) // Before pivot
quickSort(array, pivotIndex + 1, high) // After pivot
Implementation in C
#include <stdio.h>
// Function to swap two elementsvoid swap(int* a, int* b) { int t = *a; *a = *b; *b = t; }
// Function to partition the array on the basis of pivotint 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); }
// Function to implement Quick Sortvoid quickSort(int arr[], int low, int high) { if (low < high) { /* pi is partitioning index, arr[pi] 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); } }
// A utility function to print array of size nvoid printArray(int arr[], int size) { for (int i = 0; i < size; i++) printf("%d ", arr[i]); printf("\n");}
int main() { int arr[] = {10, 7, 8, 9, 1, 5}; int n = sizeof(arr) / sizeof(arr[0]);
printf("Unsorted array: \n"); printArray(arr, n);
quickSort(arr, 0, n - 1);
printf("Sorted array: \n"); printArray(arr, n);
return 0; }
Output
Unsorted array:
10 7 8 9 1 5
Sorted array:
1 5 7 8 9 10
Time Complexity
The speed of an algorithm is often captured by its time complexity, which expresses the relationship between the input size and the time required to complete the task.
- Best and Average Case: In the best and average scenarios, where the pivot element is chosen to divide the array into proportionate halves consistently, the time complexity is O(n log n). This is because the array is halved with each pass (log n), and this operation is performed for each n element.
- Worst Case: The worst case occurs when the pivot selection results in one partition containing all but one of the elements, leading to O(n^2). This situation commonly happens when the pivot is the smallest or largest element in the array, as it would be in an already sorted or reverse-sorted array.
Space Complexity
Space complexity refers to the amount of memory space required by an algorithm in its life cycle.
- In-Place Sorting: Quick Sort is an in-place sorting algorithm. However, it requires space for the stack frames of the recursive calls. In the best case, this leads to a space complexity of O(log n), representing the height of the balanced partition tree.
- Worst Case: In the worst case, with unbalanced partitions, the space complexity can degrade to O(n), where n is the depth of the recursive call stack, one for each array element.
Real-World Problem
Problem Visualization: Imagine a busy airport with hundreds of passengers waiting to board their flights. The boarding process must be optimized to minimize passenger waiting time and ensure efficient boarding.
Task: Sort an unsorted array of passenger boarding pass numbers in ascending order to determine the boarding sequence.
Solution: Use Quick Sort to sort the boarding pass numbers efficiently.
#include <stdio.h>
// Function to swap two elementsvoid swap(int *a, int *b) { int temp = *a; *a = *b; *b = temp;}
// Function to partition the array around a pivotint partition(int arr[], int low, int high) { int pivot = arr[high]; // Choose the last element as pivot int i = (low - 1); // Index of the smaller element
// Rearrange elements around the pivot for (int j = low; j <= high - 1; j++) { if (arr[j] <= pivot) { i++; swap(&arr[i], &arr[j]); } } swap(&arr[i + 1], &arr[high]); // Place pivot at the right position return (i + 1); // Return the partitioning index}
// Function to implement Quick Sortvoid quickSort(int arr[], int low, int high) { if (low < high) { int pi = partition(arr, low, high); // Partitioning index
// Recursively sort elements before and after partition quickSort(arr, low, pi - 1); quickSort(arr, pi + 1, high); }}
int main() { int passengerNumbers[] = {35, 12, 87, 23, 61}; int n = sizeof(passengerNumbers) / sizeof(passengerNumbers[0]);
printf("Unsorted passenger numbers:\n"); for (int i = 0; i < n; i++) { printf("%d ", passengerNumbers[i]); }
quickSort(passengerNumbers, 0, n - 1); // Sort the array
printf("\nSorted boarding sequence:\n"); for (int i = 0; i < n; i++) { printf("%d ", passengerNumbers[i]); }
return 0;}
Output
Unsorted passenger numbers:
35 12 87 23 61
Sorted boarding sequence:
12 23 35 61 87
Advantages of Quick Sort
- Efficient average-case complexity: Quick Sort has an average-case time complexity of O(n log n), making it efficient for large datasets.
- In-place sorting: It doesn't require additional memory beyond the existing array, reducing space complexity.
- Parallelizable: The algorithm can be easily parallelized across multiple processors or cores, further improving its speed.
- Cache-friendly: Quick Sort works well with modern processor caches due to its locality of reference, enhancing performance.
- No recursion depth limit: Unlike some other recursive algorithms, Quick Sort doesn't have a bound on its recursion depth, making it suitable for very large datasets.
Disadvantages of Quick Sort
- Worst-case complexity: In the worst-case scenario, Quick Sort's time complexity can deteriorate to O(n^2), which can occur when the chosen pivot elements are poorly selected.
- Unstable sorting: Quick Sort does not preserve the relative order of equal elements, which might be important for specific applications.
- High constant factor: Compared to other sorting algorithms like Merge Sort, Quick Sort might have a higher constant factor in its time complexity, leading to slightly slower performance in some cases.
- Not ideal for small datasets: For small datasets, the overhead of partitioning and recursion might outweigh the benefits, making simpler algorithms like Bubble Sort or Insertion Sort more efficient.
Contributed By: Manali Bhave
This is a collection of insightful articles from domain experts in the fields of Cloud Computing, DevOps, AWS, Data Science, Machine Learning, AI, and Natural Language Processing. The range of topics caters to upski... Read Full Bio
Top Picks & New Arrivals
