uni

Thing1's amazing uni repo
Log | Files | Refs | Submodules

sort.go (758B)

      1 package main
      2 
      3 import (
      4 	"fmt"
      5 	"math/rand"
      6 )
      7 
      8 func makeSides[T any](arr []T, cmp func(T, T) int) ([]T, []T, T) {
      9 	var lhs, rhs []T
     10 	index := rand.Int() % len(arr)
     11 	pivot := arr[index]
     12 	for i, el := range arr {
     13 		if i == index {
     14 			continue
     15 		}
     16 
     17 		if cmp(pivot, el) <= 0 {
     18 			lhs = append(lhs, el)
     19 		} else {
     20 			rhs = append(rhs, el)
     21 		}
     22 	}
     23 	return lhs, rhs, pivot
     24 }
     25 
     26 func sort[T any](arr []T, cmp func(T, T) int) []T {
     27 	lhs, rhs, pivot := makeSides(arr, cmp)
     28 	if len(lhs) > 1 {
     29 		lhs = sort(lhs, cmp)
     30 	}
     31 	if len(rhs) > 1 {
     32 		rhs = sort(rhs, cmp)
     33 	}
     34 
     35 	out := append([]T{}, lhs...)
     36 	out = append(out, pivot)
     37 	out = append(out, rhs...)
     38 	return out
     39 }
     40 
     41 func main() {
     42 	fmt.Println(sort([]int{4, 5, 6, 2, 6, 2, 8, 9},
     43 		func(a, b int) int {
     44 			return b - a
     45 		}))
     46 }