QuickSort
unknown
java
5 months ago
4.0 kB
6
Indexable
public class QuickNaive { public static void main(String[] args) { int[] arrr = {9,2,4,51,2,3,7,84,2,4,10,21}; // quickSortAsc(arrr, 0, arrr.length-1); quickSortDesc(arrr, 0, arrr.length-1); printArray(arrr); } static int partitionAsc(int arr[], int low, int high){ int pivot = arr[high]; // pivot choice last element 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; } } // move pivot arr[high] = arr[i+1]; arr[i+1] = pivot; return i+1; } static void quickSortAsc(int arr[], int low, int high){ if(low < high) { // Base case coy int pivot = partitionAsc(arr, low, high); // D&Q quickSortAsc(arr, low, pivot-1); quickSortAsc(arr, pivot+1, high); } } static int partitionDesc(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; } } // move pivot arr[high] = arr[i+1]; arr[i+1] = pivot; return i+1; } static void quickSortDesc(int arr[], int low, int high){ if(low < high){ int pivot = partitionDesc(arr, low, high); // D&Q quickSortDesc(arr, low, pivot-1); quickSortDesc(arr, pivot+1, high); } } static void printArray(int arr[]){ for(int a : arr){ System.out.print(a + " "); } System.out.println(); } } public class QuickLomuto { public static void main(String[] args) { int[] arrr = {9,2,4,51,2,3,7,84,2,4,10,21}; quickSort(arrr, 0, arrr.length-1); printArray(arrr); } static void quickSort(int arr[], int low, int high){ if(low < high){ int pivot = lomutoPartition(arr, low, high); quickSort(arr, low, pivot-1); quickSort(arr, pivot+1, high); } } static int lomutoPartition(int arr[], int low, int high){ int pivot = arr[high]; int i = low; for(int j = low;j<high;j++){ if(arr[j] < pivot){ int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; i++; } } // int pivpos = ++i; int temp = arr[i]; arr[i] = arr[high]; arr[high] = temp; return i; } static void printArray(int arr[]){ for(int a : arr){ System.out.print(a + " "); } System.out.println(); } } public class QuickHoare { public static void main(String[] args) { int[] arrr = {9,2,4,51,2,3,7,84,2,4,10,21}; quickSort(arrr, 0, arrr.length-1); printArray(arrr); } static void quickSort(int arr[], int low, int high){ if(low < high){ int pivot = hoare(arr, low, high); quickSort(arr, low, pivot-1); quickSort(arr, pivot+1, high); } } static int hoare(int arr[], int low, int high){ int pivot = arr[low]; int i = low-1; int j = high+1; while(true){ do { i++; } while (arr[i] < pivot); do { j--; } while (arr[j] > pivot); if(i >= j){ return j; } int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } static void printArray(int arr[]){ for(int a : arr){ System.out.print(a + " "); } System.out.println(); } }
Editor is loading...
Leave a Comment