経緯

ソートかけないやつはダサいらしい。

俺＝ソートかけないやつ
ダサい＝モテない
俺＝モテない

\(^o^)/

そんなの嫌なので、モテたいので、ソート書く。

進め方的な

Wikipedia に載ってるやつをピックアップしてやっていく。

アルゴリズムはWikipediaを見てもよいが、できるだけ実装はみない方向で、見てもできるだけ自分で考えてやっていく。

ゆるふわに楽しくやっていこう。

実装できたものから順次更新。長い目で見てね。

進捗的な

(DONE) バブルソート
(DONE) シェーカーソート
(DONE) コムソート
(DONE) ノームソート
(DONE) 選択ソート
(DONE) 挿入ソート
(DONE) シェルソート
(DONE) 二分木ソート
(NOTYET) 図書館ソート
(DONE) マージソート
(NOTYET) In-place マージソート
(DONE) ヒープソート
(DONE) クイックソート
(DONE) イントロソート
(DONE) 奇遇転置ソート
(DONE(?)) シェアソート

テスト用プログラム

ソートした結果が正しいかをチェックするためのプログラム。速度チェックもできて一石二鳥。

main_test.go

package main

import (
	"flag"
	"fmt"
	"math/rand"
	"testing"
	"time"
)

var size = flag.Int("size", 20, "size of array")
var repeat = flag.Int("repeat", 1, "number of repeat testing")

func TestBubbleSort(t *testing.T) {
	rand.Seed(time.Now().UnixNano())
	var want []int
	for i := 0; i < *size; i++ {
		want = append(want, i)
	}

	for x := 0; x < *repeat; x++ {
		t.Run(fmt.Sprintf("size:%v,x:%v", *size, x), func(t *testing.T) {
			var tt = rand.Perm(*size)
			got := sort(tt)

			if len(got) != len(want) {
				t.Fatalf("length is different(got:%v,want:%v)", got, want)
			}

			for i := 0; i < len(got); i++ {
				if got[i] != want[i] {
					t.Fatalf("index [%v] is different:\ngot :%v\nwant:%v", i, got, want)
				}
			}
		})
	}
}

バブルソート

バブルソート (bubble sort) は、ソートのアルゴリズムの一つ。隣り合う要素の大小を比較しながら整列させること。(Wikipedia より)

流石にこれはかけそう。

main.go

package main

func sort(src []int) []int {
	for i := 0; i < len(src)-1; i++ {
		for j := 0; j < len(src)-1; j++ {
			if src[j] > src[j+1] {
				src[j+1], src[j] = src[j], src[j+1]
			}
		}
	}
	return src
}

2回書き直したのは秘密

シェーカーソート

シェーカーソート (英: shaker sort) は、ソートのアルゴリズムの一つ。バブルソートを、効率がよくなるように改良したもの。
バブルソートではスキャンを一方向にしか行わないのに対し、シェーカーソートでは交互に二方向に行う。 (Wikipedia より)

main.go

package main

func sort(src []int) []int {
	min := 0
	max := len(src) - 1
	m := 0
	for {
		for j := min; j < max; j++ {
			if src[j] > src[j+1] {
				m = j
				src[j+1], src[j] = src[j], src[j+1]
			}
		}

		if min == m {
			break
		}

		max = m

		for j := max; j > min; j-- {
			if src[j-1] > src[j] {
				m = j
				src[j-1], src[j] = src[j], src[j-1]
			}
		}

		if max == m {
			break
		}

		min = m
	}
	return src
}

これでええんやろか...なんかもっときれいに書けそうな気がする...

コムソート

挿入ソートをシェルソートに改良したときと同様の改良を施す。適当な間隔で整列後、間隔を少しずつ狭めて整列していく。

総数 n を 1.3 で割り、小数点以下を切り捨てた数を間隔 h とする。

i=0 とする。

i 番目と i+h 番目を比べ、i+h 番目が小さい場合入れ替える。

i=i+1 とし、i+h>n となるまで3を繰り返す。

hがすでに1になっている場合は入れ替えが発生しなくなるまで上の操作を繰り返す。

h を 1.3 で割り、小数点以下を切り捨てた数を新たに間隔 h とし、操作を繰り返す。

wikipedia にアルゴリズムまんま書いてた...(ええんか...)

main.go

package main

func sort(src []int) []int {
	n := len(src)
	h := n
	for {
		if h != 1 {
			h = int(float64(h) / 1.3)
		}

		change := false
		for i := 0; i+h < n; i++ {
			if src[i] > src[i+h] {
				change = true
				src[i], src[i+h] = src[i+h], src[i]
			}
		}

		if !change {
			break
		}
	}
	return src
}

ベンチマーク見てもらったらわかるけど、くそはやい。なんでこんなに早いのか全然わからんけど、ここらへんを見るに間をあけて交換するからバブルソートよりも交換回数が減って早い。みたいな話なのかな？それにしても早すぎるやろ...

ノームソート

ノームソート（英: gnome sort）はソートアルゴリズムの一種で、挿入ソートに似ているが、要素の移動は挿入ではなくバブルソートのような一連の交換で行う。(Wikipediaより)

main.go

package main

func sort(src []int) []int {
	n := len(src) - 1
	for i := 0; i < n; i++ {
		if src[i] > src[i+1] {
			src[i], src[i+1] = src[i+1], src[i]
			for j := i; j > 0; j-- {
				if src[j-1] > src[j] {
					src[j-1], src[j] = src[j], src[j-1]
				} else {
					break
				}
			}
		}
	}
	return src
}

入れ替え処理が2個に分かれちゃっててダサさ出てる。これではモテないのでは...

選択ソート

選択ソート（英: selection sort）は、ソートのアルゴリズムの一つ。配列された要素から、最大値やまたは最小値を探索し配列最後の要素と入れ替えをおこなうこと。
データ列中で一番小さい値を探し、1番目の要素と交換する。次に、2番目以降のデータ列から一番小さい値を探し、2番目の要素と交換する。これを、データ列の最後まで繰り返す(Wikipedia より)

main.go

package main

func sort(src []int) []int {
	n := len(src)
	for i := 0; i < n-1; i++ {
		for j := i + 1; j < n; j++ {
			if src[i] > src[j] {
				src[i], src[j] = src[j], src[i]
			}
		}
	}
	return src
}

一番シンプルで直感的なソート法。という感じがする。

挿入ソート

挿入ソート（インサーションソート）は、ソートのアルゴリズムの一つ。整列してある配列に追加要素を適切な場所に挿入すること。平均計算時間・最悪計算時間がともにO(n2)と遅いが、アルゴリズムが単純で実装が容易なため、しばしば用いられる。

アルゴリズム
まず0番目と1番目の要素を比較し、順番が逆であれば入れ換える。次に、2番目の要素が1番目までの要素より小さい場合、正しい順に並ぶように「挿入」する（配列の場合、前の要素を後ろに一つずつずらす）。この操作で、2番目までのデータが整列済みとなる（ただし、さらにデータが挿入される可能性があるので確定ではない）。このあと、3番目以降の要素について、整列済みデータとの比較と適切な位置への挿入を繰り返す。
(Wikipedia より)

main.go

package main

func insertionSort(src []int) []int {
	n := len(src)
	for i := 1; i < n; i++ {
		tmp := src[i]
		for j := 0; j < i; j++ {
			if src[j] > tmp {
				for k := i; k > j; k-- {
					src[k] = src[k-1]
				}
				src[j] = tmp
				break
			}
		}
	}
	return src
}

ピックアップした値と配列を比較するときに、ピックアップした場所から0番目方向に比較するのがいいのか、0番目から順番に比較すればいいのか悩んだ。はじめはピックアップした場所から0番目方向に比較してたんだけど、処理が複雑になりそうだったので、素直に0番目から比較するようにした。

シェルソート

シェルソート（改良挿入ソート、英語: Shellsort, Shell sort, Shell's method）は、in-placeな比較ソートのアルゴリズムの一種である。シェルソートは、交換によるソート（バブルソート）あるいは挿入によるソート（挿入ソート）の一般化と見なすことができる[2]。ソートの方法は、まず、間隔の離れた要素の組に対してソートを行い、だんだんと比較する要素間の間隔を小さくしながらソートを繰り返す、というものである。離れた場所の要素からソートを始めることで、単純に近くの要素を比較する場合よりも速く、要素を所定の位置に移動させることができる。(Wikipedia より)

これだけじゃわからなかったので、こちらのサイトも参考にした

一回目のコーディングでは挿入ソートより遅い実装になってて書き直した。おそらく、eとの比較を配列の頭からやってたから。(下記の実装でも、先頭からやるとgo test -size=10000 -repeat=100で8秒以上かかる。挿入ソートでは前からでも後ろからでも速度に差はなかったので、やっぱりh=1になるまでにある程度ソートされていることが効果あるってことなんだろう。)

あと、当初は間隔離したまま、ループする処理(xの処理)も初めは入れてなかったし、挿入処理(kの処理)も初めはjのループの中でやってたりと色々おかしかった。ループがネストして見にくいので、もう少し見やすくできたらいいなぁ。

main.go

package main

func shellSort(src []int) []int {
	n := len(src)
	for h := n / 2; h > 0; h /= 2 {
		for x := 0; x < h; x++ {
			for i := h + x; i < n; i += h {
				e := src[i]
				var j int
				for j = i - h; j >= x; j -= h {
					if src[j] <= e {
						break
					}
				}

				for k := i; k > j+h; k -= h {
					src[k] = src[k-h]
				}
				src[j+h] = e
			}
		}
	}
	return src
}

二分木ソート

Wikipedia にはページが無いようだったので。このページを参考にしました。

二分木を作って、小さいノードから列挙。って方法でいいのかな？

main.go

package main

import "fmt"

type binaryTree struct {
	Value int
	Left  *binaryTree
	Right *binaryTree
}

func (tree *binaryTree) Print(dup int) {
	fmt.Println("val:", tree.Value)
	if tree.Left != nil {
		for i := 0; i < dup; i++ {
			fmt.Print(" ")
		}
		fmt.Print("Left:")
		tree.Left.Print(dup + 1)
	} else {
		for i := 0; i < dup; i++ {
			fmt.Print(" ")
		}
		fmt.Print("Left:")
		fmt.Print("<nil>\n")
	}

	if tree.Right != nil {
		for i := 0; i < dup; i++ {
			fmt.Print(" ")
		}
		fmt.Print("Right:")
		tree.Right.Print(dup + 1)
	} else {
		for i := 0; i < dup; i++ {
			fmt.Print(" ")
		}
		fmt.Print("Right:")
		fmt.Print("<nil>\n")
	}
}

func (tree *binaryTree) Insert(val int) {
	if tree.Value > val {
		if tree.Left == nil {
			tree.Left = newNode(val)
		} else {
			tree.Left.Insert(val)
		}
	} else {
		if tree.Right == nil {
			tree.Right = newNode(val)
		} else {
			tree.Right.Insert(val)
		}
	}
}

func (tree *binaryTree) ToList() []int {
	var src []int

	if tree.Left != nil {
		src = tree.Left.ToList()
	}

	src = append(src, tree.Value)

	if tree.Right != nil {
		src2 := tree.Right.ToList()
		src = append(src, src2...)
	}

	return src
}

func newNode(val int) *binaryTree {
	return &binaryTree{
		Value: val,
	}
}

func binarySearchSort(src []int) []int {
	var root *binaryTree
	for _, val := range src {
		if root == nil {
			root = newNode(val)
		} else {
			root.Insert(val)
		}
	}
	return root.ToList()
}

図書館ソート

TO BE UPDATED

マージソート

既に整列してある複数個の列を1個の列にマージする際に、小さいものから先に新しい列に並べれば、新しい列も整列されている、というボトムアップの分割統治法による。大きい列を多数の列に分割し、そのそれぞれをマージする作業は並列化できる。(Wikipedia より)

main.go

package main

func mergeSort(src []int) []int {
	n := len(src)
	if n == 0 || n == 1 {
		return src
	}
	ary1 := src[0 : n/2]
	mary1 := mergeSort(ary1)
	ary2 := src[n/2:]
	mary2 := mergeSort(ary2)
	var ret []int
	i := 0
	j := 0
	for {
		if len(mary1[i:]) == 0 {
			if len(mary2[j:]) == 0 {
				break
			} else {
				ret = append(ret, mary2[j])
				j++
				continue
			}
		}

		if len(mary2[j:]) == 0 {
			ret = append(ret, mary1[i])
			i++
			continue
		}

		if mary1[i] > mary2[j] {
			ret = append(ret, mary2[j])
			j++
		} else {
			ret = append(ret, mary1[i])
			i++
		}
	}
	return ret
}

In-place マージソート

TO BE UPDATED

ヒープソート

親が必ず子よりも大きい値になるような二分木を作成し、頭から順に取り出して、取り出した後から二分木を再構築するようにすれば、頭取るだけでソートできるよね。みたいなアルゴリズム。今回は親が子よりも必ず小さい値になるようにした。大学時代のアルゴリズム本をひっぱり出してきて、答え見まくってGo言語で書き直しただけになってしまった。それでもなんかぐちゃっとしててまだまだ改善の余地がある感じ、メモリも潤沢に使いすぎじゃないですかね。。。
(追記:2018/4/13 0:51)
ポインタを渡すことで省メモリ化したけど、そんなに速度に変化がなかった。
(追記:2018/4/15 0:07)
goはスライスのポインタを渡すので、前のコードだと、ポインタのポインタが渡って言ってた模様。なので、前のコードで既にちゃんとポインタを渡せていた。ということで、元のコードに戻した。

main.go

package main

func upheap(a []int, n int) {
	if n < 1 {
		return
	}
	pn := (n+1)/2 - 1
	if a[pn] < a[n] {
		a[pn], a[n] = a[n], a[pn]
		upheap(a, pn)
	}
}

func insert(a []int, n int) {
	upheap(a, n)
}

func downheap(a []int, k int, n int) {
	v := a[k]
	var j int
	for ; k < (n+1)/2; k = j {
		j = 2*(k+1) - 1
		if j <= n-1 && a[j] < a[j+1] {
			j++
		}
		if v >= a[j] {
			break
		}
		a[k] = a[j]
	}
	a[k] = v
}

func remove(a []int, n int) {
	if n == 0 {
		return
	}

	a[0], a[n] = a[n], a[0]
	downheap(a, 0, n-1)
}

func heapSort(src []int) []int {
	for i := 0; i < len(src); i++ {
		insert(src, i)
	}
	for i := len(src) - 1; i >= 0; i-- {
		remove(src, i)
	}
	return src
}

クイックソート

ある基準点を決め、そこから右と左に分け、左には、基準よりも小さい数を置き、右には、基準よりも小さい数を置く。その後、左と右のそれぞれでソートを行う。
クイックソートには基準点を決めるフェーズと、ソートを行うフェーズとがあります。基準点を決める手順は、まず、指定された配列の右端の値を基準点とし、配列の左から順に基準点より大きい点を探します。次に、配列の右から順に基準点より小さい点を探します。両方の点を探したら、それらの値を交換します。その操作を左から走査と右からの走査が交差するまで実行し、交差したときの左からの走査の位置にある値と基準点の値を交換します。これが基準点を決めるフェーズで、基準点を元に、左と右に分割した配列を元に、再度基準点を探す走査を行うことでソートのフェーズが完了します。

main.go

package main

func sort(src []int, l, r int) {
	if l >= r {
		return
	}
	i, j := l, r-1
	for i <= j {
		for i <= r && src[i] < src[r] {
			i++
		}
		for l <= j && src[j] >= src[r] {
			j--
		}
		if i > j {
			break
		}
		src[i], src[j] = src[j], src[i]
		i++
		j--
	}
	src[r], src[i] = src[i], src[r]
	sort(src, l, i-1)
	sort(src, i+1, r)
}

func quickSort(src []int) []int {
	sort(src, 0, len(src)-1)
	return src
}

左からの走査と、右からの走査が交差する場合の場合分けが苦労した。当初は値同士の比較のみをおこなっていたが、右からの走査がout of range になってしまうので、配列の端まできたらループを抜けるようにした。
また、iとjが必ず交差するように設定しないと、値が小さいほうと基準点を交換してしまうので、そのあたりの工夫も必要。

イントロソート

クイックソートとヒープソートの混合ソートらしい、再帰の回数が、要素数の対数(log2(n))の倍数を超えた場合にヒープソートにすることで、クイックソートの短所を補ってるのかな？

main.go

package main

import "math"

func sort1(src []int, l, r, d int) {
	if l >= r {
		return
	}
	if d == 0 {
		heapSort(src[l : r+1])
		return
	}
	i, j := l, r-1
	for i <= j {
		for i <= r && src[i] < src[r] {
			i++
		}
		for l <= j && src[j] >= src[r] {
			j--
		}
		if i > j {
			break
		}
		src[i], src[j] = src[j], src[i]
		i++
		j--
	}
	src[i], src[r] = src[r], src[i]
	sort1(src, l, i-1, d-1)
	sort1(src, i+1, r, d-1)
}

func introSort(src []int) []int {
	d := math.Log2(float64(len(src)))
	sort1(src, 0, len(src)-1, int(2*d))
	return src
}

ヒープソートは依然つくったやつの使いまわし。

奇遇転置ソート

隣り合う2要素で組を作ってソートする。

要素の1番目と2番目、3番目と4番目というように偶奇で組を作りソートする
要素2番目と3番目, 4番目と5番目というように奇偶で組を作りソートする
ソートが完了するまで1, 2を繰り返す

main.go

package main

func oddEvenSort(src []int) []int {
	for {
		changed := false
		for i := 0; i+1 < len(src); i += 2 {
			if src[i] > src[i+1] {
				changed = true
				src[i], src[i+1] = src[i+1], src[i]
			}
		}
		for i := 1; i+1 < len(src); i += 2 {
			if src[i] > src[i+1] {
				changed = true
				src[i], src[i+1] = src[i+1], src[i]
			}
		}
		if !changed {
			break
		}
	}
	return src
}

Wikipediaによると並列実行できるらしいので、goroutineを使って並列化したバージョンを記載する。ただし、これを実行すると、逐次実行より遅い。goroutineの作りすぎにはご注意しましょう。(^_^;)

main.go

package main

import (
	"runtime"
	"sync"
)

func oddEvenSort2(src []int) []int {
	for {
		changed := false
		wg := &sync.WaitGroup{}
		cpu := runtime.NumCPU()
		for x := 0; x < cpu; x++ {
			wg.Add(1)
			go func(j int) {
				for i := j * 2; i+1 < len(src); i += 2 * cpu {
					if src[i] > src[i+1] {
						changed = true
						src[i], src[i+1] = src[i+1], src[i]
					}
				}
				wg.Done()
			}(x)
		}
		wg.Wait()
		for x := 0; x < cpu; x++ {
			wg.Add(1)
			go func(j int) {
				for i := j*2 + 1; i+1 < len(src); i += 2 * cpu {
					if src[i] > src[i+1] {
						changed = true
						src[i], src[i+1] = src[i+1], src[i]
					}
				}
				wg.Done()
			}(x)
		}
		wg.Wait()
		if !changed {
			break
		}
	}
	return src
}

シェアソート

一次元配列を長方形に整形して、各行、各列でソートするアルゴリズム。

以下のサンプルコードは正方形でしか動かないです。

main.go

package main

import "math"

func ssSort1(src []int, fn func(int, int) bool) {
	for i := 0; i < len(src)-1; i++ {
		for j := 0; j < len(src)-1; j++ {
			if fn(src[j], src[j+1]) {
				src[j], src[j+1] = src[j+1], src[j]
			}
		}
	}
}

func shearSort(src []int) []int {
	n := len(src)
	m := int(math.Sqrt(float64(n)))
	cnt := 2 * (int(math.Log2(float64(n))) + 1)
	for i := 0; i < int(cnt); i++ {
		for y := 0; y <= n/m; y++ {
			var fn func(int, int) bool
			if y%2 == 0 {
				fn = func(a, b int) bool {
					return a > b
				}
			} else {
				fn = func(a, b int) bool {
					return a < b
				}
			}
			var l, r int
			if (y+1)*m > n {
				l = y * m
				r = n
			} else {
				l = y * m
				r = (y + 1) * m
			}
			ssSort1(src[l:r], fn)
		}

		for x := 0; x < m; x++ {
			for y := 0; (y+1)*m+x < n; y++ {
				for z := 0; (z+1)*m+x < n; z++ {
					j := z*m + x
					if src[j] > src[j+m] {
						src[j], src[j+m] = src[j+m], src[j]
					}
				}
			}
		}
	}

	for y := 0; y <= n/m; y++ {
		var l, r int
		if (y+1)*m > n {
			l = y * m
			r = n
		} else {
			l = y * m
			r = (y + 1) * m
		}
		ssSort1(src[l:r], func(a, b int) bool {
			return a > b
		})
	}

	return src
}

オリジナルソート

golang の標準ライブラリ sortを使ったソートです。内部的にはクイックソートとヒープソートの混合らしい。

main.go

package main

import "sort"

func originalSort(src []int) []int {
	sort.Slice(src, func(i, j int) bool {
		return src[i] < src[j]
	})

	return src
}

ベンチ的な

go test --size=10000 --repeat=100 の結果

アルゴリズム	result(sec)	Note
バブルソート	14.440s	遅い...
シェーカーソート	8.116s	さすがにバブルソートよりは早い.
コムソート	0.248s	バブルソートと比較するとかなり早い.
ノームソート	3.540s	まぁまぁの速さ.
選択ソート	10.958s	感覚的にはもう少し早いかなと思ったんだけど、こんなもんか
挿入ソート	4.196s	O(n^2)らしいが、意外と早い。
シェルソート	0.302s
二分木ソート	0.431s	二分木の作成や一次元配列への変換がある割には早い
図書館ソート
マージソート	0.610s
In-place マージソート
ヒープソート	0.297s
クイックソート	0.211s
イントロソート	0.225s	純粋なクイックソートとあまり変わらない。要素数が少なすぎるのかも
奇遇転置ソート	8.386s	並列バージョンは `25.292s` でした。
シェアソート	13.966s	各行、各列のソートにクイックソートを使うと `8.345s`まで改善
オリジナル	0.264s	自前のクイックソートのほうが早いけど、おそらく最悪ケースとかで比較するとオリジナルのほうが早くなると思われる。

感想(4/5時点)

バブルソートですら2回書き直したし、シェーカーソートに至っては書いてて自分で何してるかわからなくなってきているので、今後が不安。

感想(4/8時点)

シェルソートムズイ...

感想(4/12時点)

図書館ソートにチャレンジしてるけど、まだちゃんと理解できてないので、簡単なものからやりつつ、片手間で図書館ソートのアルゴリズムを理解していく感じで。

感想(4/17時点)

クイックソートの理論は把握できるんだけど、実際に実装するとなるとコーナーケースでミスが出たりするので、まだちゃんと理解できてないんだろうなと思っている。

イントロソートのヒープソートを一から書こうかなとも思ったんだけど、手を抜いてしまった。しかも作り方を忘れてしまっていたので、一から書いたほうがよかったなと後悔。