diff options
Diffstat (limited to 'sort/quick.go')
| -rw-r--r-- | sort/quick.go | 43 |
1 files changed, 35 insertions, 8 deletions
diff --git a/sort/quick.go b/sort/quick.go index b6dd427..f3502e5 100644 --- a/sort/quick.go +++ b/sort/quick.go @@ -2,10 +2,10 @@ package sort import ( "algorithms/ds" + "math/rand" ) func Quick(a ds.ArrayList) ds.ArrayList { - Shuffle(a) quick(a) return a } @@ -22,15 +22,13 @@ func quick(a ds.ArrayList) { } func quickPartition(a ds.ArrayList) int { - i := 0 // Left scan index - j := len(a) // Right scan index + l := len(a) + i := 0 // Left scan index + j := l // Right scan index hi := j - 1 - // Median of first 3 elems is partitioning item - // This works because we randomly shuffled a in the beginning - Insertion(a[0:3]) - a.Swap(0, 1) - v := a[0] // Partitioning item + a.Swap(0, median(a, l)) + v := a[0] for { for i++; a[i] < v && i < hi; i++ { @@ -53,3 +51,32 @@ func quickPartition(a ds.ArrayList) int { // whith a[lo..j-1 <= a[j] <= a[j+1..hi] return j } + +func median(a ds.ArrayList, l int) int { + u := rand.Intn(l) + v := rand.Intn(l) + w := rand.Intn(l) + + x := a[u] + y := a[v] + z := a[w] + + if x < y { + switch { + case y < z: + return v + case x < z: + return w + default: + return u + } + } + switch { + case x < z: + return u + case y < z: + return w + default: + return v + } +} |