This article provides an overview of different sorting algorithms, focusing on both comparative and non-comparative methods. It includes practical examples of Quick Sort using Lomuto and Hoare partition schemes, highlighting their efficiency and use cases in various applications.
Alexander S. Ricciardi
September 17th, 2024
In computing science, different types of sorting algorithms are used, see Table 1 and Table 2. They are a fundamental component for organizing data, which is often a prerequisite step before the data can be processed, searched, or optimized for algorithms in various applications uses.
Table 1
Comparative Sorting Algorithms
Note: In Java comparative sorting of both primitive data (via algorithms) and user-defined data is implemented through the Comparable or Comparator interfaces. From “Sorting Cheat Sheet” by evanescesn09 (2019). Modify.
Table 2
Non-Comparative Sorting Algorithms
Below is an example of implementing a Quick Sort algorithm.
This algorithm is often implemented by E-commerce businesses to filter products by price, viewing items from the lowest to highest cost or vice versa. Quick Sort is well suited for this kind of scenario, especially when dealing with a large number of products.
Figure 1
Quick Sort
Note: From “Data Structures and Algorithms Cheat Sheet” by Elhannat (n.d.) Modify.
The code below is an implementation in Java of a Quick Sort algorithm sorting prices in ascending order.
/**
* Implements a QuickSort algorithm for sorting an array of prices (doubles)
*/
public class QuickSortPrices {
// ----------------------------------------------------------------------------
/*---------------------
| Partition Method |
---------------------*/
/**
* Divides the array into two parts: one part with elements smaller than or
* equal to the pivot and another with elements larger than the pivot elements
* smaller than or equal to the pivot are moved to the left of elements larger
* than the pivot are moved to the right
*
* @param prices The array of doubles to be partitioned
* @param low The starting index of the portion of the array to be
* partitioned
* @param high The ending index of the portion of the array to be
* partitioned.
* @return The index of the pivot element after partitioning
*/
public static int partition(double[] prices, int low, int high) {
// The last element in the array becomes the pivot
double pivot = prices[high];
// i keeps track of the index where smaller elements than the pivot should
go
// set to low - 1, which means no smaller element has been found yet
int i = low - 1;
// Iterate from the 'low' index to 'high - 1' (excluding the pivot)
for (int j = low; j < high; j++) {
// If smaller than or equal to the pivot, it is moved
// to the part of the array that holds smaller elements
if (prices[j] <= pivot) {
i++;
// Swap prices[i] and prices[j]
double temp = prices[i];
prices[i] = prices[j];
prices[j] = temp;
}
}
// Swap the pivot element (prices[high]) with the element at i+1
double temp = prices[i + 1];
prices[i + 1] = prices[high];
prices[high] = temp;
// Return the index of the pivot element. This index is used to divide the
array
// into two parts to implement further recursive sort
return i + 1;
}
// ----------------------------------------------------------------------------
/*------------------------
| QuickSort algorithm |
------------------------*/
/**
* QuickSort algorithm is a recursive method that sorts an array by dividing
* using a pivot
*
* @param prices The array of doubles to be sorted
* @param low The starting index of the portion of the array to be sorted
* @param high The ending index of the portion of the array to be sorted
*/
public static void quickSort(double[] prices, int low, int high) {
int pivotIndex; // Stores the pivot index
// Check if the portion if low is less than high
if (low < high) { // ----- Base case low is not < than high ------
// ----- Recursive Base -----
// Divides the array around a pivot
// Returns the index of the pivot element
pivotIndex = partition(prices, low, high);
// --- Recursion call to < than the pivot
// Recursive call to a subarray of elements that are smaller than th
// pivot
quickSort(prices, low, pivotIndex - 1); // Once low is not < than
high,
// it exists and the next
// recursion call to > than
// the pivot
// --- Recursion call to > than the pivot
// Recursively apply quicksort on the subarray of elements that are
// larger than the pivot
quickSort(prices, pivotIndex + 1, high);
}
}
// ----------------------------------------------------------------------------
}import java.util.Arrays;
public class Main {
public static void main(String[] args) {
// Example of product prices
double[] productPrices = { 199.99, 49.99, 349.95, 5.99, 20.00, 89.99, 150.00 };
System.out.println("\nProduct prices before sorting: " +
Arrays.toString(productPrices));
QuickSortPrices.quickSort(productPrices, 0, productPrices.length - 1);
System.out.println("Product prices after sorting: " +
Arrays.toString(productPrices));
}
}Output
Note that two partition schemes can be used to partition before recursively sorting the Lomuto Partition scheme and the Hoare partition scheme.
The example above uses the Lomuto Partition scheme. The scheme chooses the last element as the pivot, then uses a single (left or right) index to partition the array into elements less than or equal to the pivot and greater than the pivot.
On the other hand, the Hoare partition scheme uses the first element of the segment as the pivot, then moves two indices towards each other until swap conditions are met, see code example below:
import java.util.Arrays;
public class Main {
public static void quickSort(int[] array, int start, int end) {
if (start < end) {
int pivot = array[low]; // The pivot element starting index
int left = low - 1; // Start left index just before the segment
int right = high + 1; // Start right index just after the segment
}
}
private static int partition(int[] array, int start, int end) {
int pivot = array[start + (end - start) / 2];
int left = start - 1;
int right = end + 1;
while (true) {
// Move the left pointer to the right as long as the elements are < than
the pivot
do {
left++;
} while (array[left] < pivot);
// Move the right pointer to the left as long as the elements are > than
the pivot
do {
right--;
} while (array[right] > pivot);
// If the two pointers meet, return the partition point
if (left >= right) {
return right;
}
// Swap elements that are out of order with respect to the pivot
int temp = array[left];
array[left] = array[right];
array[right] = temp;
}
}
public static void main(String[] args) {
int[] data = {8, 7, 2, 1, 0, 9, 0};
System.out.println("Unsorted Array: " + Arrays.toString(data));
quickSort(data, 0, data.length - 1);
System.out.println("Sorted Array: " + Arrays.toString(data));
}
}In some aspects, this scheme is more efficient than Lomuto’s scheme, because it minimizes the number of swaps when compared to the Lomuto one.
The first example using the Lomuto partition schema, on the other hand, chooses the last element as the pivot, then uses a single (left or right) index to partition the array into elements less than or equal to the pivot and greater than the pivot.
The table below gives a detailed comparison of both schemes.
Table 1
Hoare's vs Lomuto Partition
Note: From "Hoare’s vs Lomuto partition scheme in QuickSort" by Educative (n.d.)
Both partition schemes have a time complexity of O(n) because in both scenarios the array of elements needs to be traversed at least once.
When adding the recursive aspect of the sort Quick Sort, both sorts have a time complexity of O(n log n). However, if the elements in the array were already sorted my Lomuto Quick Sort implementation will degrade to an O(n²) time complexity because it is using the last element in the array as a pivot.
The Quick Sort with a Hoare partition will also have a time complexity O(n²) with a fully sorted array. Nonetheless, it will perform better than the Lomuto scheme with partially sorted arrays because instead of using a single index to swap it utilizes two indices towards each other until swap conditions are met
To summarize, Quick Sort is efficient with large datasets, its time complexity is O(n log n) which is better than algorithms such as Bubble Sort or Selection Sort which have a time complexity of O(n²). Additionally, it operates in-place, meaning that it uses minimal memory O(1), which is crucial when handling large datasets.
No one algorithm fits all applications. For example, in the shipping industry where linked lists are used, even though having the same time complexity as Quick Sort, O(n log n), Merge Sort outperformed it. This is because Merge Sort is more suited for linked lists, as it doesn’t require random access to elements, unlike Quick Sort, which relies on indexes to access elements.
Another example is small and nearly sorted data. In this senior insertion is better suited as its time complexity is in a best-case situation O(n) when the data is already sorted. However, in unsorted large data sets its worst-case time complexity is O(n²).
In conclusion, in computing science, different types of sorting algorithms are used. No one algorithm fits all applications and the choice of which sorting algorithm to use depends on factors such as dataset size, data structure, and whether the data is already partially sorted.
References:
Elhannat, K. (n.d.). Data structures and slgorithms cheat sheet. Zero to Mastery. https://zerotomastery.io/cheatsheets/data-structures-and-algorithms-cheat-sheet/#contents
evanescesn09 (2019, August 17). Sorting cheat sheet [PDF]. Cheatography. https://cheatography.com/evanescesn09/cheat-sheets/sorting/pdf/?last=1566081837