CODEWITHSUNDEEP
goquicksort
Collander
Collander

Reputation: 51

Concurrent QuickSort only partially sorting

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?

Upvotes: 1

Views: 139

Answers (1)

Raj
Raj

Reputation: 487

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()
    }
}

Upvotes: 4

Related Questions