diff options
| -rw-r--r-- | ds/arraylist.go | 2 | ||||
| -rw-r--r-- | sort/insertion.go | 2 | ||||
| -rw-r--r-- | sort/quick.go | 66 | ||||
| -rw-r--r-- | sort/sort_test.go | 12 |
4 files changed, 80 insertions, 2 deletions
diff --git a/ds/arraylist.go b/ds/arraylist.go index 7bc002a..d3feef5 100644 --- a/ds/arraylist.go +++ b/ds/arraylist.go @@ -36,7 +36,7 @@ func (a ArrayList) Sorted() bool { return true } -func (a ArrayList) SwapPos(i, j int) { +func (a ArrayList) Swap(i, j int) { tmp := a[i] a[i] = a[j] a[j] = tmp diff --git a/sort/insertion.go b/sort/insertion.go index 9f7215b..3e271b0 100644 --- a/sort/insertion.go +++ b/sort/insertion.go @@ -12,7 +12,7 @@ func Insertion(a ds.ArrayList) ds.ArrayList { if a[j].Higher(a[j-1]) { break } - a.SwapPos(j, j-1) + a.Swap(j, j-1) } } diff --git a/sort/quick.go b/sort/quick.go new file mode 100644 index 0000000..dde71f9 --- /dev/null +++ b/sort/quick.go @@ -0,0 +1,66 @@ +package sort + +import ( + "algorithms/ds" +) + +func Quick(a ds.ArrayList) ds.ArrayList { + a = Shuffle(a) + quick(a, 0, len(a)-1) + return a +} + +func quick(a ds.ArrayList, lo, hi int) { + if hi <= lo { + return + } + + j := quickPartition(a, lo, hi) + quick(a, lo, j-1) + quick(a, j+1, hi) +} + +func quickPartition(a ds.ArrayList, lo, hi int) int { + i := lo // Left scan index + j := hi+1 // Right scan index + v := a[lo] // Partitioning item + + for { + // Scan left + for { + i++ + if i == hi { + break + } + if a[i].Lower(v) { + continue + } + break + } + + // Scan right + for { + j-- + if j == lo { + break + } + if v.Lower(a[j]) { + continue + } + break + } + + // Check scan complete + if i >= j { + break + } + + a.Swap(i, j) + } + + // Put partitioning item v into a[j] + a.Swap(lo, j) + + // whith a[lo..j-1 <= a[j] <= a[j+1..hi] + return j +} diff --git a/sort/sort_test.go b/sort/sort_test.go index 8415d7d..a0e4729 100644 --- a/sort/sort_test.go +++ b/sort/sort_test.go @@ -56,6 +56,12 @@ func TestMerge3Sort(t *testing.T) { test(Merge3, maxLength*2, t) } +func TestQuickSort(t *testing.T) { + for i := 1; i <= maxLength; i *= 10 { + test(Quick, i, t) + } +} + func TestShuffleSort(t *testing.T) { for i := 10; i <= maxLength; i *= 10 { testShuffle(Shuffle, i, t) @@ -98,6 +104,12 @@ func BenchmarkMerge3Sort(b *testing.B) { } } +func BenchmarkQuickSort(b *testing.B) { + for i := 1; i <= maxLength; i *= 10 { + benchmark(Quick, i, b) + } +} + func BenchmarkShuffleSort(b *testing.B) { for i := 1; i <= maxLength; i *= 10 { benchmark(Shuffle, i, b) |