并发快速排序

Question

所以我在go中实现了快速排序算法。我用go test进行了测试，效果很好。现在我想让它并发并检查计算时间的差异。算法是这样的：

package mysort 

import (
    "math/rand" 
) 

// ConcurrentPartition - ConcurrentQuicksort function for partitioning the array (randomized choice of a pivot) 
func ConcurrentPartition(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 
} 

// ConcurrentQuicksort - a concurrent version of a quicksort algorithm 
func ConcurrentQuicksort(A []int, p int, r int) { 
    if p < r { 
     q := ConcurrentPartition(A, p, r) 
     ConcurrentQuicksort(A, p, q-1) 
     ConcurrentQuicksort(A, q+1, r) 
    } 
} 

每ConcurrentQuicksort是实际工作中的独立默认情况下，作为其divide and conquer理念的构建。所以，我做的唯一的事情是添加go关键字每次递归调用之前，就像这样：

go ConcurrentQuicksort(A, p, q-1) 
go ConcurrentQuicksort(A, q+1, r) 

我didnt't工作。正如我所见，它只是一个数组，甚至没有一次称为递归快速排序。所以我添加time进口和这一行：

time.Sleep(time.Second * 2)（那if后）

和它的工作。所以我想这需要时间来完成所有的操作。我现在怎样才能不用等待呢？我应该使用频道，还是以不同的方式调用功能？

@Edit添加了这个：

func ConcurrentQuicksort(A []int, p int, r int, wg *sync.WaitGroup) { 
    if p < r { 
     q := ConcurrentPartition(A, p, r) 
     wg.Add(2) 
     go ConcurrentQuicksort(A, p, q-1, wg) 
     go ConcurrentQuicksort(A, q+1, r, wg) 
    } 
} 

Answer 1

您可以在这里使用sync包。创建一个WaitGroup实际上不会再沿着线程走下去，直到所有的例程都实际完成。它有非常平凡的界面。这里是使用的例子。

func main() { 
    var wg sync.WaitGroup 

    for i := 0; i < 1000; i++ { 
     wg.Add(1) 
     go func(index int) { 
      defer wg.Done() 
      fmt.Println("I'm done and my index is", index) 
     }(i) 
    } 

    wg.Wait() 

    fmt.Println("This message is actually printed after all goroutines are done") 
}