## 2020年6月10日水曜日

### Go - Go Packages, Algorithms, and Data Structures - intスライス、クイックソートの実装

Go Systems Programming: Master Linux and Unix system level programming with Go (Mihalis Tsoukalos(著)、Packt Publishing)のChapter 4(Go Packages, Algorithms, and Data Structures)、Exercises 3.の解答を求めてみる。

コード

qsort_test.go

```package qsort

import (
"testing"
)

func eq(s1, s2 []int) bool {
if len(s1) != len(s2) {
return false
}
for i, s := range s1 {
if s != s2[i] {
return false
}
}
return true
}
func TestQsort(t *testing.T) {
gots := [][]int{
{},
{1},
{1, 2},
{2, 1},
{1, 1},
{5, 1, 4, 2, 3},
{1, 2, 3, 4, 5, 5, 4, 3, 2, 1},
{5, 4, 3, 2, 1, 1, 2, 3, 4, 5},
}
wants := [][]int{
{},
{1},
{1, 2},
{1, 2},
{1, 1},
{1, 2, 3, 4, 5},
{1, 1, 2, 2, 3, 3, 4, 4, 5, 5},
{1, 1, 2, 2, 3, 3, 4, 4, 5, 5},
}
for i, got := range gots {
want := wants[i]
tmp := make([]int, len(got))
copy(tmp, got)
qsort(got, func(i, j int) bool {
return got[i] < got[j]
})
if !eq(got, want) {
t.Errorf("qsort(%v, ...) %v, want %v", tmp, got, want)
}
}
}
```

qsort.go

```package qsort

func intPartial(intSlice []int, left, right int, less func(i, j int) bool) {
if right-left < 1 {
return
}
p := (left + right) / 2
i := left
j := right
for i < j {
for less(i, p) {
i++
}
for less(p, j) {
j--
}
if i < j {
t := intSlice[i]
intSlice[i] = intSlice[j]
intSlice[j] = t
if i == p {
p = j
i++
} else if j == p {
p = i
j--
} else {
i++
j--
}
}
}
intPartial(intSlice, left, p-1, less)
intPartial(intSlice, p+1, right, less)
}
func qsort(slice interface{}, less func(i, j int) bool) bool {
intSlice, ok := slice.([]int)
if ok {
intPartial(intSlice, 0, len(intSlice)-1, less)
return true
}
return false
}
```

```% go test
--- FAIL: TestQsort (0.00s)
qsort_test.go:47: qsort([2 1], ...) [2 1], want [1 2]
qsort_test.go:47: qsort([5 1 4 2 3], ...) [5 1 4 2 3], want [1 2 3 4 5]
qsort_test.go:47: qsort([1 2 3 4 5 5 4 3 2 1], ...) [1 2 3 4 5 5 4 3 2 1], want [1 1 2 2 3 3 4 4 5 5]
qsort_test.go:47: qsort([5 4 3 2 1 1 2 3 4 5], ...) [5 4 3 2 1 1 2 3 4 5], want [1 1 2 2 3 3 4 4 5 5]
FAIL
exit status 1
FAIL _/Users/…/ch4/qsort 0.211s
% go test
PASS
ok   _/Users/…/ch4/qsort 0.212s
% go test -v
=== RUN   TestQsort
--- PASS: TestQsort (0.00s)
PASS
ok   _/Users/…/ch4/qsort 0.050s
%
```