英文:
Concurrent QuickSort only partially sorting
问题
我正在尝试并发实现快速排序。当我运行它并查看排序后的数组时，发现数组开头附近的一部分元素是未排序的，但大部分数组是有序的。
以下是代码：
package main
import (
"fmt"
"math/rand"
"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("排序时间：%v，排序结果：%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
}
我找不到问题所在，有什么想法吗？
英文:
im trying to implement QuickSort concurrently. When I run it and look at the sorted array, there is a portion of elements near the start of the array that is unsorted but the majority of the array is.
Code Below
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
}
I can't seem to find the issue, any ideas?
答案1
得分: 3
你的实现存在多个问题。Hymns For Disco在评论中已经提到了其中一些。我建议的另一个改变是不要在所有递归函数调用中使用相同的waitGroup。这样很难跟踪计数器的增减，可能会导致死锁。
我对你的代码做了一些修改，我认为它现在工作正常。请注意，'Partition'和'generateSlice'函数保持不变。
func main() {
slice := generateSlice(1000)
Quicksort(slice, 0, len(slice)-1)
fmt.Printf("%v\n", 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()
}
}
希望对你有帮助！
英文:
Your implementation has multiple problems. Hymns For Disco has already mentioned a couple of them in the comments. Another change I would suggest is not to use the same waitGroup in all recursive function calls. It can be very difficult to keep track of counter increments and decrements and you might reach a deadlock.
I have made a few changes to your code. I think it's working fine. Note that 'Partition' and 'generateSlice' functions remain unchanged.
func main() {
slice := generateSlice(1000)
Quicksort(slice, 0, len(slice)-1)
fmt.Printf("%v\n", 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()
}
}
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论