diff options
Diffstat (limited to 'sort')
| -rw-r--r-- | sort/merge.go | 3 | ||||
| -rw-r--r-- | sort/parallelmerge.go | 10 | ||||
| -rw-r--r-- | sort/parallelquick.go | 35 | ||||
| -rw-r--r-- | sort/sort_test.go | 43 |
4 files changed, 41 insertions, 50 deletions
diff --git a/sort/merge.go b/sort/merge.go index 601c378..4d5a862 100644 --- a/sort/merge.go +++ b/sort/merge.go @@ -13,7 +13,8 @@ func Merge(a ds.ArrayList) ds.ArrayList { func mergeSort(a, aux ds.ArrayList) { l := len(a) - if l <= 1 { + if l <= 10 { + Insertion(a) return } diff --git a/sort/parallelmerge.go b/sort/parallelmerge.go index 87543f6..c379883 100644 --- a/sort/parallelmerge.go +++ b/sort/parallelmerge.go @@ -12,18 +12,13 @@ func ParallelMerge(a ds.ArrayList) ds.ArrayList { func parallelMerge(a, aux ds.ArrayList) { l := len(a) - if l <= 1 { - return - } - mi := l / 2 if l < 1000 { - mergeSort(a[0:mi], aux[0:mi]) - mergeSort(a[mi:], aux[mi:]) - merge(a, aux, 0, mi, l-1) + mergeSort(a, aux) return } + mi := l / 2 var wg sync.WaitGroup wg.Add(2) @@ -39,5 +34,4 @@ func parallelMerge(a, aux ds.ArrayList) { wg.Wait() merge(a, aux, 0, mi, l-1) - return } diff --git a/sort/parallelquick.go b/sort/parallelquick.go index cde4b5e..7533d35 100644 --- a/sort/parallelquick.go +++ b/sort/parallelquick.go @@ -6,36 +6,31 @@ import ( ) func ParallelQuick(a ds.ArrayList) ds.ArrayList { - Shuffle(a) + //Shuffle(a) parallelQuick(a) return a } func parallelQuick(a ds.ArrayList) { l := len(a) - if l <= 10 { - Insertion(a) + + if l < 1000 { + quick(a) return } j := quickPartition(a) + var wg sync.WaitGroup + wg.Add(2) - if l >= 1000 { - var wg sync.WaitGroup - wg.Add(2) - defer wg.Wait() - - go func() { - parallelQuick(a[0:j]) - wg.Done() - }() - go func() { - parallelQuick(a[j+1:]) - wg.Done() - }() - return - } + go func() { + parallelQuick(a[0:j]) + wg.Done() + }() + go func() { + parallelQuick(a[j+1:]) + wg.Done() + }() - parallelQuick(a[0:j]) - parallelQuick(a[j+1:]) + wg.Wait() } diff --git a/sort/sort_test.go b/sort/sort_test.go index 024cde4..2ca6f91 100644 --- a/sort/sort_test.go +++ b/sort/sort_test.go @@ -10,7 +10,8 @@ import ( var benchResult ds.ArrayList const minLength int = 1 -const maxLength int = 100000 +const maxLength int = 1000000 +const factor int = 100 const maxSlowLength int = 100000 var arrayListCache map[string]ds.ArrayList @@ -19,32 +20,32 @@ type sortAlgorithm func(ds.ArrayList) ds.ArrayList type sortAlgorithmInt func([]int) []int func TestSelectionSort(t *testing.T) { - for i := minLength; i <= maxSlowLength; i *= 10 { + for i := minLength; i <= maxSlowLength; i *= factor { test(Selection, i, t) } } func TestInsertionSort(t *testing.T) { - for i := minLength; i <= maxSlowLength; i *= 10 { + for i := minLength; i <= maxSlowLength; i *= factor { test(Insertion, i, t) } } func TestShellSort(t *testing.T) { - for i := minLength; i <= maxLength; i *= 10 { + for i := minLength; i <= maxLength; i *= factor { test(Shell, i, t) } } func TestMergeSort(t *testing.T) { - for i := minLength; i <= maxLength; i *= 10 { + for i := minLength; i <= maxLength; i *= factor { test(Merge, i, t) } } func TestBottomUpMergeSort(t *testing.T) { t.Log("Parallel merge sort") - for i := minLength; i <= maxLength; i *= 10 { + for i := minLength; i <= maxLength; i *= factor { test(BottomUpMerge, i, t) } test(BottomUpMerge, maxLength*2, t) @@ -52,92 +53,92 @@ func TestBottomUpMergeSort(t *testing.T) { func TestParallelMergeSort(t *testing.T) { t.Log("Bottom-up merge sort") - for i := minLength; i <= maxLength; i *= 10 { + for i := minLength; i <= maxLength; i *= factor { test(ParallelMerge, i, t) } } func TestQuickSort(t *testing.T) { - for i := minLength; i <= maxLength; i *= 10 { + for i := minLength; i <= maxLength; i *= factor { test(Quick, i, t) } } func TestParallelQuickSort(t *testing.T) { - for i := minLength; i <= maxLength; i *= 10 { + for i := minLength; i <= maxLength; i *= factor { test(ParallelQuick, i, t) } } func TestQuick3WaySort(t *testing.T) { - for i := minLength; i <= maxLength; i *= 10 { + for i := minLength; i <= maxLength; i *= factor { test(Quick3Way, i, t) } } func TestShuffleSort(t *testing.T) { - for i := 10; i <= maxLength; i *= 10 { + for i := 10; i <= maxLength; i *= factor { testShuffle(Shuffle, i, t) } } func BenchmarkInsertionSort(b *testing.B) { - for i := minLength; i <= maxSlowLength; i *= 10 { + for i := minLength; i <= maxSlowLength; i *= factor { benchmark(Insertion, i, b) } } func BenchmarkSelectionSort(b *testing.B) { - for i := minLength; i <= maxSlowLength; i *= 10 { + for i := minLength; i <= maxSlowLength; i *= factor { benchmark(Selection, i, b) } } func BenchmarkShellSort(b *testing.B) { - for i := minLength; i <= maxLength; i *= 10 { + for i := minLength; i <= maxLength; i *= factor { benchmark(Shell, i, b) } } func BenchmarkMergeSort(b *testing.B) { - for i := minLength; i <= maxLength; i *= 10 { + for i := minLength; i <= maxLength; i *= factor { benchmark(Merge, i, b) } } func BenchmarkBottomUpMergeSort(b *testing.B) { - for i := minLength; i <= maxLength; i *= 10 { + for i := minLength; i <= maxLength; i *= factor { benchmark(BottomUpMerge, i, b) } } func BenchmarkParallelMergeSort(b *testing.B) { - for i := minLength; i <= maxLength; i *= 10 { + for i := minLength; i <= maxLength; i *= factor { benchmark(ParallelMerge, i, b) } } func BenchmarkQuickSort(b *testing.B) { - for i := minLength; i <= maxLength; i *= 10 { + for i := minLength; i <= maxLength; i *= factor { benchmark(Quick, i, b) } } func BenchmarkParallelQuickSort(b *testing.B) { - for i := minLength; i <= maxLength; i *= 10 { + for i := minLength; i <= maxLength; i *= factor { benchmark(ParallelQuick, i, b) } } func BenchmarkQuick3WaySort(b *testing.B) { - for i := minLength; i <= maxLength; i *= 10 { + for i := minLength; i <= maxLength; i *= factor { benchmark(Quick3Way, i, b) } } /* func BenchmarkShuffleSort(b *testing.B) { - for i := minLength; i <= maxLength; i *= 10 { + for i := minLength; i <= maxLength; i *= factor { benchmark(Shuffle, i, b) } } |