You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
47 lines
1.0 KiB
Go
47 lines
1.0 KiB
Go
package main
|
|
|
|
/*
|
|
* Quick sort - https://en.wikipedia.org/wiki/Quicksort
|
|
*/
|
|
|
|
import "math/rand"
|
|
|
|
func quick_sort(arr []int) []int {
|
|
|
|
if len(arr) <= 1 {
|
|
return arr
|
|
}
|
|
|
|
median := arr[rand.Intn(len(arr))]
|
|
|
|
low_part := make([]int, 0, len(arr))
|
|
high_part := make([]int, 0, len(arr))
|
|
middle_part := make([]int, 0, len(arr))
|
|
|
|
for _, item := range arr {
|
|
switch {
|
|
case item < median:
|
|
low_part = append(low_part, item)
|
|
case item == median:
|
|
middle_part = append(middle_part, item)
|
|
case item > median:
|
|
high_part = append(high_part, item)
|
|
}
|
|
}
|
|
|
|
low_part = quick_sort(low_part)
|
|
high_part = quick_sort(high_part)
|
|
|
|
low_part = append(low_part, middle_part...)
|
|
low_part = append(low_part, high_part...)
|
|
|
|
return low_part
|
|
}
|
|
|
|
//func main() {
|
|
// arr := utils.RandArray(10)
|
|
// fmt.Println("Initial array is:", arr)
|
|
// fmt.Println("")
|
|
// fmt.Println("Sorted array is: ", quick_sort(arr))
|
|
//}
|