quick sort


See On Github

Data

Contributor

Generic placeholder thumbnail

by jcla1

in go

Source Code

package quickSort

import "math/rand"

func QuickSort(arr []int) []int {
	if len(arr) < 2 {
		return arr
	}

	pivotIndex := rand.Intn(len(arr))
	pivot := arr[pivotIndex]

	arr = append(arr[:pivotIndex], arr[pivotIndex+1:]...)
	less, greater := make([]int, 0), make([]int, 0)

	for _, v := range arr {
		if v < pivot {
			less = append(less, v)
		} else {
			greater = append(greater, v)
		}
	}

	// Merge the recursively sorted slices back together
	return append(append(QuickSort(less), pivot), QuickSort(greater)...)
}
package quickSort

import "testing"

func TestQuickSort(t *testing.T) {
	arrs := [][]int{[]int{-2, 1, -3, 4, -1, 2, 1, -5, 4}, []int{2, 3, 7, -5, -1, 4, -10}}

	var result []int

	for _, arr := range arrs {
		result = QuickSort(arr)
		if !isSorted(result) {
			t.Errorf("QuickSort(%v) = %v", arr, result)
		}
	}
}

func isSorted(arr []int) bool {
	for i := 1; i < len(arr); i++ {
		if arr[i-1] > arr[i] {
			return false
		}
	}

	return true
}