Quick Sort is a highly efficient sorting algorithm based on the divide-and-conquer strategy. It works by selecting a “pivot” element from the array and partitioning the other elements into two sub-arrays according to whether they are less than or greater than the pivot. The sub-arrays are then recursively sorted.
Here’s a step-by-step explanation of the Quick Sort algorithm:
1. Choose a Pivot: Select a pivot element from the array. This pivot element can be chosen randomly, or it can be the first, last, or middle element of the array.
2. Partitioning: Rearrange the array so that all elements with values less than the pivot come before the pivot, and all elements with values greater than the pivot come after it. After this partitioning, the pivot is in its final sorted position.
3. Recursively Sort Sub-arrays: Recursively apply the above steps to the sub-array of elements with smaller values and the sub-array of elements with greater values.
4. Combine: Since the sub-arrays are sorted in place, no additional work is needed to combine them.
Here’s an example of the Quick Sort algorithm implemented in Java:
import java.util.Arrays;
public class QuickSortExample {
public static void quickSort(int[] array, int low, int high) {
if (low < high) {
int partitionIndex = partition(array, low, high);
quickSort(array, low, partitionIndex - 1);
quickSort(array, partitionIndex + 1, high);
}
}
public static int partition(int[] array, int low, int high) {
int pivot = array[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (array[j] < pivot) {
i++;
swap(array, i, j);
}
}
swap(array, i + 1, high);
return i + 1;
}
public static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
public static void main(String[] args) {
int[] array = {7, 2, 1, 6, 8, 5, 3, 4};
System.out.println("Original Array: " + Arrays.toString(array));
quickSort(array, 0, array.length - 1);
System.out.println("Sorted Array: " + Arrays.toString(array));
}
}
In this implementation:
– `quickSort()` is the main sorting function that takes the array, the lowest index (usually 0), and the highest index as parameters.
– `partition()` function selects the pivot and partitions the array around it.
– `swap()` function swaps two elements in the array.
– The `main()` function demonstrates the usage of Quick Sort by sorting an example array.