Sorting algorithms play a crucial role in computer science, helping us organize and manipulate data efficiently. One such powerful and widely used sorting technique is Quick Sort. In this blog, we’ll explore the Quick Sort algorithm, understand its mechanism, and provide a C implementation.
What is Quick Sort?
Quick Sort is a divide-and-conquer algorithm that works by selecting a "pivot" element from the array and partitioning the other elements into two sub-arrays: those less than the pivot and those greater than the pivot. The process is then applied recursively to the sub-arrays.
Why Use Quick Sort?
Efficiency: Quick Sort is one of the fastest sorting algorithms in practical use.
Flexibility: It works well for both small and large datasets.
In-Place Sorting: It doesn’t require additional memory compared to other sorting methods like Merge Sort.
How Does Quick Sort Work?
Steps of the Algorithm:
Choose a Pivot: Select an element as the pivot. This can be the first element, the last element, or any random element in the array.
Partition the Array: Rearrange the elements so that all elements less than the pivot are to its left, and all elements greater are to its right.
Recursively Apply: Apply the same process to the left and right sub-arrays until the base case (a single-element array) is reached.
#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 array[], int low, int high) {
int pivot = array[high]; // Choosing the last element as the pivot
int i = (low - 1); // Index of smaller element
for (int j = low; j < high; j++) {
// If the current element is smaller than or equal to the pivot
if (array[j] <= pivot) {
i++;
swap(&array[i], &array[j]);
}
}
swap(&array[i + 1], &array[high]);
return (i + 1);
}
// Quick Sort function
void quickSort(int array[], int low, int high) {
if (low < high) {
// Partition the array
int pi = partition(array, low, high);
// Recursively sort the sub-arrays
quickSort(array, low, pi - 1);
quickSort(array, pi + 1, high);
}
}
// Function to print an array
void printArray(int array[], int size) {
for (int i = 0; i < size; i++) {
printf("%d ", array[i]);
}
printf("\n");
}
int main() {
int data[] = {8, 7, 6, 1, 0, 9, 2};
int n = sizeof(data) / sizeof(data[0]);
printf("Unsorted array: \n");
printArray(data, n);
quickSort(data, 0, n - 1);
printf("Sorted array in ascending order: \n");
printArray(data, n);
return 0;
}
dtytry
Explanation of the Code
Partition Function:
It selects the last element as the pivot.
Rearranges elements around the pivot so that smaller elements are on the left and larger ones are on the right.
Returns the partition index, which is the final position of the pivot.
Quick Sort Function:
- Recursively applies Quick Sort to the sub-arrays before and after the pivot.
Main Function:
- Initializes the array and prints it before and after sorting.
Time and Space Complexity
Time Complexity:
Best Case: when the pivot divides the array into two nearly equal halves.
Worst Case: when the pivot divides the array into extremely unbalanced parts (e.g., when the array is already sorted).
Average Case: .
Space Complexity:
- In-Place Algorithm: Requires space for recursion stack.
Advantages of Quick Sort
Faster than other algorithms like Merge Sort for smaller datasets.
Requires less memory as it sorts in place.
Disadvantages of Quick Sort
Performance degrades to in the worst-case scenario.
Not a stable sorting algorithm (relative order of equal elements may change).
Quick Sort is an elegant and efficient sorting algorithm that strikes a balance between performance and simplicity. Its practical utility and straightforward implementation make it a valuable tool for software developers.