➤ How to Code a Game
➤ Array Programs in Java
➤ Java Inline Thread Creation
➤ Java Custom Exception
➤ Hibernate vs JDBC
➤ Object Relational Mapping
➤ Check Oracle DB Size
➤ Check Oracle DB Version
➤ Generation of Computers
➤ XML Pros & Cons
➤ Git Analytics & Its Uses
➤ Top Skills for Cloud Professional
➤ How to Hire Best Candidates
➤ Scrum Master Roles & Work
➤ CyberSecurity in Python
➤ Protect from Cyber-Attack
➤ Solve App Development Challenges
➤ Top Chrome Extensions for Twitch Users
➤ Mistakes That Can Ruin Your Test Metric Program
Sorting DSA | We will see how the predefined method for sorting is implemented in Java. We will discuss the following algorithms:- Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, Heap Sort, Cycle Sort, and Quick Sort.
Table of Contents
- Sorting in Java
- a. Bubble Sort Algorithm
- b. Selection Sort Algorithm
- c. Insertion Sort Algorithm
- 1. Merge Two Sorted Arrays
- Merge Sorted Array Without Extra Space
- d-i. Merge Function of Merge Sort
- d-ii. Merge Sort Algorithm
- 2. Intersection of Two Sorted Arrays
- 3. Common in 3 Sorted Arrays
- 4. Union of Two-Sorted Arrays
- 5. Count Inversions in an Array
- 6. Partition of a Given Array
- e. Quick Sort Algorithm
- 7. Quick Select Algorithm (Kth Smallest in the Array)
- 8. Chocolate Distribution Problem
- 9. Sort an Array with Two Types
- 10. Dutch National Flag Algorithm (Sort an Array with Three Types)
- 11. Minimum Difference in an Array
- 12. Merge Overlapping Intervals
- 13. Meeting Maximum Guests
- f. Cycle Sort Algorithm
- g. Heap Sort Algorithm
- h. Counting Sort Algorithm
- i. Radix Sort Algorithm
- j. Bucket Sort Algorithm
- Overview of the Sorting Algorithm
Sorting in Java
Java contains the pre-defined sort() method in the following two classes:-
- Arrays.sort():- It can be used for both arrays of primitives and objects.
- Collections.sort():- It can be used for lists (ArrayList, LinkedList, etc).
Stability in Sorting
Consider a list of students, each with a branch code and a student:- {CS, 101}, {ECE, 102}, {CS, 104}, {CS, 105}, {ECE, 107}.
After performing a stable sort based on the branch code, the list would be:- {CS, 101}, {CS, 104}, {CS, 105}, {ECE, 102}, {ECE, 107}.
Stable sorting according to branch means it sorts based on branch, but when two students have the same branch, stable sorting maintains their insertion order. Stable sorting maintains the relative order of records with equal keys. In this example, students within the same branch retain their original insertion order.
Stable sorting is not necessary for primitive arrays. Consequently, Java utilizes the Dual-Pivot Quicksort algorithm for sorting primitives. However, stable sorting is essential for objects, where Java employs a MergeSort adaptation of Timsort to ensure stability.
- Examples of Stable Sorting Algorithm are Bubble Sort, Insertion Sort, Merge Sort, etc.
- Examples of Unstable Sorting Algorithm are Selection Sort, Quick Sort, Heap Sort, etc.
Arrays.sort() Example
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
int[] arr = { 50, 25, 30, 55, 15 };
char[] charArr = { 'p', 'r', 'o', 'g', 'r', 'a', 'm' };
Arrays.sort(arr);
Arrays.sort(charArr);
System.out.println(Arrays.toString(arr));
System.out.println(Arrays.toString(charArr));
}
}Output:-
[15, 25, 30, 50, 55]
[ a, g, m, o, p, r, r ]
Arrays.sort() for primitive types doesn’t offer custom comparator therefore we can sort them either in ascending order or descending order. Java does not provide a direct method to sort primitive arrays in descending order. However, we can achieve this by sorting in ascending order and then reversing the array.
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
int[] arr = { 50, 25, 30, 55, 15 };
Arrays.sort(arr);
// reverse the array
for (int i = 0; i < arr.length / 2; i++) {
int temp = arr[i];
arr[i] = arr[arr.length - 1 - i];
arr[arr.length - 1 - i] = temp;
}
System.out.println(Arrays.toString(arr));
}
}If it is an array/list of wrapper classes then we can use the predefined Collections.reverseOrder() method along with the sort() method to sort in descending order.
import java.util.Arrays;
import java.util.Collections;
public class Test {
public static void main(String[] args) {
Integer[] arr = { 50, 25, 30, 55, 15 };
Arrays.sort(arr, Collections.reverseOrder());
System.out.println(Arrays.toString(arr));
}
}Arrays.sort() has one more version where we can sort sub-array of an array:- Arrays.sort(array, int fromIndexInclusive, int toIndexExclusive). The start index is inclusive, and the end index is exclusive.
int[] arr = { 50, 25, 30, 55, 15 };
Arrays.sort(arr, 1, 5);
System.out.println(Arrays.toString(arr)); // [50, 15, 25, 30, 55]For objects we can pass Comparator, hence we can provide a custom way of sorting.
Write a program to sort an array of Integers so that all even numbers appear first, and then all odd numbers appear. Problem: 905
import java.util.Arrays;
import java.util.Comparator;
public class Test {
public static void main(String[] args) {
Integer[] arr = { 50, 25, 30, 55, 15 };
Arrays.sort(arr, new Comparator<Integer>() {
@Override
public int compare(Integer a, Integer b) {
return a % 2 - b % 2;
}
});
System.out.println(Arrays.toString(arr)); // [50, 30, 25, 55, 15]
}
}Comparator Logic:-
- If both integers are even or both are odd, the comparator returns 0 (no change in order).
- If a is even and b is odd, a % 2 – b % 2 results in a negative number, and a will be placed before b.
- If a is odd and b is even, a % 2 – b % 2 results in a positive number, and a will be placed after b.
However, the LeetCode problem 905 uses primitives and we can’t use comparators with primitives we have boxed and unboxed which increases the time complexity unnecessarily. In that case, using a two-pointer approach is better and can be solved as moving all zeros to the end.
class Solution {
public int[] sortArrayByParity(int[] nums) {
int even = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] % 2 == 0) {
if (even != i) {
int temp = nums[even];
nums[even] = nums[i];
nums[i] = temp;
}
even++;
}
}
return nums;
}
}Collections.sort()
Collections.sort() is used to sort the list. All the collection classes only work with objects but not with the primitives. To work with primitives, we must use wrapper classes.
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class Test {
public static void main(String[] args) {
List<Integer> list = new ArrayList<>();
list.add(100);
list.add(9);
list.add(20);
list.add(18);
Collections.sort(list);
System.out.println(list); // [9, 18, 20, 100]
// to sort in descending order
Collections.sort(list, Collections.reverseOrder());
System.out.println(list); // [100, 20, 18, 9]
}
}Like an array, we can’t sort sublists. The collections class does not contain a method to sort sublists.
a. Bubble Sort Algorithm
Bubble Sort is one of the simplest and most intuitive sorting algorithms. It works by repeatedly swapping adjacent elements if they are in the wrong order. The process continues until no swaps are needed, indicating that the array is sorted.
We perform n passes. In the 1st pass, we move the largest element to the end, in the 2nd pass we move the 2nd largest element at the end-1 index, and so on.
BubbleSort(A){
for i = 0 to n - 1 {
for j = 0 to n - i - 1{
if A[j] > A[j + 1] {
swap(A[j], A[j + 1]);
}
}
}
}Steps:-
- Compare each pair of adjacent elements.
- Swap them if they are in the wrong order.
- Repeat the process for each pair of adjacent elements, “bubbling” the largest unsorted element to its correct position.
- Continue the passes through the list until no swaps are required.
There will be a total of n-1 passes.
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
int[] arr = { 10, 8, 20, 5 };
bubbleSort(arr);
System.out.println(Arrays.toString(arr));
}
private static void bubbleSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - 1; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
}
}
}
}
private static void swap(int[] arr, int j, int i) {
int temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
}
}It can be optimized as follows:-
- Instead of iterating till n-1 every time, traverse only till n-1-i because in ith iteration the last “i” elements are sorted.
- Early Termination: If no swaps are made during a pass (i.e., the array is already sorted), the
swappedflag remains false and breaks the loop, thus avoiding unnecessary iterations.
// optimized bubble sort
private static void bubbleSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
boolean swapped = false;
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
swapped = true;
}
}
if (!swapped) {
break;
}
}
}- Time Complexity for Best Case: O(n) (when the array is already sorted)
- Time Complexity for Average and Worst Case: O(n^2) (due to nested loops)
- Stability:- Bubble sort is stable and in place (it doesn’t use an extra array).
b. Selection Sort Algorithm
Selection Sort is a simple, intuitive sorting algorithm. It works by repeatedly finding the minimum element from the unsorted part of the array and swapping it with the first unsorted element, thus growing the sorted portion of the array one element at a time.
- It takes O(n^2) times in all cases.
- It uses less memory writes compared to Quick Sort, Merge Sort, Insertion Sort, etc. But Cycle Sort is optimal in terms of memory writes.
- It provides the basic idea for Heap Sort. Heap Sort uses heap data structure to apply the selection sorting technique.
- It is not stable.
- It is in place (doesn’t use an extra array).
First, let us see it through using another array. The idea is to create a new array. Find the smallest element, place it in the first index of the new array, and put INFINITE in that position of the original array. At last copy everything from the new array to the original array. Example:-
At start: Array = {10, 5, 7, 20, 2, 18}; New Array = {0, 0, 0, 0, 0, 0}.
- In 1st iteration, min = 2. Array = {10, 5, 7, 20, INF, 18}, Array = {2, 0, 0, 0, 0, 0}
- In 2nd iteration, min = 5. Array = {10, INF, 7, 20, INF, 18}, Array = {2, 5, 0, 0, 0, 0};
- In 3rd iteration, min = 7. Array = {10, INF, INF, 20, INF, 18}, Array = {2, 5, 7, 0, 0, 0};
- In 4th iteration, min = 10. Array = {INF, INF, INF, 20, INF, 18}, Array = {2, 5, 7, 10, 0, 0};
- In 5th iteration, min = 18. Array = {INF, INF, INF, 20, INF, INF}, Array = {2, 5, 7, 10, 18, 0};
- In 5th iteration, min = 20. Array = {INF, INF, INF, INF, INF, INF}, Array = {2, 5, 7, 10, 18, 20};
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
int[] arr = { 10, 8, 20, 5 };
selectionSort(arr);
System.out.println(Arrays.toString(arr));
}
private static void selectionSort(int[] arr) {
int[] temp = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
int min_ind = 0;
for (int j = 1; j < arr.length; j++) {
if (arr[j] < arr[min_ind]) {
min_ind = j;
}
}
temp[i] = arr[min_ind];
arr[min_ind] = Integer.MAX_VALUE;
}
// copy array
for (int i = 0; i < arr.length; i++) {
arr[i] = temp[i];
}
}
}In the above program, we have an extra array for better understanding purposes. However, as per the selection sort algorithm, it should be in-place. Steps:-
- Find the Minimum: Traverse the unsorted portion of the array to find the smallest element.
- Swap: Swap the smallest element found with the first element of the unsorted portion.
- Repeat: Move the boundary between the sorted and unsorted portions of one element to the right, and repeat until the entire array is sorted.
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
int[] arr = { 10, 8, 20, 5 };
selectionSort(arr);
System.out.println(Arrays.toString(arr));
}
private static void selectionSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// swap
if (minIndex != i) {
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
}
}Time Complexity: Best, Average, and Worst Case: O(n^2) (because of the nested loops).
Selection sort is not stable because it may change the order when two objects have the same value.
c. Insertion Sort Algorithm
Insertion Sort is a simple and efficient sorting algorithm that builds the final sorted array one element at a time. It’s much like sorting playing cards in your hands.
- Worst case time complexity O(n^2), when the input array is reverse sorted.
- Best case time complexity O(n), when the input array is already sorted.
- Best used in practice for small arrays (TimSort and IntraSort).
- It is in place and stable
Steps:-
- Start: Begin with the first element. Consider it as sorted.
- Insert: Pick the next element and compare it with the elements in the sorted portion.
- Shift: Move all elements in the sorted portion that are greater than the picked element one position to the right.
- Place: Insert the picked element into its correct position.
- Repeat: Repeat steps 2-4 until all elements are sorted.
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
int[] arr = { 10, 8, 20, 5 };
insertionSort(arr);
System.out.println(Arrays.toString(arr));
}
private static void insertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
}The arr[j] > key ensures that the resultant array will be stable.
Time Complexity:
- Best Case: O(n) (when the array is already sorted)
- Average and Worst Case: O(n^2) (due to nested loops)
1. Merge Two Sorted Arrays
Array1 = {10, 15, 20}; Array2 = {5, 6, 6, 15}
Resultant Array = {5, 6, 6, 10, 15, 15, 20}
Array1 = {1, 1, 2}; Array2 = {3}
Resultant Array = {1, 1, 2, 3}
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
int[] arr1 = { 10, 15, 20 };
int[] arr2 = { 5, 6, 6, 15 };
int[] resultantArr = mergeSortedArray(arr1, arr2);
System.out.println(Arrays.toString(resultantArr));
}
private static int[] mergeSortedArray(int[] left, int[] right) {
int n1 = left.length, n2 = right.length, i = 0, j = 0, k = 0;
int[] temp = new int[n1 + n2];
while (i < n1 && j < n2) {
if (left[i] <= right[j]) {
temp[k++] = left[i++];
} else {
temp[k++] = right[j++];
}
}
while (i < n1) {
temp[k++] = left[i++];
}
while (j < n2) {
temp[k++] = right[j++];
}
return temp;
}
}Time complexity is O(m + n) where m and n are array lengths of given two sorted arrays.
Merge Sorted Array Without Extra Space
Merge nums1 and nums2 into a single array sorted in non-decreasing order. The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n. Problem: 88. Solution
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
int[] arr1 = { 10, 15, 20, 0, 0, 0, 0 };
int[] arr2 = { 5, 6, 6, 15 };
merge(arr1, 3, arr2, 4);
System.out.println(Arrays.toString(arr1));
}
public static void merge(int[] nums1, int m, int[] nums2, int n) {
int p1 = m - 1; // pointer for nums1 (non-zero part)
int p2 = n - 1; // pointer for nums2
int i = m + n - 1; // pointer for the merged array
while (p2 >= 0) {
if (p1 >= 0 && nums1[p1] > nums2[p2]) {
nums1[i--] = nums1[p1--];
} else {
nums1[i--] = nums2[p2--];
}
}
}
}d-i. Merge Function of Merge Sort
For an array, low, mid, and high indexes are given. Elements from low to mid are sorted, and (mid + 1) to high are sorted. Sort the sub-array between low to high.
Example:- Array = {10, 15, 20, 11, 30}; low = 0, mid = 2, high = 4. Elements from index 0 to 2 are sorted and elements from index (2 + 1) to 4 are sorted. Sort the sub-array between low to high. Expected array = {10, 11, 15, 20, 30}.
Array = {5, 8, 12, 14, 7}; low = 0, mid = 3, high = 4.
Sorted Array = {5, 7, 8, 12, 14}
Low and high indexes are not necessarily always 0 and n respectively. It could be anywhere between 0 to n as:- 0 <= low <= mid < high <= n-1.
Example:- Array: {5, 12, 18, 3, 6, 10, 15, 20}; low = 2, mid = 4, high = 7.
- Elements from index 2 to 4 ({18, 3, 6}) are sorted.
- Elements from index 5 to 7 ({10, 15, 20}) are sorted.
- The task is to merge the subarray [18, 3, 6, 10, 15, 20] between low and high, resulting in {5, 12, 3, 6, 10, 15, 18, 20}.
Let us use the same technique we have used in the previous program. Created an array from index low to mid, and mid + 1 to high. Sort these two arrays and replace an element in the original array.
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
int[] arr = {5, 12, 3, 6, 18, 10, 15, 20};
int low = 2, mid = 4, high = 7;
merge(arr, low, mid, high);
System.out.println(Arrays.toString(arr));
// Expected output: [5, 12, 3, 6, 10, 15, 18, 20]
}
public static void merge(int[] arr, int low, int mid, int high) {
int n1 = mid - low + 1;
int n2 = high - mid;
int[] left = new int[n1];
int[] right = new int[n2];
for (int i = 0; i < n1; i++) {
left[i] = arr[low + i];
}
for (int i = 0; i < n2; i++) {
right[i] = arr[mid + 1 + i];
}
int i = 0, j = 0, k = low;
while (i < n1 && j < n2) {
if (left[i] <= right[j]) {
arr[k++] = left[i++];
} else {
arr[k++] = right[j++];
}
}
while (i < n1) {
arr[k++] = left[i++];
}
while (j < n2) {
arr[k++] = right[j++];
}
}
}
We are going to use this merge() method in the Merge sort algorithm.
d-ii. Merge Sort Algorithm
Merge Sort is a classic divide-and-conquer sorting algorithm. It’s known for its efficiency and is particularly useful for large datasets. The algorithm works by dividing the array into smaller subarrays, sorting each subarray, and then merging them back together. Problem: 912
- It uses Divide and Conquer technique (divide, conquer, and merge)
- It is a stable algorithm.
- Time complexity O(n log n) and Auxiliary space O(n).
- It is well suited for linked lists, and works in O(1) auxiliary space.
- It is not an in-place algorithm, however, there are some variants (block merge sort) that are in place.
- It is used in external sorting.
- In general, for arrays, Quick sort outperforms the merge sort (but not for the list). However, merge sort is still used in many libraries. For example Java Arrays & Collections class uses both Quick sort and Merge sort based on input type.
Steps:-
- Divide: Split the array into two halves until each subarray contains only one element.
- Conquer: Recursively sort each half.
- Combine: Merge the sorted halves to produce the sorted array.
Time Complexity: Best, Average, and Worst Case: O(n log n)
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
int[] arr = { 5, 12, 3, 6, 18, 10, 15, 20 };
mergeSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
public static void mergeSort(int[] arr, int l, int r) {
if (r > l) { // At least 2 elements should be there
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
// merge() method
}2. Intersection of Two Sorted Arrays
Arrays may contain duplicate elements but the result should contain the unique elements.
Array1 = {3, 5, 10, 10, 10, 15, 15, 20}; Array2 = {5, 10, 10, 15, 30}
Intersection = {5, 10, 15}
Array1 = {1, 1, 3, 3, 3}, Array2 = {1, 1, 1, 1, 3, 5, 7}
Intersection = {1, 3}
import java.util.ArrayList;
import java.util.List;
public class Test {
public static void main(String[] args) {
int[] arr1 = { 3, 5, 10, 10, 10, 15, 15, 20 };
int[] arr2 = { 5, 10, 10, 15, 30 };
List<Integer> intersection = intersection(arr1, arr2);
System.out.println(intersection);
}
// consider a.length <= b.length
// process array having minimum length
private static List<Integer> intersection(int[] a, int[] b) {
if (a.length > b.length) {
return intersection(b, a); // [10, 10, 15]
}
List<Integer> result = new ArrayList<>();
int n1 = a.length, n2 = b.length;
int i = 0, j = 0;
while (i < n1 && j < n2) {
// Skips Duplicates
if (i > 0 && a[i] == a[i - 1]) {
i++;
continue;
}
if (a[i] > b[j]) {
j++;
} else if (a[i] < b[j]) {
i++;
} else {
result.add(a[i]);
i++;
j++;
}
}
return result;
}
}Time complexity: O(m + n) because the pointers i and j traverse through both arrays linearly, each potentially up to their full lengths. Auxiliary space: O(1) (If we ignore storing the result). Also see:- Intersection of two unsorted array
3. Common in 3 Sorted Arrays
You are given three arrays sorted in increasing order. Find the elements that are common in all three arrays. If there are no such elements return an empty array. The resultant array should contain unique elements. Problem: 1113130
arr1 = [1, 5, 10, 20, 40, 80], arr2 = [6, 7, 20, 80, 100], arr3 = [3, 4, 15, 20, 30, 70, 80, 120]
Output: [20, 80]
import java.util.ArrayList;
import java.util.List;
public class Test {
public static void main(String[] args) {
List<Integer> a1 = List.of(1, 5, 10, 20, 40, 80);
List<Integer> a2 = List.of(6, 7, 20, 80, 100);
List<Integer> a3 = List.of(3, 4, 15, 20, 30, 70, 80, 120);
List<Integer> common = commonElements(a1, a2, a3);
System.out.println(common);
}
public static List<Integer> commonElements(List<Integer> a1,
List<Integer> a2, List<Integer> a3) {
List<Integer> common = new ArrayList<>();
int i = 0, j = 0, k = 0, n1 = a1.size(), n2 = a2.size(), n3 = a3.size();
while (i < n1 && j < n2 && k < n3) {
int val1 = a1.get(i);
int val2 = a2.get(j);
int val3 = a3.get(k);
if (val1 == val2 && val1 == val3) {
// to prevent adding duplicates
if (common.isEmpty() || common.get(common.size() - 1) != val1) {
common.add(val1);
}
i++;
j++;
k++;
// Skip duplicate elements
while (i < n1 && a1.get(i - 1) == a1.get(i)) {
i++;
}
while (j < n2 && a2.get(j - 1) == a2.get(j)) {
j++;
}
while (k < n3 && a3.get(k - 1) == a3.get(k)) {
k++;
}
} else if (val1 < val2) {
i++;
} else if (val2 < val3) {
j++;
} else {
k++;
}
}
return common;
}
}4. Union of Two-Sorted Arrays
Arrays may contain duplicate elements but the result should contain the unique elements. The resultant array should be sorted. Problem
Array1 = {3, 5, 8}; Array2 = {2, 8, 9, 10, 15}
Intersection = {2, 3, 5, 8, 9, 10, 15}
Array1 = {2, 3, 3, 3, 4, 4}, Array2 = {4, 4}
Intersection = {2, 3, 4}
import java.util.ArrayList;
import java.util.Arrays;
class Test {
public static ArrayList<Integer> findUnion(int a[], int b[]) {
int n1 = a.length, n2 = b.length, i = 0, j = 0;
ArrayList<Integer> list = new ArrayList<>();
while (i < n1 && j < n2) {
// Skip duplicates in array a
while (i > 0 && i < n1 && a[i] == a[i - 1]) {
i++;
}
// Skip duplicates in array b
while (j > 0 && j < n2 && b[j] == b[j - 1]) {
j++;
}
if (i < n1 && j < n2) {
if (a[i] < b[j]) {
list.add(a[i++]);
} else if (a[i] > b[j]) {
list.add(b[j++]);
} else {
list.add(a[i]);
i++;
j++;
}
}
}
while (i < n1) {
if (i == 0 || a[i] != a[i - 1]) {
list.add(a[i]);
}
i++;
}
while (j < n2) {
if (j == 0 || b[j] != b[j - 1]) {
list.add(b[j]);
}
j++;
}
return list;
}
public static void main(String[] args) {
int[] a1 = {1, 2, 3, 4, 5};
int[] b1 = {1, 2, 3, 6, 7};
System.out.println(findUnion(a1, b1));
int[] a2 = {2, 2, 3, 4, 5};
int[] b2 = {1, 1, 2, 3, 4};
System.out.println(findUnion(a2, b2));
int[] a3 = {1, 1, 1, 1, 1};
int[] b3 = {2, 2, 2, 2, 2};
System.out.println(findUnion(a3, b3));
}
}Time complexity: O(m + n), auxiliary space: O(1) (If we ignore storing the result). Also see:- Union of two unsorted Array
5. Count Inversions in an Array
A pair (arr[i], arr[j]) forms an inversion when i < j and arr[i] > arr[j]. Problem
Array = {2, 4, 1, 3, 5}; O/P: 3 [as (4, 1), (4, 3), (2, 1)]
Array = {10, 20, 30, 40}; O/P: 0 [Elements are sorted in ascending order]
Array = {40, 30, 20, 10}; O/P: 6 [Total = 3 + 2 + 1 = 6]
If array is sorted in descending order then n th element will form total n – 1 inversions. Hence for array of length N, total inversion = (n-1) + (n-2) + (n-3) + … + 1 = (n * (n – 1) / 2).
Naive Solution
public class Test {
public static void main(String[] args) {
int[] arr = { 2, 4, 1, 3, 5 };
System.out.println(countInversion(arr)); // 3
}
private static int countInversion(int[] arr) {
int res = 0, n = arr.length;
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (arr[i] > arr[j]) {
res++;
}
}
}
return res;
}
}Time complexity: O(n^2).
Solution using Merge Sort
Divide the array into 2 halves, sort these halves recursively, and then merge these two halves. Count the inversion while sorting the array. Count inversion in the left half and right half, and while merging count inversion in the complete array.
Every inversion (x, y) where x > y has possibilities:-
- Both x and y are in the left half.
- Both x and y are in the right half.
- X is in the left half and Y is in the right half.
We are computing res = res + (n1 - i) when left[i] > right [j] because there are total n1 elements in the left array and 0 to i-1 index elements are smaller than right[j] but the remaining n1 – i elements are greater than right[j].
public class Test {
public static void main(String[] args) {
int[] arr = { 2, 4, 1, 3, 5 };
System.out.println(countInv(arr, 0, arr.length - 1)); // 3
}
private static int countInv(int[] arr, int low, int high) {
int res = 0;
if (low < high) {
int mid = low + (high - low) / 2;
res += countInv(arr, low, mid);
res += countInv(arr, mid + 1, high);
res += merge(arr, low, mid, high);
}
return res;
}
private static int merge(int[] arr, int low, int mid, int high) {
int n1 = mid - low + 1, n2 = high - mid;
int[] left = new int[n1];
int[] right = new int[n2];
for (int i = 0; i < n1; i++) {
left[i] = arr[low + i];
}
for (int i = 0; i < n2; i++) {
right[i] = arr[mid + 1 + i];
}
int i = 0, j = 0, k = low, res = 0;
while (i < n1 && j < n2) {
if (left[i] <= right[j]) {
arr[k++] = left[i++];
} else {
arr[k++] = right[j++];
res = res + (n1 - i); // Count inversions
}
}
while (i < n1) {
arr[k++] = left[i++];
}
while (j < n2) {
arr[k++] = right[j++];
}
return res;
}
}Time complexity: O(n log n), auxiliary space: O(1).
6. Partition of a Given Array
Let us see the partition method of the quick sort alogrithm. For a given unsorted array, and index of an element of the array, partition the array based on the given index.
In the context of Quicksort, partitioning means rearranging the elements of the array such that:
- All elements less than or equal to the pivot (element at the given index) are on the left side of the pivot.
- All elements greater than the pivot are on the right side of the pivot.
- The pivot itself is placed in its correct sorted position.
Array = {3, 8, 6, 12, 10, 7};
P = 5 // index of the last element.
Resultant array = {3, 6, 7, 8, 12, 10} or {6, 3, 7, 12, 8, 10}, or …
In this example, p = 5, and at the 5th index 7 is suited. Therefore partition the array such that elements less than or equal to 7 should come on the left side of 7 and elements greater than 7 should be on the right side of 7. Resultant array = { elements_less_than_or_equal_to_7, 7, elements_greater_than_7 }. There can be multiple possible outputs because the elements on the left and right can come in any order.
Naive Partition
Problem: 2161
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
int[] arr = { 5, 13, 6, 9, 12, 11, 8 };
int p = 6; // partition-index (element = 8)
partition(arr, 0, arr.length - 1, p);
System.out.println(Arrays.toString(arr));
// [5, 6, 8, 13, 9, 12, 11]
}
private static void partition(int[] arr, int l, int h, int p) {
int[] temp = new int[h - l + 1];
int index = 0;
// elements <= arr[p]
for (int i = l; i <= h; i++) {
if (arr[i] <= arr[p]) {
temp[index] = arr[i];
index++;
}
}
// elements > arr[p]
for (int i = l; i <= h; i++) {
if (arr[i] > arr[p]) {
temp[index] = arr[i];
index++;
}
}
// replace
for (int i = l; i <= h; i++) {
arr[i] = temp[i - l];
}
}
}Time complexity: O(n), auxiliary space: O(n). But it uses 3 for loops, we can optimize it through the Lomuto partition or Hoare Partition.
Lomuto Partition Algorithm
Previously we have explicitly given partition index (p), but in the Lomuto partition, we will always consider the last index as the partition index (pivot). Steps:-
- Choose a Pivot: The last element of the array.
- Initialize Pointer:
i = l - 1. - Partition Loop: For each element j from l to h, if
arr[j] <= pivot, incrementiand swaparr[i]witharr[j]. - Final Swap: Swap
arr[i+1]with the pivot i.e.arr[h]. - Return Pivot Index:
i+1
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
int[] arr = { 5, 13, 6, 9, 12, 11, 8 };
int pivot = LomutoPartition(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
// [5, 6, 8, 9, 12, 11, 13]
System.out.println(pivot); // 2
}
private static int lomutoPartition(int[] arr, int low, int high) {
int pivot = arr[high]; // Pivot is the last element
int i = low - 1; // i is the index of the smaller element
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, high);
return i + 1; // Return the partition point
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}Time complexity: O(n), auxiliary space: O(n), and it uses a single for loop.
Corner cases:-
- {70, 60, 80, 40, 30} In this case, i remain -1 throughout the iteration. Therefore pivot element (last one) is just placed at the 0th index.
- {30, 40, 20, 50, 80} In this case, every element is less than the pivot element, therefore there will be an n-1 swap as elements replace it with itself.
How to handle the case when the pivot is not the last element? Example:- array = {50, 30, 20, 10, 5, 11}, and p = 2. In that case, we should simply call swap(arr[p], arr[h]) before computing the main logic of LomutoPartition(). Then the array will become {50, 30, 11, 10, 5, 20}. Now we can apply the same logic.
Hoare Partition Algorithm
Overall Hoare partition works best compared to Lomuto Partition. Like the Lomuto partition, it has also O(n) time and O(1) auxiliary space with only one traversal of the input array.
In Hoare’s partition, we consider the first element as the pivot element.
Alright, so here’s the gist of Hoare’s Partition Algorithm:-
- Choose a pivot element from the array.
- Initialize two pointers: one starting from the leftmost element and the other from the rightmost element.
- Move the left pointer rightwards until an element greater than the pivot is found.
- Move the right pointer leftwards until an element smaller than the pivot is found.
- Swap these two elements.
- Repeat steps 3-5 until the pointers meet or cross each other.
When the pointers meet, the array is partitioned with elements less than the pivot on one side and greater on the other.
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
int[] arr = { 5, 3, 8, 4, 2, 7, 1, 10 };
int index = hoarePartition(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
// [1, 3, 2, 4, 8, 7, 5, 10]
System.out.println("Pivot index: " + index);
}
private static int hoarePartition(int[] arr, int l, int h) {
int pivot = arr[l]; // Consider the first element as the pivot
int i = l - 1, j = h + 1;
while (true) {
// Increment i until an element greater than or equal to pivot is found
do {
i++;
} while (arr[i] < pivot);
// Decrement j until an element less than or equal to pivot is found
do {
j--;
} while (arr[j] > pivot);
// If pointers cross, return the partition point
if (i >= j) {
return j;
}
// Swap elements at i and j
swap(arr, i, j);
}
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}Output:-
[1, 3, 2, 4, 8, 7, 5, 10]
Pivot index: 3
The pivot index is 3 which means the left part contains all the smaller elements than the pivot and the right part contains elements greater than or equal to the pivot.
Lomuto vs Hoare partitions:- In the Lomuto partition we were picking up the pivot, and we were fixing that pivot at its correct position. However, in the Hoare partition, the pivot element is not at its correct position. If we want to ensure that the pivot element is placed at its correct index, then we should use the Lomuto partition.
However, in general, Hoare’s partition uses fewer comparisons than the Lomuto partition.
Corner case:-
- Pivot is the smallest. Example: {5, 10, 9, 12}. The i will remain at 0, and j will reach at 0.
- Pivot is the largest. Example: {12, 10, 5, 9}. The i will stop at 0, and j will stop at arr.length-1, then swap(arr, i, j) will swap their position, and array becomes {9, 10, 5, 12}. Now the process continues.
- All elements are the same. This case explains how Hoare’s partition algorithm is unstable, (therefore it leads quick sort to unstable). Example: {5, 5, 5, 5}. The i is stop at 0 and j will stop at arr.length-1, then swap(arr, i, j) is called and i++, j– performs. Now i is at 1 and j is at arr.length-2, again swap(arr, i, j) is called and this process continues till i < j.
Similar swapping happens in Lomuto’s partition also therefore both Lomuto and Hoare partitions are not stable. If we want stability, then we can go for the naive partition, it will provide stable results. Naive partition was not swapping, it was just coping the element.
e. Quick Sort Algorithm
- It is a divide-and-conquer algorithm.
- Partition is the key function (Naive, Lomuto, Hoare).
- Worst case time complexity: O(n^2)
- Despite O(n^2) worst case, it is considered fast because of the following reasons:-
- In-place (Extra space is required only for recursive calls but not for the array).
- Cache friendly (Because we are using the array for modification).
- The average case is O(n log n).
- The best case is O(n log n).
- Tail Recursive.
Quick sort with different partition approaches:-
- Quick Sort + Naive Partition = Stable (but inefficient)
- Quick Sort + Lomuto Partition = Unstable
- Quick Sort + Hoare Partition = Unstable (best)
Merge sort vs Quick Sort:- If you don’t need stability then quick sort (or its variation) is the fastest algorithm. But if you need stability then merge sort is best.
Quick Sort Using Lomuto Partition
Lomuto Partition is simpler and uses a single index to partition the array. Here’s how you can implement quicksort with Lomuto partition:
- Choose a Pivot: Typically, the last element in the array is chosen as the pivot.
- Partitioning: Reorder the array so that all elements less than the pivot come before it, and all elements greater than the pivot come after it.
- Recursively Apply: Apply the above steps recursively to the sub-arrays.
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
int[] arr = { 5, 3, 8, 4, 2, 7, 1, 10 };
quickSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
private static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pivotIndex = lomutoPartition(arr, low, high);
quickSort(arr, low, pivotIndex - 1);
// pivotIndex is already at correct position
quickSort(arr, pivotIndex + 1, high);
}
}
private static int lomutoPartition(int[] arr, int low, int high) {
int pivot = arr[high]; // Pivot is the last element
int i = low - 1; // i is the index of the smaller element
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, high);
return i + 1; // Return the partition point
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}Quick Sort Using Hoare Partition
Here’s how it goes:-
- Choose a Pivot: Typically, the first element is chosen as the pivot.
- Partitioning: Using Hoare’s scheme, rearrange the array so elements less than the pivot are on one side, and greater elements are on the other.
- Recursively Apply: Apply these steps to the sub-arrays.
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
int[] arr = { 5, 3, 8, 4, 2, 7, 1, 10 };
quickSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
private static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pivotIndex = hoarePartition(arr, low, high);
quickSort(arr, low, pivotIndex);
quickSort(arr, pivotIndex + 1, high);
}
}
private static int hoarePartition(int[] arr, int low, int high) {
int pivot = arr[low]; // Pivot is the first element
int i = low - 1, j = high + 1;
while (true) {
do {
i++;
} while (arr[i] < pivot);
do {
j--;
} while (arr[j] > pivot);
if (i >= j) {
return j; // Return the partition index
}
swap(arr, i, j);
}
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}Using Random Index for Pivot
Using a random index for the pivot can help improve the average performance of quicksort, especially in cases where the input may be already sorted or nearly sorted, which can lead to poor performance with a fixed pivot. Here’s how you could implement it:-
- Generate a random index between low and high.
- Swap the element at the random index with the element at low to use it as the pivot.
private static int hoarePartition(int[] arr, int low, int high) {
Random random = new Random();
int pivotIndex = low + random.nextInt(high - low + 1);
swap(arr, low, pivotIndex); // Move pivot to the start
int pivot = arr[low];
int i = low - 1, j = high + 1;
while (true) {
do {
i++;
} while (arr[i] < pivot);
do {
j--;
} while (arr[j] > pivot);
if (i >= j) {
return j;
}
swap(arr, i, j);
}
}Tail Call Elimination in Quick Sort
Tail call elimination is a neat optimization technique that can make recursive algorithms like quicksort more efficient by reducing the depth of the recursive call stack. Here’s the trick for quicksort:
- Identify: The tail-recursive part of the function, which is typically the last recursive call.
- Convert: The tail-recursive call into an iterative loop.
For quicksort, after partitioning, you’ll want to handle the smaller part first and turn the other part into a tail call. Here’s a Java implementation that does this:
private static void quickSort(int[] arr, int low, int high) {
while (low < high) { // while loop
// Partition the array
int pivotIndex = hoarePartition(arr, low, high);
// Recursively sort the smaller part
if (pivotIndex - low < high - pivotIndex) {
quickSort(arr, low, pivotIndex);
low = pivotIndex + 1; // Tail call optimization
} else {
quickSort(arr, pivotIndex + 1, high);
high = pivotIndex; // Tail call optimization
}
}
}Optimized Code for Quick Sort
import java.util.Arrays;
import java.util.Random;
public class Test {
public static void quickSort(int[] arr, int low, int high) {
while (low < high) {
// Partition the array
int pivotIndex = hoarePartition(arr, low, high);
// Recursively sort the smaller part
if (pivotIndex - low < high - pivotIndex) {
quickSort(arr, low, pivotIndex);
low = pivotIndex + 1; // Tail call optimization
} else {
quickSort(arr, pivotIndex + 1, high);
high = pivotIndex; // Tail call optimization
}
}
}
private static int hoarePartition(int[] arr, int low, int high) {
Random random = new Random();
int pivotIndex = low + random.nextInt(high - low + 1);
swap(arr, low, pivotIndex); // Move pivot to the start
int pivot = arr[low];
int i = low - 1, j = high + 1;
while (true) {
do {
i++;
} while (arr[i] < pivot);
do {
j--;
} while (arr[j] > pivot);
if (i >= j) {
return j;
}
swap(arr, i, j);
}
}
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 = { 9, 13, 6, 5, 12, 11, 8 };
quickSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr)); // Output sorted array
}
}7. Quick Select Algorithm (Kth Smallest in the Array)
For a given unsorted array, find the kth smallest element in the array. Consider the array contains distinct elements. Examples:-
Array = { 10, 5, 30, 12}, k = 2; O/P: 10
Array = { 30, 20, 5, 10, 8}, k = 4; O/P: 20
The naive solution is to sort the array and return (k-1)th element from the sorted array. Time complexity will be O(n log n). This approach modifies the original array. We can optimize it using the Lomuto partition.
Quick Select is a neat algorithm for finding the kth smallest (or largest) element in an unsorted array with distinct elements. It’s like quicksort but instead of sorting the entire array, it focuses on the partitioning step to narrow down the search. Here’s the gist:
- Partition the array: Choose a pivot and partition the array around it.
- Compare the pivot index: If the pivot index matches k – 1, you’ve found the k-th smallest element.
- Adjust search range: If the pivot index is greater, search in the left sub-array; if smaller, search in the right sub-array.
- Repeat until found: Keep partitioning and narrowing down until the element is found.
import java.util.Random;
public class Test {
public static void main(String[] args) {
int[] arr = { 10, 5, 30, 12 };
int k = 2;
System.out.println(kthSmallest(arr, k)); // 10
}
private static int kthSmallest(int[] arr, int k) {
int low = 0, high = arr.length - 1;
while (low <= high) { // should be low <= high
int pivotIndex = lomutoPartition(arr, low, high);
if (pivotIndex == k - 1) {
return arr[pivotIndex];
} else if (pivotIndex > k - 1) {
high = pivotIndex - 1;
} else {
low = pivotIndex + 1;
}
}
return -1;
}
private static int lomutoPartition(int[] arr, int low, int high) {
Random random = new Random();
int pivotIndex = low + random.nextInt(high - low + 1);
swap(arr, pivotIndex, high); // Move pivot to the end
int pivot = arr[pivotIndex];
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;
}
}Time complexity:
- Best Case: O(n)
- Average Case: O(n)
- Worst Case: O(n^2)
How it will work for the kth largest element? For finding the k-th largest element, the Quick Select algorithm needs a slight adjustment. Instead of looking for the kth smallest element, you’ll need to look for the (n-k)-th smallest element, where n is the size of the array. This essentially flips the problem.
private static int kthSmallest(int[] arr, int k) {
int low = 0, high = arr.length - 1;
int kLargestIndex = arr.length - k; // Adjust index for k-th largest
while (low <= high) {
int pivotIndex = lomutoPartition(arr, low, high);
if (pivotIndex == kLargestIndex) {
return arr[pivotIndex];
} else if (pivotIndex > kLargestIndex) {
high = pivotIndex - 1;
} else {
low = pivotIndex + 1;
}
}
return -1;
}Note that the quick select algorithm modifies the original array. If you don’t want to modify the original array then you can create a separate copy of the original array.
8. Chocolate Distribution Problem
The Chocolate Distribution Problem is a classic problem in computer science and optimization. It typically involves distributing a certain number of chocolate packets among children in such a way that the difference between the number of chocolates in the packet with the most chocolates and the packet with the least chocolates is minimized.
Here’s the usual formulation:
- Given: An array of n packets, where each packet has a certain number of chocolates, and a number m, which represents the number of children.
- Constraints: Each child must get exactly one packet, and the number of packets n should be at least as many as the number of children m (i.e., n >= m).
- Objective: Distribute the packets such that the difference between the maximum number of chocolates in a packet and the minimum number of chocolates in a packet given to the children is minimized.
Array = {7, 3, 2, 4, 9, 12, 56}, m = 3; O/P: 2 [as (3, 2, 4)]
Array = {3, 4, 1, 9, 56, 7, 9, 12}, m = 5; O/P: 6 [as (3, 4, 7, 9, 9)]
Approach:
- Sort the array: Sort the array of chocolates.
- Find the minimum difference: Iterate through the array, and for each window of size m, find the difference between the maximum and minimum chocolates. Keep track of the minimum of these differences.
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
int[] arr = { 7, 3, 2, 4, 9, 12, 56 };
int m = 3;
System.out.println(minDiff(arr, m));
}
private static int minDiff(int[] arr, int m) {
if (m > arr.length) {
return -1;
}
Arrays.sort(arr);
int res = arr[m - 1] - arr[0];
for (int i = 1; (i + m - 1) < arr.length; i++) {
res = Math.min(res, arr[i + m - 1] - arr[i]);
}
return res;
}
}Time complexity: O(n log n)
9. Sort an Array with Two Types
This problem is asked in different forms. Here are the main 3 popular forms:-
1. Segregate Positive and Negative. Put all negatives first in the sorted array, and then the positives. The order between positive elements and negative elements may change.
Array = {15, -3, -2, 18}; O/P: {-3, -2, 15, 18} or {-2, -3, 18, 15} or ..
2. Segregate Even and Odd: Put all even elements first in the sorted array and then the odd elements. The order among odd/events may change.
Array = {15, 14, 13, 12}; O/P: {14, 12, 15, 13}
3. Sort a Binary Array
Array = {0, 1, 1, 1, 0}; O/P: {0, 0, 1, 1, 1}
This problem is mainly a variation of the partition of Quick Sort. Hoare or Lomuto partition can solve this in O(n) time and O(1) auxiliary space.
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
int[] arr = { -12, 18, -10, 15 };
segPosNeg(arr);
System.out.println(Arrays.toString(arr));
// [-12, -10, 18, 15]
}
private static void segPosNeg(int[] arr) {
int i = -1, n = arr.length, j = n;
while (true) {
do {
i++;
} while (arr[i] < 0);
do {
j--;
} while (arr[j] > 0);
if (i >= j) {
return;
}
swap(arr, i, j);
}
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}10. Dutch National Flag Algorithm (Sort an Array with Three Types)
This problem is asked in different forms. Here are the main popular forms:-
1. Sort an array of 0s, 1s and 2s. Problem: 75
Array = {0, 1, 0, 2, 1, 2}; O/P: {0, 0, 1, 1, 2, 2}
2. Three-way partitioning: For a given array, partition the array around a pivot. There can be multiple occurrences of this pivot. All occurrences of the pivot should come together. All elements smaller than the pivot should come left side (in any order), and all elements greater than the pivot should come right side.
Array = {2, 1, 2, 20, 10, 20, 1}, Pivot = 2
O/P: {1, 1, 2, 2, 20, 10, 20}
3. Partition Around a range: In the below example, all the elements smaller than 5 should come first, elements between 5 to 10 should come, and then elements greater than 10 should come. The order of elements doesn’t matter.
Array = {10, 5, 6, 3, 20, 9, 40}, Range = [5, 10]
O/P: {3, 5, 6, 9, 10, 20, 40}
The Dutch National Flag Algorithm is a variation of Hoare’s partition.
The Dutch National Flag Algorithm, devised by Edsger Dijkstra, is a clever way to sort an array containing three distinct elements. Imagine you have an array of elements colored red, white, and blue (like the Dutch flag), and you need to sort them in this exact order.
Here’s how it works:-
- Initialize three pointers:
- low (starting from the beginning of the array)
- mid (also starting from the beginning)
- high (starting from the end of the array)
- Iterate through the array:
- If the element at mid is red (0), swap it with the element at low, and increment both low and mid.
- If the element at mid is white (1), just move mid ahead.
- If the element at mid is blue (2), swap it with the element at high, and decrement high.
- Stop when mid crosses high.
Time complexity O(n) with one traversal, auxiliary space o(1).
1. Sort an array of 0s, 1s and 2s
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
int[] arr = { 0, 1, 0, 2, 1, 2 };
partition(arr);
System.out.println(Arrays.toString(arr));
// [0, 0, 1, 1, 2, 2]
}
private static void partition(int[] arr) {
int low = 0, mid = 0, high = arr.length - 1;
while (mid <= high) {
if (arr[mid] == 0) { // Red
swap(arr, low++, mid++);
} else if (arr[mid] == 1) { // White
mid++;
} else if (arr[mid] == 2) { // Blue
swap(arr, mid, high--);
}
}
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}2. Three-way partitioning
public class PartitionExample {
public static void main(String[] args) {
int[] arr = { 2, 1, 2, 20, 10, 20, 1 };
int pivot = 2;
partition(arr, pivot);
System.out.println(Arrays.toString(arr)); // [1, 1, 2, 2, 20, 10, 20]
}
private static void partition(int[] arr, int pivot) {
int low = 0, mid = 0, high = arr.length - 1;
while (mid <= high) {
if (arr[mid] < pivot) {
swap(arr, low++, mid++);
} else if (arr[mid] == pivot) {
mid++;
} else if (arr[mid] > pivot) {
swap(arr, mid, high--);
}
}
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}11. Minimum Difference in an Array
For a given array, find the minimum difference between any two elements. Example:-
Array = {1, 8, 12, 5, 18}; Minimum difference = 3 (for 8 & 5)
Array = {8, 15}; Minimum difference = 7
Array = {8, -1, 0, 3}; Minimum difference = 1 (for -1 & 0)
Array = {10}; Minimum difference = Infinite
// naive solution
public class Test {
public static void main(String[] args) {
int[] arr = { 1, 8, 12, 5, 18 };
System.out.println(minimumDifference(arr));
}
private static int minimumDifference(int[] arr) {
int res = Integer.MAX_VALUE;
for (int i = 1; i < arr.length; i++) {
for (int j = 0; j < i; j++) {
res = Math.min(res, Math.abs(arr[j] - arr[i]));
}
}
return res;
}
}Time complexity: O(n^2)
We can find out the minimum difference only within the value of the closest elements. Therefore if we sort the array, then it will lot easier to compare the adjusted elements:-
- Sort the array
- Computer the difference between the adjacent elements.
- Return the minimum difference.
private static int minimumDifference(int[] arr) {
int res = Integer.MAX_VALUE;
Arrays.sort(arr);
for (int i = 0; i < arr.length - 1; i++) {
res = Math.min(res, Math.abs(arr[i + 1] - arr[i]));
}
return res;
}Time complexity: O(n log n)
12. Merge Overlapping Intervals
Given a collection of intervals, merge all overlapping intervals. Problem: 56. Example:-
Input: { {1, 3}, {2, 6}, {8, 10}, {15, 18} }
Output: { {1, 6}, {8, 10}, {15, 18} }
Explanation:-
- Intervals {1, 3} and {2, 6} overlap and are merged into {1, 6}.
- Intervals {8, 10} and {15, 18} do not overlap and remain as is.
Constraints:
- All intervals are represented as pairs of integers [start, end].
- The intervals are not necessarily sorted initially.
More Examples:-
Input = { {1, 3}, {2, 4}, {5, 7}, {6, 8} }
Output = { {1, 4}, {5, 8} }
Input = { {7, 9}, {6, 10}, {4, 5}, {1, 3}, {2, 4} }
Output = { {1, 5}, {6, 10} }
How to check if two intervals overlap?
i1 = {5, 10}, i2 = {1, 7}
If the larger of one pair (7) lies between the other pair (l1) then they overlap. Here 7 >= 5 and 7 <= 10. Another example is: i1 = {10, 20}, i2 = {5, 15}. Here, 15 >= 10 and 15 <= 20.
In case of two interval overlap, the new interval becomes:-
start = min(i1.start, i2.start)
end = max(i1.end, i2.end)
Solution idea:-
- Sort by start time in increasing order (or sort by end time in decreasing order).
- Traverse all interval from left to right, and keep merging overlapping interval.
- For comparison, compare with previously merged interval.
import java.util.Arrays;
import java.util.Comparator;
public class Test {
static class Interval {
int start;
int end;
public Interval(int start, int end) {
this.start = start;
this.end = end;
}
}
public static void main(String[] args) {
Interval[] arr = { new Interval(5, 10), new Interval(3, 15),
new Interval(18, 30), new Interval(2, 7) };
mergeIntervals(arr);
}
private static void mergeIntervals(Interval[] arr) {
Arrays.sort(arr, new Comparator<Interval>() {
@Override
public int compare(Interval o1, Interval o2) {
return o1.start - o2.start;
}
});
// {{2, 7}, {3, 15}, {5, 10}, {18, 30}}
int res = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[res].end >= arr[i].start) { // overlap
arr[res].end = Math.max(arr[res].end, arr[i].end);
arr[res].start = Math.min(arr[res].start, arr[i].start);
} else {
res++;
arr[res] = arr[i];
}
}
// display array from 0 to res only
for (int i = 0; i <= res; i++) {
System.out.println("{" + arr[i].start + ", " + arr[i].end + "}");
}
}
}Output:-
{2, 15}
{18, 30}
Time complexity: O(n log n) because of sorting (n log n) + linear traversal (n).
13. Meeting Maximum Guests
This problem involves finding the maximum number of guests present at the same time during an event, given their arrival and departure times. Problem: 1353
Given two arrays:
- arrival: An array of times at which guests arrive.
- departure: An array of times at which guests leave.
The task is to find the maximum number of guests present at the event at the same time and the time at which the maximum number of guests are present.
For simplicity, we will be using 940 instead of 9:40. 0 <= arr[i], dep[] <= 2359
Input:
- arrival = {900, 940}
- departure = {1000, 1030}
Output:
- Maximum number of guests: 2
- Time: 9:40 to 10:00
More Examples:-
Arrival = {800, 700, 600, 500}
Departure = {840, 820, 830, 530}
Maximum guests = 3 (time: 8:00 to 8:20)
Arrival = {900, 940, 950, 1100, 1500, 1800}
Arrival = {910, 1200, 1120, 1130, 1900, 2000}
Maximum guests = 3 (time: 11:00 to 11:20)
To solve this problem we will use sorting. We will consider all the timelines from first arrival to last departure and every time we will see how many guests are there. The maximum number of guests at a particular time will be the answer.
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
int[] arrival = { 800, 700, 600, 500 };
int[] departure = { 840, 820, 830, 530 };
System.out.println(maxGuest(arrival, departure)); // 3
}
private static int maxGuest(int[] arrival, int[] departure) {
Arrays.sort(arrival);
Arrays.sort(departure);
// in arrival start from 1st entry
int i = 1, maxGuest = 1, currentGuest = 1;
// in departure start from 0 index
int j = 0, n = arrival.length;
// merge both array
while (i < n && j < n) {
if (arrival[i] <= departure[j]) {
currentGuest++;
i++;
} else {
currentGuest--;
j++;
}
maxGuest = Math.max(maxGuest, currentGuest);
}
return maxGuest;
}
}Time complexity: O(n log n) because of sorting (n log n) + linear traversal (m + n).
f. Cycle Sort Algorithm
Cycle Sort is an in-place, non-comparison-based sorting algorithm, and it’s ideal for situations where memory writes are expensive. The key idea is to place elements directly into their correct positions.
- The worst-case time complexity is O(n^2).
- Specialty:- It does minimum memory writes (compared to other sorting algorithms) and can be useful for cases where memory writing is costly.
- It is in place and not stable.
- It is useful to solve questions like finding the minimum swaps required to sort an array.
Steps:-
- For each cycle:
- Start with the element at the current index.
- Find the correct position of this element by counting how many elements are smaller than it.
- If the element is already in the correct position, skip it.
- Otherwise, place it into the correct position and continue to place elements from this position until the cycle is complete.
- Repeat for all cycles in the array.
Example:- 20 40 50 10 30
Item = 20, find its correct and place it, get the previous suited element as the item.
1st cycle, 20 20 50 10 30, item = 40
2nd cycle, 20 20 50 40 30, item = 10
3rd cycle, 10 20 50 40 30, item = 20
20 is already in the correct position, therefore move to the next element => item = 50
4th cycle, 10 20 50 40 50, item = 30
5th cycle, 10 20 30 40 50, item = 40
40 is already in the correct position, therefore move to the next element => item = 50
50 is already in the correct position, and there are no more elements in the array.
Cycle sort algorithm implementation considering the array does not contain duplicate elements.
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
int[] arr = { 20, 40, 50, 10, 30 };
cycleSortDistinct(arr);
System.out.println(Arrays.toString(arr));
}
private static void cycleSortDistinct(int[] arr) {
int n = arr.length;
for (int cs = 0; cs < n - 1; cs++) {
int item = arr[cs];
int pos = cs;
// Find the position where we should put the element
for (int i = cs + 1; i < n; i++) {
if (arr[i] < item) {
pos++;
}
}
// If the item is already in the correct position
if (pos == cs) {
continue;
}
// Otherwise, put the item to its correct position
while (item == arr[pos]) {
pos++;
}
if (pos != cs) {
int temp = item;
item = arr[pos];
arr[pos] = temp;
}
// Rotate rest of the cycle
while (pos != cs) {
pos = cs;
for (int i = cs + 1; i < n; i++) {
if (arr[i] < item) {
pos++;
}
}
while (item == arr[pos]) {
pos++;
}
if (pos != cs) {
int temp = item;
item = arr[pos];
arr[pos] = temp;
}
}
}
}
}Cycle sort algorithm implementation considering array contains duplicate elements.
When dealing with duplicates, Cycle Sort requires some tweaks to handle repeated elements correctly:
- Detection of Duplicates: When placing an element in its correct position, skip over duplicate elements to avoid unnecessary swaps and cycles.
- Handling Cycles: Instead of cycling through positions blindly, check if the position is already correct before swapping, and ensure duplicates don’t cause infinite loops.
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
int[] arr = { 10, 5, 10, 30, 40, 20, 5, 30 };
System.out.println("Minimum swap required: " + cycleSort(arr));
System.out.println(Arrays.toString(arr));
}
public static int cycleSort(int[] arr) {
int n = arr.length, swapCount = 0;
for (int cs = 0; cs < n - 1; cs++) {
int item = arr[cs];
int pos = cs;
// Find the position where we should put the element
for (int i = cs + 1; i < n; i++) {
if (arr[i] < item) {
pos++;
}
}
// If the item is already in the correct position, skip
if (pos == cs) {
continue;
}
// skip duplicates
while (item == arr[pos]) {
pos++;
}
// place the item in its correct position
int temp = arr[pos];
arr[pos] = item;
item = temp;
swapCount++;
// rest of the cycle
while (pos != cs) {
pos = cs;
// Find the position where we should put the element
for (int i = cs + 1; i < n; i++) {
if (arr[i] < item) {
pos++;
}
}
// skip duplicates
while (item == arr[pos]) {
pos++;
}
// place the item in its correct position
temp = arr[pos];
arr[pos] = item;
item = temp;
swapCount++;
}
}
return swapCount;
}
}Output:-
Minimum swap required: 6
[5, 5, 10, 10, 20, 30, 30, 40]
g. Heap Sort Algorithm
The basic idea of heap sort is based on the selection sort algorithm where we first the maximum element and swap it with the last element. In the selection sort, we do a linear search to find the maximum element therefore the time complexity of the selection sort becomes O(n^2). Heap sort uses max heap data structure to find the maximum element therefore its time complexity becomes O(n log n).
In heap sort, we restructure the array, so that the array can form a max heap. Building a max heap from a random array takes log n time. After forming the max heap, we swap the last element with the root of the max heap, and then we Heapfiy the root.
If we want to sort the array in increasing order then we use max heap, and if we want to sort the array in decreasing order then we use min heap.
Here’s a step-by-step explanation of how Heap Sort works:
- Build a Max Heap: Convert the array into a Max Heap, where the largest element is at the root. This process ensures that the parent node is always greater than or equal to its child nodes.
- Extract Elements:
- Swap the root (largest element) with the last element of the heap.
- Reduce the heap size by one and heapify the root element to maintain the Max Heap property.
- Repeat this process until all elements are extracted and the heap size is reduced to one.
Algorithm Steps:-
- Build a Max Heap from the input data.
- Repeat the following until the heap size is greater than 1:
- Swap the root of the heap with the last element.
- Reduce the size of the heap by one.
- Heapify the root element.
public class HeapSort {
public void sort(int arr[]) {
int n = arr.length;
// Build max heap
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// One by one extract an element from heap
for (int i = n - 1; i > 0; i--) {
// Move current root to end
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// Call max heapify on the reduced heap
heapify(arr, i, 0);
}
}
void heapify(int arr[], int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
// If left child is larger than root
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
// If right child is larger than largest so far
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
// If largest is not root
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
// Recursively heapify the affected sub-tree
heapify(arr, n, largest);
}
}
public static void main(String[] args) {
int arr[] = {12, 11, 13, 5, 6, 7};
HeapSort heapSort = new HeapSort();
heapSort.sort(arr);
System.out.println("Sorted array is:");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
}Advantages:
- Efficiency: Heap Sort has a time complexity of O(n log n) for all cases (best, average, and worst).
- In-place Sorting: It does not require additional memory for sorting (except for the input array).
Disadvantages:
- Not Stable: Heap Sort is not a stable sort, meaning that the relative order of equal elements is not preserved.
Heap Sort is particularly useful when dealing with large datasets where memory usage needs to be minimized.
Heap Sort can be mainly seen as an improvement of the selection sort. It uses heap data structure and the concept of selection sort. Time complexity: O(n log n).
Merge sort takes O(n log n) in worst case, quick sort takes O(n log n) on average case, heap sort takes O(n log n) in all cases.
When we compare Heap sort with merge sort and quick sort, the constant hidden in heap sort is higher than merge sort and quick sort. In practice, merge sort and quick sort takes less time compared to heap sort. Merge sort and Quick sort are used more in practice.
However, there are hybrid algorithms like Intro sort which are based on quick sort but also use heap sort. Quick sort may go beyond O(n log n) in certain cases and recursion depth becomes more than O(n log n). Intro sort switches to heap sort when the recursion depth goes beyond O(n log n). Intro sort is used in the C++ standard library. In libraries, heap sort alone is not used, however, it is used as a hybrid algorithm.
h. Counting Sort Algorithm
Counting Sort is a non-comparison-based sorting algorithm that works by counting the occurrences of each unique element in the input array and using this information to place the elements in their correct positions. It is efficient for sorting integers within a known, limited range.
It is a linear time algorithm for the cases when our input is in the small range. For example we have N elements and elements are from 0 to k-1 then it will take O(N + K) times to sort them. It never compares items with each other.
Example:-
Array = {1, 4, 4, 1, 0, 1}
K = 5
Sorted Array = {0, 1, 1, 1, 4, 4}
Array = {2, 1, 8, 9, 4}
K = 10
Sorted Array = {1, 2, 4, 8, 9}
Naive Solution:-
- Create an empty array (count) of size k.
- Count the elements and assign them to count[i].
- Use this count array to replace the original array elements.
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
int arr[] = { 1, 4, 4, 1, 0, 1 };
int k = 5;
countingSort(arr, k);
System.out.println(Arrays.toString(arr));
// [0, 1, 1, 1, 4, 4]
}
private static void countingSort(int[] arr, int k) {
int[] count = new int[k];
for (int a : arr) {
count[a]++;
}
int index = 0;
for (int i = 0; i < k; i++) {
for (int j = 0; j < count[i]; j++) {
arr[index] = i;
index++;
}
}
}
}Overall time complexity: O(n + k)
Problem with this approach: It can’t be used as a general-purpose algorithm for sorting objects with multiple members, like sorting an array of students by marks.
General Purpose Implementation
- Find the Range: Determine the range of the input data (i.e., find the maximum and minimum values).
- Create Count Array: Create a count array to store the frequency of each unique element in the input array.
- Cumulative Count: Modify the count array by adding the count of the previous element to the current element. This step ensures that each position in the count array contains the actual position of the element in the sorted array.
- Build the Output Array: Traverse the input array from right to left and place each element in its correct position in the output array using the count array.
- Copy the Output Array: Copy the sorted elements from the output array back to the original array.
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
int arr[] = { 5, 6, 5, 2 };
int k = 7;
countingSort(arr, k);
System.out.println(Arrays.toString(arr));
// [2, 5, 5, 6]
}
private static void countingSort(int[] arr, int k) {
int n = arr.length;
// Create count array with size (k + 1)
int[] count = new int[k + 1];
// Store the count of each element
for (int a : arr) {
count[a]++;
}
// Store the cumulative count
for (int i = 1; i <= k; i++) {
count[i] += count[i - 1];
}
// find the index of each element and place it in the output array
int[] output = new int[n];
for (int i = n - 1; i >= 0; i--) {
output[count[arr[i]] - 1] = arr[i];
count[arr[i]]--;
}
// copy the sorted elements back to the original array
for (int i = 0; i < n; i++) {
arr[i] = output[i];
}
}
}While placing the elements we have used i = n - 1 which will make the resultant array as stable.
Important points about counting sort:-
- Not a comparison-based algorithm.
- Time complexity: O(n + k)
- Auxiliary complexity: O(n + k)
- Stable
- Used as a subroutine in Radix Sort.
Disadvantages:
- Limited Range: Counting Sort is only efficient when the range of the input data (i.e., the difference between the maximum and minimum values) is not significantly larger than the number of elements.
- Space Complexity: It requires additional memory for the count array, which can be problematic for large ranges.
Extend the given implementation to work for an arbitrary range of size K
For that, we have to determine the minimum and maximum values in the input array to calculate the range and calculate an offset to handle negative numbers.
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
int[] arr = { 4, 2, -2, 8, 3, -3, 1 };
countingSort(arr);
System.out.println(Arrays.toString(arr));
// [2, 5, 5, 6]
}
private static void countingSort(int[] arr) {
int n = arr.length;
// Find minimum and maximum elements
int max = arr[0], min = arr[0];
for (int k : arr) {
max = Math.max(max, k);
min = Math.min(min, k);
}
// Calculate the range and offset
int range = max - min + 1;
int offset = -min;
// Create count array with size = range
int[] count = new int[range];
// Store the count of each element
for (int a : arr) {
count[a + offset]++;
}
// Store the cumulative count
for (int i = 1; i < range; i++) {
count[i] += count[i - 1];
}
// find the index of each element and place it in the output array
int[] output = new int[n];
for (int i = n - 1; i >= 0; i--) {
output[count[arr[i] + offset] - 1] = arr[i];
count[arr[i] + offset]--;
}
// copy the sorted elements back to the original array
for (int i = 0; i < n; i++) {
arr[i] = output[i];
}
}
}i. Radix Sort Algorithm
Like counting sort, radix sort is also a linear time algorithm that can be used if the data is within a limited range. The question arises: If counting sort is already there, why do we need Radix sort? Counting sort takes O(n + k). If k = n2, it will take O(n2), which is worse than standard comparison-based algorithms like Merge sort and Heap sort. Radix Sort supports linear time O(n) even for a larger range.
It uses counting sort as a subroutine. It is also a non-comparison-based sorting algorithm. Steps:-
- Determine the Maximum Number of Digits: Find the maximum number in the array to determine the number of digits in the largest number.
- Sort by Each Digit: Starting from the least significant digit, sort the array based on each digit using a stable sorting algorithm (typically Counting Sort).
- Repeat for Each Digit: Repeat the sorting process for each digit until all digits have been processed.
Array = {319, 212, 6, 8, 100, 50}
Make the same number of digits by re-writing numbers with leading zeros:-
{319, 212, 006, 008, 100, 050}
Stable sort according to the last digit (last significant digit)
{100, 050, 212, 006, 008, 319}
Stable sort according to the middle digit
{100, 006, 008, 212, 319, 050}
Stable sort according to the first digit
{006, 008, 050, 100, 212, 319}
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
int[] arr = { 319, 212, 6, 8, 100, 50 };
radixSort(arr);
System.out.println(Arrays.toString(arr));
// [6, 8, 50, 100, 212, 319]
}
private static void radixSort(int[] arr) {
int max = arr[0];
for (int k : arr) {
max = Math.max(max, k);
}
for (int exp = 1; max / exp > 0; exp = exp * 10) {
countingSort(arr, arr.length, exp);
}
}
private static void countingSort(int[] arr, int n, int exp) {
int[] count = new int[10];
for (int a : arr) {
count[(a / exp) % 10]++;
}
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
int[] output = new int[n];
for (int i = n - 1; i >= 0; i--) {
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}
for (int i = 0; i < n; i++) {
arr[i] = output[i];
}
}
}Advantages:
- Efficiency: Radix Sort has a time complexity of O(nk), where n is the number of elements and k is the number of digits in the largest number.
- Stability: Radix Sort is stable, meaning it maintains the relative order of equal elements.
Disadvantages:
- Space Complexity: Requires additional memory for counting arrays and output arrays.
- Applicability: Best suited for sorting numbers or fixed-length strings.
Radix Sort is particularly effective when dealing with large datasets of fixed-size keys (like integers).
j. Bucket Sort Algorithm
- Consider a situation where we have numbers uniformly distributed in the range from 1 to 10^8. Then how do we sort them efficiently?
- Consider another situation where we have floating point numbers uniformly distributed in the range from 0.0 (inclusive) to 1.0 (exclusive).
Meaning of Uniformly Distributed
What is the meaning of uniformly distributed here? When numbers are uniformly distributed, it means that each number within the specified range has an equal probability of occurring. In other words, the numbers are spread evenly across the entire range.
Imagine you have 10 numbers in the range from 1 to 100. If these numbers are uniformly distributed, you might get a list like this: 10, 20, 30, 40, 50, 60, 70, 80, 90, 100. In this list, each number is evenly spaced by 10 units apart, covering the entire range from 1 to 100.
For floating point numbers uniformly distributed in the range from 0.0 to 1.0, you might get: 0.05, 0.15, 0.25, 0.35, 0.45, 0.55, 0.65, 0.75, 0.85, 0.95. Here, each number is evenly spaced by 0.1 units, covering the entire range from 0.0 to 1.0.
This property makes Bucket Sort particularly effective, as it ensures that elements are evenly distributed into the buckets, leading to balanced and efficient sorting.
Bucket Sort
Bucket Sort is an efficient algorithm for sorting numbers that are uniformly distributed across a range. It works by dividing the data into several buckets, then individually sorting each bucket, and finally merging the sorted buckets back together.
Steps of Bucket Sort:
- Create Buckets: Divide the input data into a number of buckets. The number of buckets can be chosen based on the data or a fixed size.
- Distribute Elements: Place each element in the corresponding bucket based on a hashing function or the value range.
- Sort Each Bucket: Sort the elements in each bucket. You can use another sorting algorithm like Insertion Sort, which is efficient for small datasets.
- Concatenate Buckets: Merge all the sorted buckets to form the final sorted array.
Input Array: 20, 88, 70, 85, 75, 95, 18, 82, 60
Consider the range 0 to 99
Create buckets: 0-19, 20-39, 40-59, 60-79, 80-99
Put array elements in their appropriate bucket & sort each bucket:
Bucket 0: 18
Bucket 1: 20
Bucket 2: (empty)
Bucket 3: 60, 70, 75
Bucket 4: 82, 85, 88, 95
Join the sorted buckets:-
18, 20, 60, 70, 75, 82, 85, 88, 95
To sort each bucket we can use any standard algorithm. If we ensure that each bucket will have less number of elements then we can use insertion sort.
If the data is uniformly distributed then the only thing to do is:- put elements in the appropriate bucket, every bucket will have only 1 element, so sorting is not required, just collect them. With this, it will have O(n) time.
This algorithm might work really bad when data is not uniformly distributed. In that case, multiple buckets will have multiple elements and each bucket is going to call some standard sorting algorithm.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
public class Test {
public static void main(String[] args) {
int[] arr = { 38, 27, 43, 3, 9, 82, 10 };
bucketSort(arr, 5);
System.out.println(Arrays.toString(arr));
// [3, 9, 10, 27, 38, 43, 82]
}
private static void bucketSort(int[] arr, int bucketCount) {
if (arr.length == 0) {
return;
}
// Create buckets
ArrayList<Integer>[] buckets = new ArrayList[bucketCount];
for (int i = 0; i < bucketCount; i++) {
buckets[i] = new ArrayList<>();
}
// Determine the range
int max = arr[0], min = arr[0];
for (int i : arr) {
max = Math.max(max, i);
min = Math.min(min, i);
}
int range = max - min + 1;
// Distribute elements into buckets
for (int i : arr) {
int bucketIndex = (i - min) / (range / bucketCount);
buckets[bucketIndex].add(i);
}
// Sort each bucket and concatenate results
int idx = 0;
for (ArrayList<Integer> bucket : buckets) {
if (bucket.size() > 1) {
Collections.sort(bucket);
}
for (int i : bucket) {
arr[idx++] = i;
}
}
}
}Example Code for Floating-Point Numbers:-
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
public class Test {
public static void main(String[] args) {
float[] arr = { 0.42f, 0.32f, 0.23f, 0.52f, 0.25f, 0.47f, 0.51f };
bucketSort(arr, 10);
System.out.println(Arrays.toString(arr));
// [0.23, 0.25, 0.32, 0.42, 0.47, 0.51, 0.52]
}
private static void bucketSort(float[] arr, int bucketCount) {
if (arr.length == 0) {
return;
}
// Create buckets
ArrayList<Float>[] buckets = new ArrayList[bucketCount];
for (int i = 0; i < bucketCount; i++) {
buckets[i] = new ArrayList<>();
}
// Distribute elements into buckets
for (float i : arr) {
int bucketIndex = (int) (i * bucketCount);
buckets[bucketIndex].add(i);
}
// Sort each bucket and concatenate results
int idx = 0;
for (ArrayList<Float> bucket : buckets) {
if (bucket.size() > 1) {
Collections.sort(bucket);
}
for (float i : bucket) {
arr[idx++] = i;
}
}
}
}Time complexity:-
- Best Case: O(n + k), where k is the number of buckets. This occurs when the input data is uniformly distributed, leading to evenly filled buckets.
- Average Case: O(n + k * (log(k))), when the distribution of elements across the buckets is fairly even.
- Worst Case: O(n^2), if all elements end up in a single bucket, making Bucket Sort equivalent to performing a single sorting algorithm on the entire array. If we use insertion sort to sort individual buckets then O(n^2). If we use O(n * log n) algorithm to sort the individual buckets, then O(n * log n).
Overview of the Sorting Algorithm
In which special case, which sorting algorithm should be used:-
- Binary Array: Partition of Quick Sort (Lomuto, Hoare, Naive)
- Array with three values: Partition of Quick Sort (Lomuto, Hoare, Naive)
- Array with size N and small ranged values: Counting sort
- Array with size N and range is of size N^2 or N^3 or closer: Radix Sort
- An array of uniformly distributed data over a range: Bucket Sort
- When memory writes are costly: Selection Sort or Cycle Sort
- When only adjacent swaps are allowed: Bubble Sort. The Bubble Sort’s advanced & better version is Cocktail Sort.
- When array size is small: Insertion Sort
- When available extra memory is less (on embedded systems or small devices): Shell Sort. It takes O(n * (log n)^2).
General Purpose Sorting Algorithms (when we don’t know anything about the input data):-
- Merge Sort**
- Heap Sort
- Quick Sort
It is mathematically proven that when we don’t know anything about the input data then it will take at least O(n * log n) time to sort the data.
Merge and Quick Sort are divide-and-conquer algorithms. Merge sort is stable but Heap and Quick sort are not stable.
Hybrid Algorithms (Used in libraries):-
- TimSort in Python (Insertion Sort & Merge Sort). It uses Merge sort for general purposes, and when input becomes small in a recursive call then it uses Insertion sort.
- IntroSort in C++ library (Quick Sort, Heap Sort, and Insertion Sort). In general, it uses Quick Sort, when the Quick Sort is doing many unfair partitioning (the number of recursion calls is going beyond log n) then it switches to Heap Sort. When the array size becomes small then it uses insertion sort.
C++ also has a stable_sort() function which is internally implemented using merge sort because merge sort is a stable sorting algorithm.
If you enjoyed this post, share it with your friends. Do you want to share more information about the topic discussed above or do you find anything incorrect? Let us know in the comments. Thank you!