QuickSort In Java
- Divide and Conquer Strategy
- Space required is less as compared to other sorting algorithms
- Not Stable
- Best Case Time Complexity: O(n log n)
- Worst Case Time Complexity: O(n^2)
- Space Complexity: O(n log n)
class QuickSortInJava { /* The main function that implements QuickSortInJava() arr[] --> Array to be sorted, low --> Starting index (min. is 0), high --> Ending index (max. is n-1)*/ void sort(int arr[], int low, int high) { if (low < high) { /* correctPivotPos is index of pivot at its correct position i.e. arr[correctPivotPos] */ int correctPivotPos = partition(arr, low, high); // Recursively sort numbers sort(arr, low, correctPivotPos-1); // Left Partition ( low <--> pivotIndex - 1) sort(arr, correctPivotPos+1, high); // Right Partition ( pivotIndex + 1 <--> high) } } /* Pivot = last element of array. The pivot is placed at its correct position in sorted array and the numbers smaller than pivot are in left half of the partition and numbers greater than pivot are in right half of the partition */ int partition(int arr[], int low, int high) { int pivot = arr[high]; // pivot is last element of array int i = (low-1); // index of smaller element for (int j=low; j<high; j++) // for loop : low <- to -> high { // If current element is smaller than or // equal to pivot if (arr[j] <= pivot) { i++; // since i = low - 1 // swap arr[i] and arr[j] int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } // Middle Position (i+1) number is swapped with Pivot Position (high) number int temp = arr[i+1]; arr[i+1] = arr[high]; arr[high] = temp; return i+1; // return position of pivot (middle) } /* A utility function to print array of size n */ static void printArray(int arr[]) { int n = arr.length; for (int i=0; i<n; ++i) System.out.print(arr[i]+" "); System.out.println(); } public static void main(String args[]) { int arr[] = {10, 7, 8, 9, 1, 5}; int n = arr.length; QuickSortInJava obj = new QuickSortInJava(); obj.sort(arr, 0, n-1); System.out.println("Sorted:"); printArray(arr); } } /* OUTPUT: Sorted: 1 5 7 8 9 10 */ QuickSort Analysis
public class QuickSortAnalysis { /* The main function that implements QuickSortInJava() arr[] --> Array to be sorted, low --> Starting index (min. is 0), high --> Ending index (max. is n-1)*/ void sort(int arr[], int low, int high) { System.out.println("--------------------------"); System.out.println("(INDEX) "+ low + " < " + high + " ? "); System.out.println("--------------------------"); if (low < high) { /* correctPivotPos is index of pivot at its correct position i.e. arr[correctPivotPos] */ int correctPivotPos = partition(arr, low, high); printArray(arr); // Recursively sort numbers System.out.println("(INDEX) Sorting: " + low + " <----> " + (correctPivotPos-1)); sort(arr, low, correctPivotPos-1); // Left Partition ( low <--> pivotIndex - 1) System.out.println("(INDEX) Sorting: " + (correctPivotPos+1) + " <----> " + high); sort(arr, correctPivotPos+1, high); // Right Partition ( pivotIndex + 1 <--> high) } } /* Pivot = last element of array. The pivot is placed at its correct position in sorted array and the numbers smaller than pivot are in left half of the partition and numbers greater than pivot are in right half of the partition */ int partition(int arr[], int low, int high) { int pivot = arr[high]; // pivot is last element of array int i = (low-1); // index of smaller element for (int j=low; j<high; j++) // for loop : low <- to -> high { // If current element is smaller than or // equal to pivot if (arr[j] <= pivot) { i++; // since i = low - 1 // swap arr[i] and arr[j] System.out.println("SWAPPING: " + arr[i] + " with " + arr[j]); int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } // Middle Position (i+1) number is swapped with Pivot Position (high) number int temp = arr[i+1]; arr[i+1] = arr[high]; arr[high] = temp; return i+1; // return position of pivot (middle) } /* A utility function to print array of size n */ static void printArray(int arr[]) { int n = arr.length; System.out.println("***************"); for (int i=0; i<n; ++i) System.out.print(arr[i]+" "); System.out.println(); System.out.println("***************"); } public static void main(String args[]) { int arr[] = {10, 7, 8, 9, 1, 5}; int n = arr.length; QuickSortInJava obj = new QuickSortInJava(); obj.sort(arr, 0, n-1); System.out.println("Sorted:"); printArray(arr); } } /* OUTPUT: -------------------------- (INDEX) 0 < 5 ? -------------------------- SWAPPING: 10 with 1 *************** 1 5 8 9 10 7 *************** (INDEX) Sorting: 0 <----> 0 -------------------------- (INDEX) 0 < 0 ? -------------------------- (INDEX) Sorting: 2 <----> 5 -------------------------- (INDEX) 2 < 5 ? -------------------------- *************** 1 5 7 9 10 8 *************** (INDEX) Sorting: 2 <----> 1 -------------------------- (INDEX) 2 < 1 ? -------------------------- (INDEX) Sorting: 3 <----> 5 -------------------------- (INDEX) 3 < 5 ? -------------------------- *************** 1 5 7 8 10 9 *************** (INDEX) Sorting: 3 <----> 2 -------------------------- (INDEX) 3 < 2 ? -------------------------- (INDEX) Sorting: 4 <----> 5 -------------------------- (INDEX) 4 < 5 ? -------------------------- *************** 1 5 7 8 9 10 *************** (INDEX) Sorting: 4 <----> 3 -------------------------- (INDEX) 4 < 3 ? -------------------------- (INDEX) Sorting: 5 <----> 5 -------------------------- (INDEX) 5 < 5 ? -------------------------- Sorted: *************** 1 5 7 8 9 10 *************** */