I'm attempting to write a quicksort function in java that receives an unsorted array, and returns the same array sorted. This algorithm is supposed to call itself until the entire array is sorted. the base case would be when the subarray range is just 1 element. As long as the subarray isn't 1, we keep calling quicksort on both ends of the partition
Currently, my code returns the following
Example: [5,2,3,1] Expected output: [1,2,3,5] Output: [3,2,3,5]
Can someone please help me spot the error? Thank you!
This is my code:
class Solution {
public int[] sortArray(int[] nums) {
return quickSort(nums, 0, nums.length-1);
}
// 1. recursive method
public int[] quickSort(int[] arr, int start, int end){
// recurse: if array is more than one element, quicksort both left and right partitions
// get pivot
if (end-start >= 1) {
int partition = sort(arr, start, end);
quickSort(arr, start, partition);
quickSort(arr, partition+1, end);
}
return arr;
}
// 2. swap method
public void swap(int[] arr, int a, int b){
int temp = arr[a];
arr[a] = b;
arr[b] = temp;
}
// 3. find pivot method
public int findPivot(int min, int max){
int random_int = (int)Math.floor(Math.random()*(max-min+1)+min);
return random_int;
}
/* 4. sorting method
finds pivot value, places it to the end of the range
compares each element in the range to the pivot value and swaps the items
with the pivot index if the items are less than the pivot value, then moves pivot index to the right
at the end of the loop, all items less than pivot are to the left of the pivot index
end of loop: swap pivot index with pivot (currently at the right end of the range)
method returns pivot index
5. 8. 2. 3
s/pI p
*/
public int sort(int[] arr, int start, int end){
// find pivot value
int pivot = findPivot(start, end);
// place pivot at the end of the sorting range
swap(arr, end, pivot);
// pivot index starts out at the start
int pivotIndex = start;
// loop through start to (end -1) and make appropriate swaps
for (int i= start; i<= end-1; i++){
if (arr[i] < arr[end]) { // comparing current and pivot (pivot is in start)
// swap with pivot index, increase pivot index
swap (arr, i, pivotIndex);
pivotIndex++;
}
}
// once loop is done, swap pivot index with pivot
swap(arr, pivotIndex, end);
return pivotIndex;
}
}
First of all in swap
method you put index of b
instead of b
value into a
position