Quick Sort in Go

QuickSort

• Divide and conquer algorithm
• After determining the pivot, the position of the pivot is confirmed and aligned
• Quicksort has many variations based on pivot.
• When comparing numbers, the pivot is the standard.
• The speed varies depending on the position of the pivot.
• There are left pivot, right pivot, middle pivot, and random pivot.
• O(n²) in the worst case
• Range, Criteria, Compare, Swap

quickSort

C

void quickSort(int arr[], intl, int r){
    if (l < r) {
        int p = partition(arr, l, r);

        quickSort(arr, l, p -1);
        quickSort(arr, p+1, r);
   }
}

Go

func quickSort(arr []int, l, r int){
    if l < r {
        p := partition(arr, l, r)

        quickSort(arr, l, p-1)
        quickSort(arr, p+1, r)
   }
}

• It takes 3 parameters. Array, left, right.
• Since it is a recursive function, there is a termination condition.
• Left must be less than right.
• Array will be seperated until l and r are same.
• It means element will be only one in array.

Partition

C

int partition (int arr[], int l, int r){  
    int pivot = arr[r];      // pivot
    int i = (l - 1);


    for(int j = l; j <= r-1; j++){

        if(arr[j] <= pivot){
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[r]);
    return (i + 1);
}

Go

func partition (arr []int, l, r int) {
    pivot := arr[r]        // pivot
    i := (l - 1)

    for  j := l; j <= r-1; j++ {

        if arr[j] <= pivot {
            i++
            arr[i], arr[j] = arr[j], arr[i]
        }
    }
    arr[i + 1], arr[r] = arr[r], arr[i + 1]
    return i + 1
}

• This function is responsible for conquering.
• It also takes 3 parameters. Array, left, right.
• This code will select right as pivot.
• i is l minus 1.
• In for loop, j will have l value.
• Because pivot is r, so for loop condition is until r - 1.
• While looping, if condition checks j is same or less than pivot.
• So j is same or less than pivot, i will increase and swap i and j.
• It looks like small number is moving to left.
• also i looks like saying how many small or same numbers this array has.
• When for loop ends, last swap will happen(i +1 and r).
• i shows here is the less numbers than pivot.
• End return i + 1. pivot will be return.
• We don't know based on i+1 it was arranged or not. but we know left arrays is less or same and right arrays is bigger.

After partition

• code ran one time, pivot location will be saved to p.
• Arriving at the recursive function call
• First recursive function takes array, left and before pivot array.
• And starts arranging numbers until the element will be one.
• After arranging left of pivot code, right of pivot code works.

https://youtu.be/cWH49IKDIiI

Summary

1. divided into division and conquest
2. After setting the pivot, quicksort left, quicksort right
3. Various pivot selection methods -> Various quick sort
4. Time Complexity
   • worst O(n²)
   • Average O(n log n)
   • Best O(n log n)