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

Go Systems Programming:
Master Linux and Unix
system level programming with Go
楽天ブックス 紀伊國屋書店

開発環境

• macOS Catalina - Apple (OS)
• Emacs (Text Editor)
• Windows 10 Pro (OS)
• Visual Studio Code (Text Editor)
• Go (プログラミング言語)

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
}

入出力結果(Zsh、PowerShell、Terminal)

% 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
%