Quick Sorting and Goang Implementation

Quick sort

Quick Sorting Thought

Quick sorting selects a base element pivot from an array by the idea of branching, moves the smaller pivot in the array to the left and the larger pivot to the right. Then the left and right arrays are sorted quickly.

Bilateral Circulation Method

thinking

Set two pointers, left and right, initially pointing to the left and right ends of the array. Compare the right pointer to the element and pivot element. If the right element is larger than the pivot element, the right pointer moves one bit to the left and then compares with the pivot. If the right element is smaller than the pivot element, stop moving and switch to the left pointer.
The operation of the left pointer is to compare the elements pointed by the left pointer with pivot elements. If the left pointer is less than or equal to pivot, the left pointer moves to the right, and if the left element is larger than pivot element, stop moving.
When both left and right stop moving, exchange the elements pointed by left and right, so that the left pointer points to an element smaller than pivot, and right points to an element larger than pivot.
When the left and right overlap, the comparison is finished. The first element is exchanged with the left and right pointing elements to complete a round of sorting.

Code

func partition(arr []int, startIndex, endIndex int) int {
    var (
        pivot = arr[startIndex]
        left  = startIndex
        right = endIndex
    )

    for left != right {
        for left < right && pivot < arr[right] {
            right--
        }

        for left < right && pivot >= arr[left] {
            left++
        }

        if left < right {
            arr[left], arr[right] = arr[right], arr[left]
        }
    }

    arr[startIndex], arr[left] = arr[left], arr[startIndex]

    return left
}

Unilateral cyclic method

thinking

Unilateral loop code is simple to implement.
A mark pointer is used to point to the last element of a set less than pivot. Finally, the first element is exchanged with the element pointed by mark for the next round.
The mark pointer starts pointing to the first element, and then starts traversing the array. If the current element is larger than pivot, continue traversing. If it is smaller than pivot, the mark pointer moves right, swapping the mark pointing to the element and the current traversing element.

Code

func partitionv2(arr []int, startIndex, endIndex int) int {
    var (
        mark  = startIndex
        pivot = arr[startIndex]
        point = startIndex + 1
    )

    for point < len(arr) {
        if arr[point] < pivot {
            mark++
            arr[mark], arr[point] = arr[point], arr[mark]
        }
        point++
    }

    arr[startIndex], arr[mark] = arr[mark], arr[startIndex]
    return mark
}

pivot selection

There are arrays 5, 4, 3, 2, 1 to be sorted. If the first element is selected as pivot, each selection is the maximum or minimum value in the array. Each sorting only determines the location of one element, resulting in time complexity degenerating to O(n^2).
When choosing pivot, we can choose it by random selection, that is, to select an element randomly as pivot in the current array, so as to reduce the probability of choosing the maximum or minimum value.

Non-recursive method

thinking

Replace recursion with loops and stacks. The stacks in the following code are implemented by themselves.

Code

func QuickSortNonRecursive(arr []int, startIndex, endIndex int) {
    var (
        s     = v1.NewStack()
        m     = make(map[string]int)
        start = "start_index"
        end   = "end_index"

    )
    m[start] = startIndex
    m[end] = endIndex
    s.Push(m)
    for !s.IsEmpty() {
        param := s.Pop().(map[string]int)
        pivotIndex := partitionv2(arr, param[start], param[end])
        if param[start] < pivotIndex-1 {
            leftParam := make(map[string]int)
            leftParam[start] = param[start]
            leftParam[end] = pivotIndex - 1
            s.Push(leftParam)
        }
        if param[end] > pivotIndex+1 {
            rightParam := make(map[string]int)
            rightParam[start] = pivotIndex + 1
            rightParam[end] = param[end]
            s.Push(rightParam)
        }
    }
}

summary

All code

package sort

import (
    v1 "xiawan/algorithm/stack/v1"
)

func QuickSort(arr []int, startIndex, endIndex int) {
    if startIndex >= endIndex {
        return
    }

    pivotIndex := partitionv2(arr, startIndex, endIndex)
    QuickSort(arr, startIndex, pivotIndex-1)
    QuickSort(arr, pivotIndex+1, endIndex)
}

//Bilateral cycle, starting on the right
func partition(arr []int, startIndex, endIndex int) int {
    var (
        pivot = arr[startIndex]
        left  = startIndex
        right = endIndex
    )

    for left != right {
        for left < right && pivot < arr[right] {
            right--
        }

        for left < right && pivot >= arr[left] {
            left++
        }

        if left < right {
            arr[left], arr[right] = arr[right], arr[left]
        }
    }

    arr[startIndex], arr[left] = arr[left], arr[startIndex]

    return left
}

//Unilateral cycle
func partitionv2(arr []int, startIndex, endIndex int) int {
    var (
        mark  = startIndex
        pivot = arr[startIndex]
        point = startIndex + 1
    )

    for point < len(arr) {
        if arr[point] < pivot {
            mark++
            arr[mark], arr[point] = arr[point], arr[mark]
        }
        point++
    }

    arr[startIndex], arr[mark] = arr[mark], arr[startIndex]
    return mark
}

func QuickSortNonRecursive(arr []int, startIndex, endIndex int) {
    var (
        s     = v1.NewStack()
        m     = make(map[string]int)
        start = "start_index"
        end   = "end_index"

    )
    m[start] = startIndex
    m[end] = endIndex
    s.Push(m)
    for !s.IsEmpty() {
        param := s.Pop().(map[string]int)
        pivotIndex := partitionv2(arr, param[start], param[end])
        if param[start] < pivotIndex-1 {
            leftParam := make(map[string]int)
            leftParam[start] = param[start]
            leftParam[end] = pivotIndex - 1
            s.Push(leftParam)
        }
        if param[end] > pivotIndex+1 {
            rightParam := make(map[string]int)
            rightParam[start] = pivotIndex + 1
            rightParam[end] = param[end]
            s.Push(rightParam)
        }
    }
}

Tags: Go less

Posted on Thu, 29 Aug 2019 02:25:16 -0700 by blue-genie