Quick Sort
Quick sort is a popular sorting algorithm that uses a divide-and-conquer strategy to efficiently sort an array or list. It works 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 recursively sorted.
Here's a detailed algorithm for the Quick Sort algorithm:
Algorithm: Quick Sort
1.Choose a pivot element from the array. This can be done in various ways, such as selecting the first element, the last element, or a random element. The choice of the pivot can affect the algorithm's performance.
2,Partition the array into two sub-arrays:
Elements less than the pivot (left sub-array).
Elements greater than the pivot (right sub-array).
3.Recursively apply the Quick Sort algorithm to the left and right sub-arrays.
4.Combine the sorted left sub-array, pivot, and sorted right sub-array to obtain the final sorted array.
Example:
Let's walk through a step-by-step example of the Quick Sort algorithm on an unsorted list of integers. For this example, we'll use the following list:
[4, 7, 2, 1, 5, 9, 8, 6]
Step 1: Choose a Pivot We'll start by choosing a pivot element. For this example, we'll choose the first element, which is 4.
Step 2: Partition the List Now, we'll partition the list into two sub-arrays: elements less than the pivot and elements greater than the pivot.
Lesser elements (left sub-array): [2, 1]
Pivot: 4
Greater elements (right sub-array): [7, 5, 9, 8, 6]
Pivot: 4
Greater elements (right sub-array): [7, 5, 9, 8, 6]
The pivot is now in its final sorted position because all elements in the left sub-array are less than 4, and all elements in the right sub-array are greater than 4.
Step 3: Recursion
Next, we recursively apply the Quick Sort algorithm to the left and right sub-arrays.
Left sub-array [2, 1]:
Choose pivot: 2
Partitioning:
Partitioning:
Lesser elements: [1]
Pivot: 2
Greater elements: [] (empty)
Pivot: 2
Greater elements: [] (empty)
Since both sub-arrays have at most one element, they are considered sorted.
Choose pivot: 7
Partitioning:Lesser elements: [5, 6]
Pivot: 7
Greater elements: [9, 8]
Partitioning:Lesser elements: [5, 6]
Pivot: 7
Greater elements: [9, 8]
Now, recursively apply Quick Sort to the left and right sub-arrays of the right sub-array.
Left sub-array [5, 6]:
Choose pivot: 5
Partitioning:Lesser elements: [5]
Pivot: 6
Greater elements: []
Both sub-arrays are sorted.Partitioning:Lesser elements: [5]
Pivot: 6
Greater elements: []
Choose pivot: 9
Partitioning:Lesser elements: [8]
Pivot: 9
Greater elements: []
Both sub-arrays are sorted.
Partitioning:Lesser elements: [8]
Pivot: 9
Greater elements: []
Both sub-arrays are sorted.
Step 4: Combine Sorted Sub-Arrays Now that all sub-arrays are sorted, we can combine them to get the final sorted array.
Combine:Left sub-array: [1, 2]
Pivot: 4
Right sub-array: [5, 6, 7, 8, 9]
The final sorted array is [1, 2, 4, 5, 6, 7, 8, 9].
That's the Quick Sort algorithm in action, sorting the given list in ascending order. It divides the problem into smaller sub-problems and combines the results to achieve a sorted array.
Pseudo Code
QuickSort(arr, low, high):
if low < high:
# Partition the array into two sub-arrays
pivotIndex = Partition(arr, low, high)
# Recursively sort the sub-arrays
QuickSort(arr, low, pivotIndex - 1)
QuickSort(arr, pivotIndex + 1, high)
Partition(arr, low, high):
pivot = arr[high] # Choose the pivot element (typically the last element)
i = low - 1 # Index of the smaller element
for j from low to high - 1:
if arr[j] <= pivot:
i = i + 1
Swap(arr[i], arr[j])
Swap(arr[i + 1], arr[high]) # Place the pivot element in its correct position
return i + 1
This pseudocode defines the QuickSort function, which takes an array arr, a low index low, and a high index high as input parameters. It first checks if the sub-array has more than one element (i.e., low < high). If so, it proceeds to partition the array using the Partition function and then recursively sorts the left and right sub-arrays.
The Partition function chooses a pivot element (in this case, the last element), and it rearranges the elements in the sub-array such that all elements less than or equal to the pivot are on the left side, and all elements greater than the pivot are on the right side. It returns the index of the pivot element after partitioning.
Time Complexity:
Average Case: Quick Sort has an average-case time complexity of O(n log n), where "n" is the number of elements in the array. This makes Quick Sort one of the most efficient sorting algorithms on average.
Worst Case: In the worst-case scenario, Quick Sort can have a time complexity of O(n^2). This happens when the pivot selection strategy consistently results in poorly balanced partitions. However, this worst-case scenario is rare in practice, especially when using a good pivot selection strategy.
Best Case: The best-case time complexity of Quick Sort is also O(n log n). This occurs when the pivot choices lead to well-balanced partitions, resulting in the most efficient performance.
Space Complexity:
Quick Sort is an in-place sorting algorithm, which means it doesn't require additional memory proportional to the size of the input data. It uses a small amount of extra memory for recursive function calls and maintaining the stack, but this space usage is typically O(log n) in the average and best cases, where "n" is the number of elements in the array.
In the worst case (rarely encountered in practice), where the recursion depth is equal to the number of elements in the array, the space complexity can be O(n) due to the recursive function call stack. However, many programming languages and compilers optimize tail recursion, reducing the space complexity to O(log n) in practice.
In summary, Quick Sort is highly efficient on average and is widely used in practice due to its O(n log n) average-case time complexity. Its space complexity is typically O(log n) due to the recursion stack, making it suitable for sorting large datasets with limited additional memory requirements.
Let’s go through a few key benefits of using Quicksort:
It works rapidly and effectively.
It has the best time complexity when compared to other sorting algorithms.
Limitations of Quicksort
It has the best time complexity when compared to other sorting algorithms.
Quick sort has a space complexity of O(logn), making it an excellent choice for situations when space is limited.
Despite being the fastest algorithm, QuickSort has a few drawbacks. Let’s have a look at some of the drawbacks of Quicksort.
This sorting technique is considered unstable since it does not maintain the key-value pairs initial order.
When the pivot element is the largest or smallest, or when all of the components have the same size. The performance of the quicksort is significantly impacted by these worst-case scenarios.
It’s difficult to implement since it’s a recursive process, especially if recursion isn’t available.
C Program- Quick Sort
/*******************************************************************************/
#include <stdio.h>
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
int partition(int arr[], int first, int last) {
int pivot = arr[last]; // Choose the pivot element (last element)
int i = first - 1; // Index of the smaller element
for (int j = first; j < last; j++) {
if (arr[j] <= pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[last]); // Place the pivot element in its correct position
return i + 1;
}
void quickSort(int arr[], int first, int last) {
if (first < last) {
int pivotIndex = partition(arr, first, last);
// Recursively sort the left and right sub-arrays
quickSort(arr, first, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, last);
}
}
int main() {
int arr[50],n,i;
printf("Enter size of the array: ");
scanf("%d",&n);
printf("Enter %d elements: ",n);
for(i=0;i<n;i++)
scanf("%d",&arr[i]);
quickSort(arr, 0, n - 1);
printf("\nSorted array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
Comments
Post a Comment