// Takes an array, along with the left and right indexes // Partitions it and then recursively calls itself on // left and right halfs of array. public static int[] quickSort(int[] data, int left, int right){ if (left < right) { int i = partition(data,left,right); quickSort(data, left, i - 1); quickSort(data, i + 1 , right); } return data; } public static int partition(int[] data, int left, int right){ // Select a pivot value in the right most index int pivot = data[right]; int i = left; int temp; for (int j = left; j < right; j++) { if (data[j] < pivot) { // Swap i with j, increment i temp = data[i]; data[i] = data[j]; data[j] = temp; i++; } } // Move pivot to last index "i" temp = data[i]; data[i] = data[right]; data[right] = temp; return i; }
Posted: March 20, 2023
Return to the snippets listing