From 9bee249738c6bbea23a3618bd487d8d046dd2fc4 Mon Sep 17 00:00:00 2001 From: Paul Buetow Date: Sat, 8 Aug 2020 16:24:56 +0100 Subject: fix test --- sort/quick.go | 12 ++++-------- 1 file changed, 4 insertions(+), 8 deletions(-) (limited to 'sort/quick.go') diff --git a/sort/quick.go b/sort/quick.go index 7222515..b6dd427 100644 --- a/sort/quick.go +++ b/sort/quick.go @@ -26,21 +26,17 @@ func quickPartition(a ds.ArrayList) int { j := len(a) // 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 for { - for i++; a[i] < v; i++ { - if i == hi { - break - } + for i++; a[i] < v && i < hi; i++ { } - for j--; v < a[j]; j-- { - if j == 0 { - break - } + for j--; v < a[j] && j > 0; j-- { } // Check scan complete -- cgit v1.2.3