QuickSort Notes - GoMani/algorithms GitHub Wiki
First step:
Choose pivot
- Simple rule : choose the index high as pivot
- Partition by pivot
// start and end are index postion
partition(int[] arr, int start,int end){
// Set i the position where the smallest element last inserted or
// we can point to position where we want to insert the next small element
int i=start-1;
int pivot=arr[end];
for(int j=start;j < end;j++){
if(arr[j] <= pivot) {
i++;
swap(arr[j],arr[i]);
}
}
// Step 2 bring the pivot to the right position
swap(arr[end],arr[i+1]);
// return pivot index
return i+1;
}
- based on pivot partition the array
quickSort(int[] array, int start, int end) {
if(start < end) {
int pivotIndex= partition(array,start,end);
quickSort(array,start,pivotIndex-1);
quickSort(array,pivotIndex+1,end);
}
}