From c870dae11a5ec088800a35665d6ac1baa3abef3a Mon Sep 17 00:00:00 2001 From: Paul Buetow Date: Sat, 8 Aug 2020 14:32:37 +0100 Subject: refactor quicksort --- sort/insertion.go | 9 +++------ sort/parallelquick.go | 21 +++++++++++---------- sort/quick.go | 35 ++++++++++++++--------------------- sort/quick3way.go | 25 +++++++++++++------------ sort/sort_test.go | 4 ++-- 5 files changed, 43 insertions(+), 51 deletions(-) (limited to 'sort') diff --git a/sort/insertion.go b/sort/insertion.go index 6663bca..203d4f2 100644 --- a/sort/insertion.go +++ b/sort/insertion.go @@ -5,12 +5,7 @@ import ( ) func Insertion(a ds.ArrayList) ds.ArrayList { - insertion(a, 0, len(a)-1) - return a -} - -func insertion(a ds.ArrayList, lo, hi int) { - for i := lo; i <= hi; i++ { + for i, _ := range a { for j := i; j > 0; j-- { if a[j] > a[j-1] { break @@ -18,4 +13,6 @@ func insertion(a ds.ArrayList, lo, hi int) { a.Swap(j, j-1) } } + + return a } diff --git a/sort/parallelquick.go b/sort/parallelquick.go index f68135f..2ac9f0e 100644 --- a/sort/parallelquick.go +++ b/sort/parallelquick.go @@ -7,34 +7,35 @@ import ( func ParallelQuick(a ds.ArrayList) ds.ArrayList { Shuffle(a) - parallelQuick(a, 0, len(a)-1) + parallelQuick(a) return a } -func parallelQuick(a ds.ArrayList, lo, hi int) { - if hi <= lo+10 { - insertion(a, lo, hi) +func parallelQuick(a ds.ArrayList) { + length := len(a) + if length <= 10 { + Insertion(a) return } - j := quickPartition(a, lo, hi) + j := quickPartition(a) - if hi <= lo+1000 { + if length >= 1000 { var wg sync.WaitGroup wg.Add(2) defer wg.Wait() go func() { - parallelQuick(a, lo, j-1) + parallelQuick(a[0:j]) wg.Done() }() go func() { - parallelQuick(a, j+1, hi) + parallelQuick(a[j+1:]) wg.Done() }() return } - parallelQuick(a, lo, j-1) - parallelQuick(a, j+1, hi) + parallelQuick(a[0:j]) + parallelQuick(a[j+1:]) } diff --git a/sort/quick.go b/sort/quick.go index 5dbcfe5..72db370 100644 --- a/sort/quick.go +++ b/sort/quick.go @@ -6,41 +6,34 @@ import ( func Quick(a ds.ArrayList) ds.ArrayList { Shuffle(a) - quick(a, 0, len(a)-1) + quick(a) return a } -func quick(a ds.ArrayList, lo, hi int) { - if hi <= lo+10 { - insertion(a, lo, hi) +func quick(a ds.ArrayList) { + if len(a) <= 10 { + Insertion(a) return } - j := quickPartition(a, lo, hi) - - quick(a, lo, j-1) - quick(a, j+1, hi) + j := quickPartition(a) + quick(a[0:j]) + quick(a[j+1:]) } -func quickPartition(a ds.ArrayList, lo, hi int) int { - i := lo // Left scan index - j := hi + 1 // Right scan index +func quickPartition(a ds.ArrayList) int { + i := 0 // Left scan index + j := len(a) // Right scan index - insertion(a, lo, lo+2) - a.Swap(lo, lo+1) - v := a[lo] // Partitioning item + Insertion(a[0:3]) + a.Swap(0, 1) + v := a[0] // Partitioning item for { for i++; a[i] < v; i++ { - if i == hi { - break - } } for j--; v < a[j]; j-- { - if j == lo { - break - } } // Check scan complete @@ -52,7 +45,7 @@ func quickPartition(a ds.ArrayList, lo, hi int) int { } // Put partitioning item v into a[j] - a.Swap(lo, j) + a.Swap(0, j) // whith a[lo..j-1 <= a[j] <= a[j+1..hi] return j diff --git a/sort/quick3way.go b/sort/quick3way.go index e6cb677..6e7dc18 100644 --- a/sort/quick3way.go +++ b/sort/quick3way.go @@ -7,23 +7,24 @@ import ( // Quick3Way uses a 3-way partitioning so it is more efficient dealing with duplicates func Quick3Way(a ds.ArrayList) ds.ArrayList { Shuffle(a) - quick3Way(a, 0, len(a)-1) + quick3Way(a) return a } -func quick3Way(a ds.ArrayList, lo, hi int) { - if hi <= lo+10 { - insertion(a, lo, hi) +func quick3Way(a ds.ArrayList) { + length := len(a) + if length <= 10 { + Insertion(a) return } - lt := lo // Lower than - i := lo + 1 // lt..i contain duplicates - gt := hi // Greater than + lt := 0 // Lower than + i := 1 // lt..i contain duplicates + gt := length - 1 // Greater than - insertion(a, lo, lo+2) - a.Swap(lo, lo+1) - v := a[lo] // Partitioning item + Insertion(a[0:3]) + a.Swap(0, 1) + v := a[0] // Partitioning item for i <= gt { switch { @@ -41,6 +42,6 @@ func quick3Way(a ds.ArrayList, lo, hi int) { } // Now a[lo..lt-1] < v = a[lt..gt] < a[gt+1..hi] - quick3Way(a, lo, lt-1) - quick3Way(a, gt+1, hi) + quick3Way(a[0:lt]) + quick3Way(a[gt+1:]) } diff --git a/sort/sort_test.go b/sort/sort_test.go index 6f6bcc2..f350b46 100644 --- a/sort/sort_test.go +++ b/sort/sort_test.go @@ -11,8 +11,8 @@ var benchResult ds.ArrayList var benchResultInt []int const minLength int = 1 -const maxLength int = 100000 -const maxSlowLength int = 100000 +const maxLength int = 1000 +const maxSlowLength int = 1000 var arrayListCache map[string]ds.ArrayList -- cgit v1.2.3