Quick Sort

Question 1

Quick Sort Definition

Answer 1

An algorithm that moves smaller elements to the left of a pivot and larger elements to the right. Then recursively divides the array in 2 partitions

Question 2

Quick Sort complexity

Answer 2

Time : Best case O(n log(n))
Worst case O(n^2) if the array is a
already sorted.

Space: O(log(n)) due to recursion

Question 3

Quick sort Function

Answer 3

private static void quickSort(int[] array, int start, int end) {
if(end <= start) return;

        int pivot = partition(array, start, end);

        quickSort(array,start,pivot-1);
        quickSort(array,pivot +1, end);
}

Question 4

QS Helper Partition Function

Answer 4

private static int partition(int[] array, int start, int end) {
int pivot = array[end];
int i = start -1;

    for(int j = start; j<= end-1; j++){
        if(array[j]  < pivot){
            i++;
            swap(array,i ,j);
        }
    }
    i++;
    swap(array,i ,end);
    return i;
}

Question 5

QS Step1

Answer 5

Implement the base case
if(end <= start) return;

Then declare pivot variable that calls the helper class:
int pivot = partition(array, start, end);

Then implement recursion:
quickSort(array,start,pivot-1);
quickSort(array,pivot +1, end);

Question 6

QS Step 2

Answer 6

Declare relevant variables for the pivot and indices:
int pivot = array[end];
int i = start -1;

Using a for loop and nested if statement do the comparison and swap:
for(int j = start; j<= end-1; j++){
if(array[j] < pivot){
i++;
swap(array,i ,j);
}
}

Too ensure everything has been compared increment i and do a final swap afte the for loop before returning i:
i++;
swap(array,i ,end);
return i;