135 lines
2.4 KiB
Go
135 lines
2.4 KiB
Go
// Sorting algorithms. May also contain deduplication operations.
|
|
package sort
|
|
|
|
import (
|
|
"context"
|
|
"fmt"
|
|
)
|
|
|
|
// Merge too already sorted and deduplicated lists.
|
|
func MergeLists(l []int, r []int) []int {
|
|
n := []int{}
|
|
|
|
i := 0
|
|
j := 0
|
|
for {
|
|
if i == len(l) && j == len(r) {
|
|
break
|
|
} else if i == len(l) {
|
|
n = append(n, r[j:]...)
|
|
break
|
|
} else if j == len(r) {
|
|
n = append(n, l[i:]...)
|
|
break
|
|
}
|
|
|
|
if l[i] < r[j] {
|
|
n = append(n, l[i])
|
|
i++
|
|
} else if l[i] > r[j] {
|
|
n = append(n, r[j])
|
|
j++
|
|
} else if l[i] == r[j] {
|
|
n = append(n, l[i])
|
|
i++
|
|
j++
|
|
}
|
|
}
|
|
|
|
return n
|
|
}
|
|
|
|
// Mergesorts and deduplicates the list.
|
|
func SortedAndDedup(ctx context.Context, list []int) (res []int, err error) {
|
|
sorted, err := Mergesort(ctx, list)
|
|
if err != nil {
|
|
return nil, err
|
|
}
|
|
|
|
deduped := dedupSortedList(sorted)
|
|
return deduped, nil
|
|
}
|
|
|
|
// Deduplicate the sorted list and return a new one with a potentially different
|
|
// size.
|
|
func dedupSortedList(list []int) []int {
|
|
newList := []int{}
|
|
if len(list) <= 1 {
|
|
return list
|
|
}
|
|
var prev int = list[0]
|
|
newList = append(newList, list[0])
|
|
for i := 1; i < len(list); i++ {
|
|
if prev != list[i] {
|
|
newList = append(newList, list[i])
|
|
}
|
|
prev = list[i]
|
|
}
|
|
|
|
return newList
|
|
}
|
|
|
|
// Mergesorts the given list and returns it as a result. The input list
|
|
// is not modified.
|
|
// The algorithm is a bottom-up iterative version and not explained
|
|
// in detail here.
|
|
func Mergesort(ctx context.Context, list []int) (res []int, err error) {
|
|
newList := append([]int{}, list...)
|
|
temp := append([]int{}, list...)
|
|
n := len(newList)
|
|
|
|
for m := 1; m < (n - 1); m = 2 * m {
|
|
for i := 0; i < (n - 1); i += 2 * m {
|
|
select {
|
|
case <-ctx.Done():
|
|
return nil, fmt.Errorf("Sorting timed out")
|
|
default:
|
|
}
|
|
from := i
|
|
mid := i + m - 1
|
|
to := min(i+2*m-1, n-1)
|
|
|
|
merge(ctx, newList, temp, from, mid, to)
|
|
}
|
|
}
|
|
|
|
return newList, nil
|
|
}
|
|
|
|
// The merge part of the mergesort.
|
|
func merge(ctx context.Context, list []int, temp []int, from int, mid int, to int) {
|
|
k := from
|
|
i := from
|
|
j := mid + 1
|
|
|
|
for i <= mid && j <= to {
|
|
if list[i] < list[j] {
|
|
temp[k] = list[i]
|
|
i++
|
|
} else {
|
|
temp[k] = list[j]
|
|
j++
|
|
}
|
|
k++
|
|
}
|
|
|
|
for i <= mid && i < len(temp) {
|
|
temp[k] = list[i]
|
|
i++
|
|
k++
|
|
}
|
|
|
|
for i := from; i <= to; i++ {
|
|
list[i] = temp[i]
|
|
}
|
|
}
|
|
|
|
// Get the minimum of two integers.
|
|
func min(l int, r int) int {
|
|
if l < r {
|
|
return l
|
|
} else {
|
|
return r
|
|
}
|
|
}
|