Quick sort is a highly efficient sorting algorithm that follows the divide-and-conquer approach. 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.
Various Sorting Algorithm
- Bubble sort
- Modified Bubble Sort
- Selection sort
- Insertion sort
- Quick sort
- Merge sort
- Heap sort
Quick sort
0 1 2 6 7 8
58 62 91 43 29 37 88 72 16
16 37 29 43 58 91 88 72 62
The main steps of the quick sort algorithm are as follows:
- Choose a pivot element from the array. The pivot can be selected in various ways, such as the first element, last element, or a random element.
- Partition the array into two sub-arrays: elements less than the pivot and elements greater than the pivot.
- Recursively apply the quick sort algorithm to the two sub-arrays.
- Combine the sorted sub-arrays to produce the final sorted array.
Algorithm
The quick sort algorithm is a widely used sorting algorithm that employs the divide-and-conquer approach. The steps of the quick sort algorithm are as follows:
- Choose a Pivot: Choose a pivot element from the array. The choice of the pivot can vary, and it can be the first element, the last element, the middle element, or a randomly selected element from the array.
- Partitioning: Reorder the array so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it. After this partitioning, the pivot is in its final position. This is called the partition operation.
- Recursively Sort Sub-Arrays: Apply the quick sort algorithm recursively to the sub-arrays on the left and right of the pivot.
Here is the algorithm of the quick sort:
quickSort(arr[], low, high)
if (low < high)
{
arr[pi] is
now at right place
pi = partition(arr, low, high);
// Recursively sort elements before
partition and after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
partition(arr[], low, high)
// Select a pivot element
pivot = arr[high];
i = low - 1;
// Index of smaller element
for (j = low; j < high; j++)
{
// If current element
is smaller than the pivot
if (arr[j] < pivot)
{
i++;
// Swap arr[i] and arr[j]
swap arr[i] and arr[j];
}
}
// Swap arr[i + 1]
and arr[high] (or the pivot)
return i + 1;
Working of Quick Sort Algorithm
Certainly! Let’s go through the working of the Quick Sort algorithm step by step with an example and corresponding diagrams. Consider the following unsorted array:
7,2,1,6,8,5,3,4
- Choose a Pivot: Let’s choose the first element,
7, as the pivot. Partitioning: Rearrange the array such that all elements less than the pivot come before it, and all elements greater than the pivot come after it. After the first partition, the pivot
7is in its final position.4,2,1,6,5,3,∗∗7∗∗,8
Recursively Sort Sub-Arrays: Apply the quick sort algorithm to the sub-arrays on the left and right of the pivot.
- For the left sub-array: 4,2,1,6,5,3
- For the right sub-array: 8
Partitioning (Left Sub-Array): Choose a pivot (let’s choose the first element,
4) and rearrange the elements around it.3,2,1,∗∗4∗∗,5,6
Recursively Sort Sub-Arrays (Left Sub-Array): Apply the quick sort algorithm to the sub-arrays on the left and right of the pivot.
- For the left sub-array: 3,2,1
- For the right sub-array: 5,6
- Continue this process until the entire array is sorted.
Initial Array:
[7, 2, 1, 6, 8, 5, 3, 4]
Partitioning Step 1:
[4, 2, 1, 6, 5, 3, 7, 8]
Partitioning Step 2:
[3, 2, 1, 4, 5, 6, 7, 8]
Final Sorted Array:
[1, 2, 3, 4, 5, 6, 7, 8]
Quicksort complexity
The time complexity of heap sort in different cases along with its space complexity is as follows:
| Case | Time Complexity |
|---|---|
| Best Case | O(n*logn)) |
| Average Case | O(n*logn) |
| Worst Case | O(n2) |
Best Case Time Complexity: O(n log n)
- The best case occurs when the pivot divides the array into two subarrays of equal size. In this scenario, each partitioning step divides the array into two nearly equal parts, leading to a balanced division and a time complexity of O(n log n).
- Average Case Time Complexity: O(n log n)
- On average, Quicksort performs efficiently, dividing the array into subarrays of nearly equal sizes. The average time complexity is O(n log n), making Quicksort one of the fastest sorting algorithms for most cases.
- Worst Case Time Complexity: O(n^2)
- The worst case occurs when the pivot is chosen poorly, causing uneven partitioning, such as when the pivot is the smallest or largest element in the array. This can lead to one subarray with n-1 elements and the other with 0 elements, resulting in a time complexity of O(n^2).
Implementation of quicksort
Certainly! Below is a simple implementation of the Quicksort algorithm in Java:
import java.util.Arrays;
public class QuickSort {
public 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);
}
}
public int partition(int[] arr,
int low, int high)
{
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
public static void main(String[] args) {
int[] arr = {12, 11, 13, 5, 6, 7};
QuickSort ob = new QuickSort();
System.out.println("Original array: "
+ Arrays.toString(arr));
ob.quickSort(arr, 0, arr.length - 1);
System.out.println("Sorted array: "
+ Arrays.toString(arr));
}
}
