Quick Sort is a highly efficient divide-and-conquer sorting algorithm. It works by selecting a “pivot” element, partitioning the array such that elements smaller than the pivot are placed to its left and elements larger are placed to its right, and then recursively sorting the subarrays.
How Quick Sort Works?
- Partitioning:
- Select a pivot element from the array.
- Reorganize the array such that:
- All elements smaller than the pivot are on the left.
- All elements larger than the pivot are on the right.
- The pivot element is now in its correct position.
- Recursive Sorting:
- Recursively apply the above steps to the subarrays on the left and right of the pivot.
Steps of the Quick Sort Algorithm:
Input Array: [10, 80, 30, 90, 40, 50, 70]
- Choose Pivot: Select the last element as the pivot (e.g.,
70
). - Partitioning: Rearrange the array:
- Elements <
70
on the left:[10, 30, 40, 50]
- Pivot
70
:[70]
- Elements >
70
on the right:[80, 90]
. - The result after partition:
[10, 30, 40, 50, 70, 80, 90]
.
- Elements <
- Recursive Steps:
- Apply Quick Sort to
[10, 30, 40, 50]
and[80, 90]
.
- Apply Quick Sort to
- Base Case: Stop recursion when subarrays contain a single element.
Quick Sort Program in Java
package com.javacodepoint.sort;
public class QuickSort {
// Partition method to rearrange the array
public static int partition(int[] array, int low, int high) {
int pivot = array[high]; // Pivot is the last element
int i = low - 1; // Index of smaller element
for (int j = low; j < high; j++) {
// If current element is smaller than or equal to pivot
if (array[j] <= pivot) {
i++;
// Swap array[i] and array[j]
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
// Swap the pivot element with the element at i + 1
int temp = array[i + 1];
array[i + 1] = array[high];
array[high] = temp;
return i + 1; // Return the pivot index
}
// Recursive Quick Sort method
public static void quickSort(int[] array, int low, int high) {
if (low < high) {
// Partition the array and get the pivot index
int pivotIndex = partition(array, low, high);
// Recursively sort the left and right subarrays
quickSort(array, low, pivotIndex - 1);
quickSort(array, pivotIndex + 1, high);
}
}
public static void main(String[] args) {
int[] numbers = { 10, 80, 30, 90, 40, 50, 70 };
System.out.println("Original Array:");
for (int num : numbers) {
System.out.print(num + " ");
}
// Sort the array using Quick Sort
quickSort(numbers, 0, numbers.length - 1);
System.out.println("\nSorted Array:");
for (int num : numbers) {
System.out.print(num + " ");
}
}
}
OUTPUT:
Original Array:
10 80 30 90 40 50 70
Sorted Array:
10 30 40 50 70 80 90
Explanation of Key Steps:
- Partitioning:
- Rearranges the array such that the pivot is in its correct position, and smaller/larger elements are divided around it.
- Recursive Calls:
- Applies Quick Sort to the left and right subarrays of the pivot.
- Base Case:
- Stops recursion when the subarray size is 1 or 0 (already sorted).
Time Complexity
- Best Case: O(n log n) (Balanced partitions).
- Average Case: O(n log n) (Random partitions).
- Worst Case: O(n^2) (Unbalanced partitions, e.g., sorted array).
Space Complexity
- In-place Algorithm: Uses O(log n) space for recursion stack.
Also Read: Selection Sort | Insertion Sort | Bubble Sort | Merge Sort