hkucuk

Shell Sort GoLang İmplementasyonu

29 Şubat 2020 • ☕️ 6 dk okuma • 🏷 bilgisayar, yazılım, sıralama


Shell Sort(Kabuk Sıralama) temel olarak Insertion Sort(Araya Sokma Sıralaması)‘nın bir varyasyonudur. Insertion Sort’da bir eleman sadece yanındaki elemanlarla sırayla karşılaştırılır. Bundan dolayı bir elemanın bulunduğu pozisyona çok uzak bir noktaya gidebilmesi için birçok karşılaştırma yapılması gerekir. Shell Sort birbirine uzak elemanların önceden karşılaştırılmasına ve yer değiştirmesine izin vererek verim sağlamaya çalışır. Sıralamayı aynı dizi üzerinde yapar, Insertion Sort gibi fazladan yer ihtiyacı yoktur.

Shell Sort’un çalışma mantığını bir örnek üzerinden inceleyelim.

Sıralanacak dizimiz şu olsun:

6, 8, 9, 4, 5, 7, 9, 11, 12, 2, 1, 3

Shell Sort’ta ilk olarak gap’ler belirlenir. Gap denilen şey kaç tane sütün oluşturulacağının belirlenmesidir. Burada gap’in 4 olarak seçildiğini düşünelim.

6, 8, 9, 4, 
5, 7, 9, 11, 
12, 2, 1, 3

Gap’ler belirlendikten sonra her sütün kendi arasında sıralanır.

5, 2, 1, 3, 
6, 7, 9, 4, 
12, 8, 9, 11

Sıralama işleminden sonra tüm sütünlar bir araya getirilir.

5, 2, 1, 3, 6, 7, 9, 4, 12, 8, 9, 11

Yukarıdaki aşama tekrar uygulanır. Fakat bu defa gap bir öncekinin yarısı olarak seçilir. Gap = 4 / 2 = 2.

5, 2, 
1, 3, 
6, 7, 
9, 4, 
12, 8, 
9, 11

Sütünlar tekrar kendi arasında sıralanır:

1, 2, 
5, 3, 
6, 4, 
9, 7, 
9, 8, 
12, 11

Sütünlar tekrar bir araya getirilir:

1, 2, 5, 3, 6, 4, 9, 7, 9, 8, 12, 11

Son olarak yukarıdaki aşama 1’lik gap’ler ile tekrarlanır ve bu şekilde de sıralı diziye ulaşılmış olur.

1, 2, 3, 4, 5, 6, 7, 8, 9, 9, 11, 12

Yukarıdaki örneğin GoLang’de uygulanmış halini aşağıdan inceleyebilirsiniz.

package main

import (
	"fmt"
)

func main() {
	array := []int{6, 8, 9, 4, 5, 7, 9, 11, 12, 2, 1, 3}
	ShellSort(array)
	fmt.Println(array)
}

func ShellSort(array []int) {
	for gap := len(array) / 2; gap > 0; gap /= 2 {
		for i := gap; i < len(array); i++ {
			x := array[i]
			j := i
			for ; j >= gap && array[j-gap] > x; j -= gap {
				array[j] = array[j-gap]
			}
			array[j] = x
		}
	}
}

Kodun çalışır halini test etmek için => RUN


Shell Sort’un çalışma hızını test etmek için daha kapsamlı bir algoritma örneğini de aşağıdan incelenebilir.

shell.go

package main

import (
	"sort"
)

// https://en.wikipedia.org/wiki/Shellsort
func ShellSort(s sort.Interface) {

	delta := s.Len()

	for delta > 1 {
		delta = int(float32(delta) * 0.5)

		for i := delta; i < s.Len(); i++ {
			it := i
			var j int

			for j = i; (j >= delta) && (s.Less(it, j-delta)); j -= delta {
				if j == it {
					it = j - delta
				} else if (j - delta) == it {
					it = j
				}
				s.Swap(j, j-delta)
			}

			s.Swap(j, it)
		}
	}
}

shell_test.go

package main

import "testing"

func TestShellSort(t *testing.T) {
	s := NewRandom(20, 7)
	ShellSort(s)
}

func BenchmarkShellSort(b *testing.B) {
	BenchAlgorithm(b, ShellSort)
}

helper_test.go

package main

import (
	"fmt"
	"math/rand"
	"sort"
	"testing"
)

type SortType []uint

func (a SortType) Len() int           { return len(a) }
func (a SortType) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
func (a SortType) Less(i, j int) bool { return a[i] < a[j] }

func NewRandom(length uint, seed int64) SortType {
	s := rand.NewSource(seed)
	r := rand.New(s)
	st := New(length)

	r.Shuffle(len(st), func(i, j int) {
		st[i], st[j] = st[j], st[i]
	})

	return st
}

func New(length uint) SortType {
	s := make(SortType, length)

	for i := range s {
		s[i] = uint(i) + 1
	}

	return s
}

func NewReversed(length uint) SortType {
	s := make(SortType, length)

	for i := range s {
		s[i] = length - uint(i)
	}

	return s
}

func NewNearlySorted(length uint, seed int64, sparse uint) SortType {
	s := rand.NewSource(seed)
	r := rand.New(s)
	st := New(length)

	for i := 0; uint(i) < length; i++ {
		newIndex := uint(i + r.Intn(int(sparse)))

		if newIndex < length {
			st[i], st[newIndex] = st[newIndex], st[i]
		}
	}

	return st
}

func NewFewUnique(length uint, seed int64, groups uint) SortType {
	s := rand.NewSource(seed)
	r := rand.New(s)
	st := make(SortType, length)

	for i := uint(0); i < length; i += groups {
		for j := i; j < length; j++ {
			st[j] = i + 1
		}
	}

	r.Shuffle(len(st), func(i, j int) {
		st[i], st[j] = st[j], st[i]
	})

	return st
}

func NewOfType(t string, length uint, seed int64) SortType {
	switch t {
	case "random":
		return NewRandom(length, seed)
	case "nearlysorted":
		return NewNearlySorted(length, seed, length/8)
	case "reversed":
		return NewReversed(length)
	case "fewunique":
		return NewFewUnique(length, seed, (length/10)+1)
	}
	panic(fmt.Sprintf("Unknown type %v", t))
}

func BenchAlgorithm(b *testing.B, f func(sort.Interface)) {
	benchTypes := []string{
		"random",
		"nearlysorted",
		"reversed",
		"fewunique",
	}

	slicesLengths := []uint{10}

	for _, t := range benchTypes {
		b.Run(t, func(b *testing.B) {
			for _, n := range slicesLengths {
				b.Run(fmt.Sprintf("%v", n), func(b *testing.B) {
					b.StopTimer()
					for i := 0; i < b.N; i++ {
						slice := NewOfType(t, n, int64(int(n)*b.N))
						b.StartTimer()
						f(slice)
						b.StopTimer()
					}
				})
			}
		})
	}
}

Benchmark.go

BenchmarkShellSort/random/10-12                  3000000               538 ns/op
BenchmarkShellSort/random/25-12                  1000000              1294 ns/op
BenchmarkShellSort/random/50-12                   500000              3033 ns/op
BenchmarkShellSort/random/100-12                  200000              7600 ns/op
BenchmarkShellSort/random/200-12                  100000             24155 ns/op
BenchmarkShellSort/random/300-12                   50000             34732 ns/op
BenchmarkShellSort/random/600-12                   20000             84596 ns/op
BenchmarkShellSort/random/1000-12                  10000            151735 ns/op
BenchmarkShellSort/random/2000-12                   5000            371222 ns/op
BenchmarkShellSort/random/5000-12                   2000           1102749 ns/op
BenchmarkShellSort/nearlysorted/10-12            3000000               480 ns/op
BenchmarkShellSort/nearlysorted/25-12            2000000               999 ns/op
BenchmarkShellSort/nearlysorted/50-12             500000              2580 ns/op
BenchmarkShellSort/nearlysorted/100-12            300000              6373 ns/op
BenchmarkShellSort/nearlysorted/200-12            100000             16416 ns/op
BenchmarkShellSort/nearlysorted/300-12             50000             29462 ns/op
BenchmarkShellSort/nearlysorted/600-12             20000             68368 ns/op
BenchmarkShellSort/nearlysorted/1000-12            10000            130586 ns/op
BenchmarkShellSort/nearlysorted/2000-12             5000            303023 ns/op
BenchmarkShellSort/nearlysorted/5000-12             2000            939944 ns/op
BenchmarkShellSort/reversed/10-12                2000000               703 ns/op
BenchmarkShellSort/reversed/25-12                1000000              1253 ns/op
BenchmarkShellSort/reversed/50-12                 500000              2762 ns/op
BenchmarkShellSort/reversed/100-12                300000              5716 ns/op
BenchmarkShellSort/reversed/200-12                100000             13647 ns/op
BenchmarkShellSort/reversed/300-12                100000             22099 ns/op
BenchmarkShellSort/reversed/600-12                 30000             49397 ns/op
BenchmarkShellSort/reversed/1000-12                20000             87561 ns/op
BenchmarkShellSort/reversed/2000-12                10000            189891 ns/op
BenchmarkShellSort/reversed/5000-12                 3000            568537 ns/op
BenchmarkShellSort/fewunique/10-12               3000000               489 ns/op
BenchmarkShellSort/fewunique/25-12               1000000              1189 ns/op
BenchmarkShellSort/fewunique/50-12                500000              2693 ns/op
BenchmarkShellSort/fewunique/100-12               200000              6040 ns/op
BenchmarkShellSort/fewunique/200-12               100000             16905 ns/op
BenchmarkShellSort/fewunique/300-12                50000             24623 ns/op
BenchmarkShellSort/fewunique/600-12                20000             56229 ns/op
BenchmarkShellSort/fewunique/1000-12               20000            100739 ns/op
BenchmarkShellSort/fewunique/2000-12               10000            230638 ns/op
BenchmarkShellSort/fewunique/5000-12                2000            639915 ns/op

Kaynaklar