go-sort - 解答

スタック実装

package gosort

type Stack struct {
    data []int
}

func NewStack(numbers []int) *Stack {
    data := make([]int, len(numbers))
    copy(data, numbers)
    return &Stack{data: data}
}

func (s *Stack) Push(n int) {
    s.data = append([]int{n}, s.data...)
}

func (s *Stack) Pop() int {
    if len(s.data) == 0 {
        return 0
    }
    n := s.data[0]
    s.data = s.data[1:]
    return n
}

func (s *Stack) Len() int {
    return len(s.data)
}

操作実装

type Stacks struct {
    A, B *Stack
    ops  []string
}

func (s *Stacks) Sa() {
    if s.A.Len() < 2 {
        return
    }
    s.A.data[0], s.A.data[1] = s.A.data[1], s.A.data[0]
    s.ops = append(s.ops, "sa")
}

func (s *Stacks) Pa() {
    if s.B.Len() == 0 {
        return
    }
    s.A.Push(s.B.Pop())
    s.ops = append(s.ops, "pa")
}

func (s *Stacks) Pb() {
    if s.A.Len() == 0 {
        return
    }
    s.B.Push(s.A.Pop())
    s.ops = append(s.ops, "pb")
}

func (s *Stacks) Ra() {
    if s.A.Len() < 2 {
        return
    }
    first := s.A.data[0]
    s.A.data = append(s.A.data[1:], first)
    s.ops = append(s.ops, "ra")
}

ソートアルゴリズム

func Sort(numbers []int) []string {
    s := &Stacks{
        A: NewStack(numbers),
        B: NewStack(nil),
    }

    n := s.A.Len()

    switch n {
    case 0, 1:
        return nil
    case 2:
        return sort2(s)
    case 3:
        return sort3(s)
    default:
        return sortLarge(s)
    }
}

func sort3(s *Stacks) []string {
    a := s.A.data
    if a[0] > a[1] && a[1] < a[2] && a[0] < a[2] {
        s.Sa()
    } else if a[0] > a[1] && a[1] > a[2] {
        s.Sa()
        s.Rra()
    } else if a[0] > a[1] && a[1] < a[2] && a[0] > a[2] {
        s.Ra()
    } else if a[0] < a[1] && a[1] > a[2] && a[0] < a[2] {
        s.Sa()
        s.Ra()
    } else if a[0] < a[1] && a[1] > a[2] && a[0] > a[2] {
        s.Rra()
    }
    return s.ops
}

func sortLarge(s *Stacks) []string {
    // 基数ソートまたはチャンクベースのアルゴリズム
    // 実装は省略
    return s.ops
}