Quicksort: A Comprehensive Guide
Quicksort is an efficient, in-place sorting algorithm that uses a divide-and-conquer strategy. It is widely used and, on average, performs better than many other sorting algorithms. Quicksort has an average time complexity of O(n log n) and is known for its efficiency and relatively simple implementation.
How Quicksort Works
- Choose a 'pivot' element from the array.
- Partition the other elements into two sub-arrays, according to whether they are less than or greater than the pivot.
- Recursively apply the above steps to the sub-arrays.
The base case of the recursion is arrays of size zero or one, which are always sorted.
Implementation in Java
Here's a basic implementation of Quicksort in Java:
public class Quicksort {
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pivotIndex = partition(arr, low, high);
quickSort(arr, low, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, high);
}
}
private static 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++;
swap(arr, i, j);
}
}
swap(arr, i + 1, high);
return i + 1;
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String[] args) {
int[] arr = {10, 7, 8, 9, 1, 5};
quickSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
}
Implementation in C++
Here's the same implementation in C++:
#include <iostream>
#include <vector>
class Quicksort {
public:
static void quickSort(std::vector<int>& arr, int low, int high) {
if (low < high) {
int pivotIndex = partition(arr, low, high);
quickSort(arr, low, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, high);
}
}
private:
static int partition(std::vector<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++;
swap(arr, i, j);
}
}
swap(arr, i + 1, high);
return i + 1;
}
static void swap(std::vector<int>& arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
};
int main() {
std::vector<int> arr = {10, 7, 8, 9, 1, 5};
Quicksort::quickSort(arr, 0, arr.size() - 1);
for (int num : arr) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
Popular Interview Problems
Let's look at some popular interview problems related to Quicksort and their solutions in both Java and C++.
1. Kth Largest Element in an Array
Problem: Find the kth largest element in an unsorted array.
Java Solution:
class Solution {
public int findKthLargest(int[] nums, int k) {
return quickSelect(nums, 0, nums.length - 1, nums.length - k);
}
private int quickSelect(int[] nums, int low, int high, int k) {
int pivot = partition(nums, low, high);
if (pivot == k) {
return nums[k];
} else if (pivot < k) {
return quickSelect(nums, pivot + 1, high, k);
} else {
return quickSelect(nums, low, pivot - 1, k);
}
}
private int partition(int[] nums, int low, int high) {
int pivot = nums[high];
int i = low;
for (int j = low; j < high; j++) {
if (nums[j] <= pivot) {
swap(nums, i, j);
i++;
}
}
swap(nums, i, high);
return i;
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
C++ Solution:
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
return quickSelect(nums, 0, nums.size() - 1, nums.size() - k);
}
private:
int quickSelect(vector<int>& nums, int low, int high, int k) {
int pivot = partition(nums, low, high);
if (pivot == k) {
return nums[k];
} else if (pivot < k) {
return quickSelect(nums, pivot + 1, high, k);
} else {
return quickSelect(nums, low, pivot - 1, k);
}
}
int partition(vector<int>& nums, int low, int high) {
int pivot = nums[high];
int i = low;
for (int j = low; j < high; j++) {
if (nums[j] <= pivot) {
swap(nums[i], nums[j]);
i++;
}
}
swap(nums[i], nums[high]);
return i;
}
};
Explanation: This problem uses a variation of Quicksort called Quickselect. Instead of recursing into both sides, we only recurse into one side - the side with the kth largest element. This reduces the average time complexity to O(n).
2. Sort Colors (Dutch National Flag Problem)
Problem: Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue.
Java Solution:
class Solution {
public void sortColors(int[] nums) {
int low = 0, mid = 0, high = nums.length - 1;
while (mid <= high) {
switch (nums[mid]) {
case 0: // red
swap(nums, low++, mid++);
break;
case 1: // white
mid++;
break;
case 2: // blue
swap(nums, mid, high--);
break;
}
}
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
C++ Solution:
class Solution {
public:
void sortColors(vector<int>& nums) {
int low = 0, mid = 0, high = nums.size() - 1;
while (mid <= high) {
switch (nums[mid]) {
case 0: // red
swap(nums[low++], nums[mid++]);
break;
case 1: // white
mid++;
break;
case 2: // blue
swap(nums[mid], nums[high--]);
break;
}
}
}
};
Explanation: This problem, also known as the Dutch National Flag problem, can be solved using a variation of the partition method from Quicksort. We use three pointers: low, mid, and high. We move all 0s (red) before low, all 2s (blue) after high, and all 1s (white) between low and high.
These problems demonstrate how the concepts from Quicksort can be applied to solve more complex sorting and selection problems efficiently. Understanding these variations is crucial for mastering sorting algorithms and performing well in coding interviews.