Summary: Comparing Sorting Algorithms
Below is a simple table that provides a comparison of sorting algorithms in terms of their average-case time complexity, worst-case time complexity, best-case time complexity, space complexity, and whether they are stable or not.
| Algorithm | Average Case Time | Worst Case Time | Best Case Time | Space Complexity | Stability |
|---|---|---|---|---|---|
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Quick Sort | O(n log n) | O(n^2) | O(n log n) | O(log n) | No |
| Bubble Sort | O(n^2) | O(n^2) | O(n) | O(1) | Yes |
| Selection Sort | O(n^2) | O(n^2) | O(n^2) | O(1) | No |
| Insertion Sort | O(n^2) | O(n^2) | O(n) | O(1) | Yes |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
| Bucket Sort | O(n + k) | O(n^2) | O(n+k) | O(n+k) | Yes |
| Radix Sort | O(nk) | O(nk) | O(nk) | O(n+k) | Yes |
| Shell Sort | O(n log n) | O(n^2) | O(n) | O(1) | No |
| Counting Sort | O(n + k) | O(n + k) | O(n + k) | O(n + k) | Yes |
Note:
- n is the number of elements in the array.
- k is the range of input.
- The values provided here are generalized and can vary based on the specific variant of the algorithm and the type of data they are applied to.
- Stability refers to the maintenance of relative order of equal elements. A sorting algorithm is said to be stable if the relative order of equivalent items remains unchanged after sorting.
Related Article: How to Use the aria-label Attribute in HTML
Merge Sort
Merge Sort is a popular sorting algorithm in Java that follows the divide-and-conquer approach. It divides the input array into two halves, sorts them separately, and then merges them back to obtain the sorted array. The algorithm has a time complexity of O(n log n), making it efficient for large data sets.
Here is an example of the Merge Sort algorithm implemented in Java:
public class MergeSort {
public void merge(int[] arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int[] leftArr = new int[n1];
int[] rightArr = new int[n2];
for (int i = 0; i < n1; ++i)
leftArr[i] = arr[left + i];
for (int j = 0; j < n2; ++j)
rightArr[j] = arr[mid + 1 + j];
int i = 0, j = 0;
int k = left;
while (i < n1 && j < n2) {
if (leftArr[i] <= rightArr[j]) {
arr[k] = leftArr[i];
i++;
} else {
arr[k] = rightArr[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = leftArr[i];
i++;
k++;
}
while (j < n2) {
arr[k] = rightArr[j];
j++;
k++;
}
}
public void sort(int[] arr, int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
sort(arr, left, mid);
sort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
public static void main(String[] args) {
int[] arr = {5, 2, 8, 12, 7};
MergeSort mergeSort = new MergeSort();
mergeSort.sort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
}
In the above example, we have an array [5, 2, 8, 12, 7]. The sort method is called with the array and the indices of the leftmost and rightmost elements. The sort method recursively divides the array into smaller subarrays until the base case is reached (when left is less than right). Then, the merge method merges the sorted subarrays back together to obtain the final sorted array [2, 5, 7, 8, 12].
Quick Sort
Quick Sort is another widely used sorting algorithm in Java that also follows the divide-and-conquer approach. It selects a pivot element, partitions the array into two subarrays based on the pivot, and recursively sorts the subarrays. The algorithm has an average time complexity of O(n log n).
Here is an example of the Quick Sort algorithm implemented in Java:
public class QuickSort {
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 void sort(int[] arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
sort(arr, low, pi - 1);
sort(arr, pi + 1, high);
}
}
public static void main(String[] args) {
int[] arr = {5, 2, 8, 12, 7};
QuickSort quickSort = new QuickSort();
quickSort.sort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
}
In the above example, we have an array [5, 2, 8, 12, 7]. The sort method is called with the array and the indices of the leftmost and rightmost elements. The sort method recursively partitions the array based on a pivot element and sorts the subarrays. The partition method selects the last element as the pivot and rearranges the array such that all elements smaller than the pivot are placed on the left side, and all elements greater than or equal to the pivot are placed on the right side. The pivot element is then placed at its correct position in the sorted array. After the recursive calls, the final sorted array is [2, 5, 7, 8, 12].
Bubble Sort
Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The algorithm continues to iterate through the list until no more swaps are needed, indicating that the list is sorted. Bubble Sort has a worst-case time complexity of O(n^2).
Here is an example of the Bubble Sort algorithm implemented in Java:
public class BubbleSort {
public void sort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
public static void main(String[] args) {
int[] arr = {5, 2, 8, 12, 7};
BubbleSort bubbleSort = new BubbleSort();
bubbleSort.sort(arr);
System.out.println(Arrays.toString(arr));
}
}
In the above example, we have an array [5, 2, 8, 12, 7]. The sort method is called with the array. The outer loop runs for n-1 iterations, where n is the length of the array. The inner loop compares adjacent elements and swaps them if they are in the wrong order. After each pass of the inner loop, the largest element is bubbled up to its correct position. After completing all the iterations, the final sorted array is [2, 5, 7, 8, 12].
Related Article: Troubleshooting 502 Bad Gateway Nginx
Selection Sort
Selection Sort is a simple sorting algorithm that works by repeatedly finding the minimum element from the unsorted part of the array and putting it at the beginning. The algorithm maintains two subarrays: the sorted subarray and the unsorted subarray. Selection Sort has a worst-case time complexity of O(n^2).
Here is an example of the Selection Sort algorithm implemented in Java:
public class SelectionSort {
public void sort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
public static void main(String[] args) {
int[] arr = {5, 2, 8, 12, 7};
SelectionSort selectionSort = new SelectionSort();
selectionSort.sort(arr);
System.out.println(Arrays.toString(arr));
}
}
In the above example, we have an array [5, 2, 8, 12, 7]. The sort method is called with the array. The outer loop runs for n-1 iterations, where n is the length of the array. In each iteration, the minimum element from the unsorted part of the array is found and swapped with the element at the beginning of the unsorted part. After completing all the iterations, the final sorted array is [2, 5, 7, 8, 12].
Insertion Sort
Insertion Sort is a simple sorting algorithm that builds the final sorted array one item at a time. It iterates through the array and for each iteration, it compares the current element with the elements before it and inserts it in its correct position. Insertion Sort has a worst-case time complexity of O(n^2).
Here is an example of the Insertion Sort algorithm implemented in Java:
public class InsertionSort {
public void sort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; 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;
}
}
public static void main(String[] args) {
int[] arr = {5, 2, 8, 12, 7};
InsertionSort insertionSort = new InsertionSort();
insertionSort.sort(arr);
System.out.println(Arrays.toString(arr));
}
}
In the above example, we have an array [5, 2, 8, 12, 7]. The sort method is called with the array. The outer loop iterates through the array starting from the second element. For each iteration, the current element is compared with the elements before it and inserted in its correct position by shifting the elements greater than the current element to the right. After completing all the iterations, the final sorted array is [2, 5, 7, 8, 12].
Heap Sort
Heap Sort is a comparison-based sorting algorithm that uses a binary heap data structure. It first builds a max heap from the input array and then repeatedly extracts the maximum element from the heap and places it at the end of the array. Heap Sort has a worst-case time complexity of O(n log n).
Here is an example of the Heap Sort algorithm implemented in Java:
public class HeapSort {
public void sort(int[] arr) {
int n = arr.length;
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
for (int i = n - 1; i >= 0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
}
public void heapify(int[] arr, int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
heapify(arr, n, largest);
}
}
public static void main(String[] args) {
int[] arr = {5, 2, 8, 12, 7};
HeapSort heapSort = new HeapSort();
heapSort.sort(arr);
System.out.println(Arrays.toString(arr));
}
}
In the above example, we have an array [5, 2, 8, 12, 7]. The sort method is called with the array. The first loop builds a max heap from the input array by calling the heapify method. The heapify method organizes the array into a max heap by comparing the current element with its children and swapping if necessary. After building the max heap, the second loop repeatedly extracts the maximum element from the heap (the root of the heap) and places it at the end of the array. The heapify method is called to maintain the max heap property after each extraction. After completing all the iterations, the final sorted array is [2, 5, 7, 8, 12].
Related Article: How to Do Sorting in C++ & Sorting Techniques
Bucket Sort
Bucket Sort is a sorting algorithm that works by distributing the elements of an array into a number of buckets, and then sorting each bucket individually. It requires prior knowledge of the range of the input elements and is most effective when the elements are uniformly distributed. Bucket Sort has an average time complexity of O(n+k), where n is the number of elements and k is the number of buckets.
Here is an example of the Bucket Sort algorithm implemented in Java:
import java.util.ArrayList;
import java.util.Collections;
public class BucketSort {
public void sort(int[] arr, int bucketSize) {
int min = arr[0];
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] < min) {
min = arr[i];
} else if (arr[i] > max) {
max = arr[i];
}
}
int numBuckets = (max - min) / bucketSize + 1;
ArrayList<ArrayList<Integer>> buckets = new ArrayList<>(numBuckets);
for (int i = 0; i < numBuckets; i++) {
buckets.add(new ArrayList<>());
}
for (int i = 0; i < arr.length; i++) {
int bucketIndex = (arr[i] - min) / bucketSize;
buckets.get(bucketIndex).add(arr[i]);
}
int currentIndex = 0;
for (int i = 0; i < numBuckets; i++) {
Collections.sort(buckets.get(i));
for (int j = 0; j < buckets.get(i).size(); j++) {
arr[currentIndex++] = buckets.get(i).get(j);
}
}
}
public static void main(String[] args) {
int[] arr = {5, 2, 8, 12, 7};
BucketSort bucketSort = new BucketSort();
bucketSort.sort(arr, 3);
System.out.println(Arrays.toString(arr));
}
}
In the above example, we have an array [5, 2, 8, 12, 7]. The sort method is called with the array and the bucket size (3 in this case). The minimum and maximum values in the array are determined. The number of buckets is calculated based on the range of the input elements and the bucket size. An ArrayList of ArrayLists is created to represent the buckets. Each element in the array is distributed into the appropriate bucket based on its value. The elements within each bucket are then sorted individually. Finally, the sorted elements from each bucket are concatenated back into the original array. After completing all the steps, the final sorted array is [2, 5, 7, 8, 12].
Radix Sort
Radix Sort is a non-comparative sorting algorithm that sorts integers by sorting them digit by digit. It works by distributing the input elements into a number of buckets based on their least significant digit, then sorting the elements based on the next significant digit, and so on, until all the digits have been considered. Radix Sort has a time complexity of O(kn), where n is the number of elements and k is the maximum number of digits.
Here is an example of the Radix Sort algorithm implemented in Java:
import java.util.Arrays;
public class RadixSort {
public void sort(int[] arr) {
int max = getMax(arr);
for (int exp = 1; max / exp > 0; exp *= 10) {
countSort(arr, exp);
}
}
public int getMax(int[] arr) {
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}
public void countSort(int[] arr, int exp) {
int n = arr.length;
int[] output = new int[n];
int[] count = new int[10];
Arrays.fill(count, 0);
for (int i = 0; i < n; i++) {
count[(arr[i] / exp) % 10]++;
}
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
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];
}
}
public static void main(String[] args) {
int[] arr = {5, 2, 8, 12, 7};
RadixSort radixSort = new RadixSort();
radixSort.sort(arr);
System.out.println(Arrays.toString(arr));
}
}
In the above example, we have an array [5, 2, 8, 12, 7]. The sort method is called with the array. The maximum value in the array is determined using the getMax method. The outer loop runs for the number of digits in the maximum value. The countSort method is called for each digit position (exp). The countSort method performs counting sort on the array based on the current digit position. It counts the frequency of occurrence of each digit in the array, calculates the cumulative count array, and uses it to determine the correct position of each element in the output array. Finally, the sorted array is copied back to the original array. After completing all the iterations, the final sorted array is [2, 5, 7, 8, 12].
Shell Sort
Shell Sort is an extension of Insertion Sort that sorts elements at a specific interval. It starts by sorting pairs of elements far apart from each other, then progressively reduces the interval between elements to be compared until the interval becomes 1, at which point the algorithm becomes equivalent to Insertion Sort. Shell Sort has an average time complexity of O(n^2), but it performs better than Insertion Sort for large arrays.
Here is an example of the Shell Sort algorithm implemented in Java:
public class ShellSort {
public void sort(int[] arr) {
int n = arr.length;
for (int gap = n / 2; gap > 0; gap /= 2) {
for (int i = gap; i < n; i++) {
int temp = arr[i];
int j;
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
arr[j] = arr[j - gap];
}
arr[j] = temp;
}
}
}
public static void main(String[] args) {
int[] arr = {5, 2, 8, 12, 7};
ShellSort shellSort = new ShellSort();
shellSort.sort(arr);
System.out.println(Arrays.toString(arr));
}
}
In the above example, we have an array [5, 2, 8, 12, 7]. The sort method is called with the array. The outer loop initializes the gap value to half of the array length and reduces it by half in each iteration. The inner loop starts from the gapth element and compares it with the elements before it, shifting the elements greater than the current element to the right. The inner loop continues until the current element is smaller than the element at a gap distance before it. After completing all the iterations, the final sorted array is [2, 5, 7, 8, 12].
Related Article: How to Use JSON Parse and Stringify in JavaScript
Counting Sort
Counting Sort is an integer sorting algorithm that works by determining, for each input element, the number of elements that are less than it. It then uses this information to place the element in its correct position in the sorted output array. Counting Sort has a time complexity of O(n+k), where n is the number of elements and k is the range of input values.
Here is an example of the Counting Sort algorithm implemented in Java:
import java.util.Arrays;
public class CountingSort {
public void sort(int[] arr) {
int n = arr.length;
int max = getMax(arr);
int[] count = new int[max + 1];
int[] output = new int[n];
for (int i = 0; i < n; i++) {
count[arr[i]]++;
}
for (int i = 1; i <= max; i++) {
count[i] += count[i - 1];
}
for (int i = n - 1; i >= 0; i--) {
output[count[arr[i]] - 1] = arr[i];
count[arr[i]]--;
}
for (int i = 0; i < n; i++) {
arr[i] = output[i];
}
}
public int getMax(int[] arr) {
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}
public static void main(String[] args) {
int[] arr = {5, 2, 8, 12, 7};
CountingSort countingSort = new CountingSort();
countingSort.sort(arr);
System.out.println(Arrays.toString(arr));
}
}
In the above example, we have an array [5, 2, 8, 12, 7]. The sort method is called with the array. The maximum value in the array is determined using the getMax method. An array count of size max + 1 is created to store the frequency of occurrence of each value in the input array. The count array is then modified to store the cumulative count of each value. The output array is initialized to store the sorted elements. The input array is iterated from right to left, and each element is placed in its correct position in the output array based on its count in the count array. Finally, the sorted array is copied back to the original array. After completing all the steps, the final sorted array is [2, 5, 7, 8, 12].
Maintaining a Sorted Subarray in Insertion Sort
Insertion Sort is a simple sorting algorithm that builds the final sorted array one item at a time. It iterates through the array and for each iteration, it compares the current element with the elements before it and inserts it in its correct position. One of the key steps in Insertion Sort is maintaining a sorted subarray.
Here is an example of how the sorted subarray is maintained in the Insertion Sort algorithm implemented in Java:
public class InsertionSort {
public void sort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; 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;
}
}
public static void main(String[] args) {
int[] arr = {5, 2, 8, 12, 7};
InsertionSort insertionSort = new InsertionSort();
insertionSort.sort(arr);
System.out.println(Arrays.toString(arr));
}
}
In the above example, we have an array [5, 2, 8, 12, 7]. The sort method is called with the array. The outer loop iterates through the array starting from the second element. For each iteration, the current element is compared with the elements before it and inserted in its correct position by shifting the elements greater than the current element to the right. The while loop runs as long as there are elements greater than the current element that need to be shifted. After inserting the current element in its correct position, the sorted subarray is extended by one element. This process continues until all elements have been inserted in the sorted subarray. After completing all the iterations, the final sorted array is [2, 5, 7, 8, 12].
Time Complexity of Merge Sort
The time complexity of Merge Sort is O(n log n), where n is the number of elements in the input array.
Merge Sort follows the divide-and-conquer approach, which involves dividing the input array into two halves, sorting them separately, and then merging them back to obtain the sorted array.
The algorithm divides the array into two halves in each recursive call until the base case is reached (when the array size becomes 1). The division process takes O(log n) time, as it repeatedly divides the array in half.
The merging process, which is performed after the recursive calls, takes O(n) time. During merging, the algorithm compares and merges the elements from the two sorted subarrays, resulting in the final sorted array. The merging process requires iterating through each element of the array once.
Since the array is divided into halves in each recursive call, the number of recursive calls is proportional to the height of the binary tree representing the recursive calls. The height of the binary tree is log n, where n is the number of elements in the array.
Therefore, the time complexity of Merge Sort can be calculated as O(n log n), where n is the number of elements in the input array.
Here is an example of the Merge Sort algorithm implemented in Java:
public class MergeSort {
public void merge(int[] arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int[] leftArr = new int[n1];
int[] rightArr = new int[n2];
for (int i = 0; i < n1; ++i)
leftArr[i] = arr[left + i];
for (int j = 0; j < n2; ++j)
rightArr[j] = arr[mid + 1 + j];
int i = 0, j = 0;
int k = left;
while (i < n1 && j < n2) {
if (leftArr[i] <= rightArr[j]) {
arr[k] = leftArr[i];
i++;
} else {
arr[k] = rightArr[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = leftArr[i];
i++;
k++;
}
while (j < n2) {
arr[k] = rightArr[j];
j++;
k++;
}
}
public void sort(int[] arr, int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
sort(arr, left, mid);
sort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
public static void main(String[] args) {
int[] arr = {5, 2, 8, 12, 7};
MergeSort mergeSort = new MergeSort();
mergeSort.sort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
}
In the above example, we have an array [5, 2, 8, 12, 7]. The sort method is called with the array and the indices of the leftmost and rightmost elements. The sort method recursively divides the array into smaller subarrays until the base case is reached (when left is less than right). Then, the merge method merges the sorted subarrays back together to obtain the final sorted array [2, 5, 7, 8, 12]. The time complexity of this implementation is O(n log n).
Related Article: How to Implement Min Heap Binary Trees
Pivot Element Selection in Quick Sort
Quick Sort is a widely used sorting algorithm in Java that follows the divide-and-conquer approach. It selects a pivot element, partitions the array into two subarrays based on the pivot, and recursively sorts the subarrays. The choice of the pivot element plays a crucial role in the efficiency of the algorithm.
There are several approaches to select the pivot element in Quick Sort, each with its own advantages and disadvantages. Some common approaches include:
1. Choosing the first element as the pivot:
int pivot = arr[left];
This approach is simple and straightforward but may result in poor performance if the input array is already sorted or almost sorted.
2. Choosing the last element as the pivot:
int pivot = arr[right];
This approach is also simple and straightforward but suffers from similar issues as choosing the first element as the pivot.
3. Choosing the middle element as the pivot:
int pivot = arr[(left + right) / 2];
This approach aims to select a pivot element that is close to the median of the array. It can yield better performance than choosing the first or last element as the pivot, especially for arrays that are partially sorted or contain many duplicates.
4. Choosing a random element as the pivot:
int pivotIndex = left + (int) (Math.random() * (right - left + 1)); int pivot = arr[pivotIndex];
This approach randomly selects an element from the array as the pivot. It helps to avoid worst-case scenarios and provides good average performance.
5. Choosing the median of three elements as the pivot:
int mid = (left + right) / 2;
if (arr[left] > arr[mid]) {
int temp = arr[left];
arr[left] = arr[mid];
arr[mid] = temp;
}
if (arr[left] > arr[right]) {
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
if (arr[mid] > arr[right]) {
int temp = arr[mid];
arr[mid] = arr[right];
arr[right] = temp;
}
int pivot = arr[mid];
This approach selects the median of the first, middle, and last elements as the pivot. It aims to choose a pivot that is likely to divide the array into two equal halves. This approach provides good performance in most cases.
The choice of the pivot element can significantly affect the performance of Quick Sort. In practice, various pivot selection strategies are used based on the characteristics of the input data. Some implementations even switch to other sorting algorithms like Insertion Sort for small subarrays to reduce the overhead of recursive calls.
Here is an example of the Quick Sort algorithm with the pivot element randomly selected implemented in Java:
public class QuickSort {
public int partition(int[] arr, int low, int high) {
int pivotIndex = low + (int) (Math.random() * (high - low + 1));
int pivot = arr[pivotIndex];
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 void sort(int[] arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
sort(arr, low, pi - 1);
sort(arr, pi + 1, high);
}
}
public static void main(String[] args) {
int[] arr = {5, 2, 8, 12, 7};
QuickSort quickSort = new QuickSort();
quickSort.sort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
}
In the above example, we have an array [5, 2, 8, 12, 7]. The sort method is called with the array and the indices of the leftmost and rightmost elements. The partition method randomly selects an element from the array as the pivot and partitions the array into two subarrays based on the pivot. The pivot element is then placed at its correct position in the sorted array. The sort method recursively sorts the subarrays until the base case is reached. The time complexity of this implementation is O(n log n).
Additional Resources
Best Java Sort Algorithm for Large Data Sets