Concurrent QuickSort仅部分排序

Question

我试图实现快速排序并发。当我运行它并查看已排序的数组时，在数组开头附近有一部分元素未排序，但数组的大部分元素都未排序。

下面的代码

package main
import (
"fmt"
"math/rand"
//"runtime"
"sync"
"time"
)
func main() {
slice := generateSlice(1000000)
var wg sync.WaitGroup
start := time.Now()
go Quicksort(slice, 0, len(slice)-1, &wg)
wg.Wait()
end := time.Since(start)
fmt.Printf("Sort Time: %v, sorted: %v n", end, slice)
}
func Quicksort(A []int, p int, r int, wg *sync.WaitGroup) {
if p < r {
q := Partition(A, p, r)
wg.Add(2)
go Quicksort(A, p, q-1, wg)
go Quicksort(A, q+1, r, wg)
}
}
func Partition(A []int, p int, r int) int {
index := rand.Intn(r-p) + p
pivot := A[index]
A[index] = A[r]
A[r] = pivot
x := A[r]
j := p - 1
i := p
for i < r {
if A[i] <= x {
j++
tmp := A[j]
A[j] = A[i]
A[i] = tmp
}
i++
}
temp := A[j+1]
A[j+1] = A[r]
A[r] = temp
return j + 1
}
func generateSlice(size int) []int {
slice := make([]int, size)
rand.Seed(time.Now().UnixNano())
for i := 0; i < size; i++ {
slice[i] = rand.Intn(999) - rand.Intn(999)
}
return slice
}

我似乎找不到问题，有什么主意吗?

Answer 1

您的实现有多个问题。Hymns For Disco已经在评论中提到了其中的几个。我建议的另一个更改是不要在所有递归函数调用中使用相同的waitGroup。跟踪计数器的递增和递减是非常困难的，可能会导致死锁。

我对你的代码做了一些修改。我认为它工作得很好。注意'Partition'和'generateSlice'函数保持不变。

func main() {
slice := generateSlice(1000)
Quicksort(slice, 0, len(slice)-1)
fmt.Printf("%vn", slice)
}
func Quicksort(A []int, p int, r int) {
if p < r {
var wg sync.WaitGroup
q := Partition(A, p, r)
wg.Add(2)
go func() {
defer wg.Done()
Quicksort(A, p, q-1)
}()
go func() {
defer wg.Done()
Quicksort(A, q+1, r)
}()
wg.Wait()
}
}