【Golang】Sleep Sortを実装してみた

TL;DR

Sleep Sortなるものを（今更）知ったので、Go言語で書いてみました。

Sleep Sortとは

画期的（？）なソートアルゴリズム「Sleep Sort」 - 濃縮還元オレンジニュース
sleep sort の解説 - Qiita

ソースコード

sleepsort.go

package main

import(
  "fmt"
  "time"
)

func main() {
  numList := []int{12, 27, 46, 23, 30, 6, 38, 43, 19, 11}
  fmt.Printf("numList:\t%d\n", numList)
  sortedList := make([]int, 0, 10)

  start := make(chan struct{})
  for _, num := range numList {
    go func(n int) {
      <- start
      time.Sleep(time.Duration(n) * time.Millisecond)
      sortedList = append(sortedList, n)
    }(num)
  }

  close(start)
  for {
    if len(numList) == len(sortedList){
      fmt.Printf("sortedList:\t%d\n", sortedList)
      return
    }
  }
}

実行結果

numList:    [12 27 46 23 30 6 38 43 19 11]
sortedList: [6 11 12 19 23 27 30 38 43 46]

　そもそも

やはりですが、他にも実装している人がいました。
【ネタ】Go言語 で Sleep Sort - Qiita
Sleep sort in Go
調べてから書きましょう（戒め）

工夫点

記事にするか迷ったのですが、channelを使用して並行処理を一斉開始するように工夫したので投稿しました。

sleepsort.go

//channelの作成（種類はどうでもいい）
start := make(chan struct{})
  for _, num := range numList {
    go func(n int) {
      //全ての並行処理の準備が終わり、開始されるのを待つ
      <- start
      time.Sleep(time.Duration(n) * time.Millisecond)
      sortedList = append(sortedList, n)
    }(num)
  }

  //並行処理の開始
  close(start)

つまづきポイント

Gopherには当たり前だとは思いますが、記事の内容そのままハマりました。
Goのforとgoroutineでやりがちなミスとたった一つの冴えたgo vetと - Qiita
今回は関数内の処理が少ないので、「無名関数で引数を宣言し、実行時に値を渡す」方式にしました。

まとめ

「他の要素と比較しない」のにソートされるというのが新鮮でした。
しかも、発表（？）されたのが2000年後半以降というのがまた。