Skip to content

Instantly share code, notes, and snippets.

@elisehuard
Created October 19, 2010 20:55
Show Gist options
  • Save elisehuard/635097 to your computer and use it in GitHub Desktop.
Save elisehuard/635097 to your computer and use it in GitHub Desktop.
parallel quicksort
package main
import (
"fmt"
"os"
)
type request struct {
data []int
replyChannel chan []int
}
func append(lesser[]int, pivot int, greater[]int) []int {
newSlice := make([]int, (len(lesser) + len(greater) + 1))
copy(newSlice, lesser)
newSlice[len(lesser)] = pivot
for i, c := range greater {
newSlice[len(lesser) + i + 1] = c
}
return newSlice
}
func sort(incoming *request) {
data := incoming.data
if len(data) <= 1 {
incoming.replyChannel <- data
return
}
pivot, _ := pivot(data)
lessReply, greaterReply := startListener(incoming, pivot) // create channels and listener
less, greater := partition(data)
// now sort the resulting sub arrays in 2 goroutines
var lessReq, greaterReq request
lessReq.data = less
greaterReq.data = greater
lessReq.replyChannel, greaterReq.replyChannel = lessReply, greaterReply
go sort(&lessReq)
go sort(&greaterReq)
}
func pivot(data []int) (pivot int, pivotIndex int) {
pivotIndex = len(data)/2
pivot = data[pivotIndex]
return pivot, pivotIndex
}
func partition(data []int) (less []int, greater []int) {
pivot, pivotIndex := pivot(data)
less = make([]int, len(data))
greater = make([]int, len(data)) //just to be on the safe side
lessIndex := 0
greaterIndex := 0
for i := 0; i < len(data); i++ {
switch {
case i == pivotIndex:
case data[i] <= pivot:
less[lessIndex] = data[i]
lessIndex += 1
case data[i] > pivot:
greater[greaterIndex] = data[i]
greaterIndex += 1
}
}
return less[0:lessIndex], greater[0:greaterIndex]
}
func startListener(result *request, pivot int) (lessReply chan []int, greaterReply chan []int) {
lessReply = make(chan []int)
greaterReply = make(chan []int)
go sortListener(lessReply, greaterReply, result, pivot)
return lessReply, greaterReply
}
func sortListener(lessReply chan []int, greaterReply chan []int, result *request, pivot int) {
less, greater := false, false
var sortedLess []int
var sortedGreater []int
for !(less && greater) {
select {
case sortedLess = <-lessReply:
less = true
case sortedGreater = <-greaterReply:
greater = true
}
}
appended := append(sortedLess,pivot,sortedGreater)
result.replyChannel <- appended
}
func main() {
data := []int{74, 59, 238, -784, 9845, 959, 905, 0, 0, 42, 7586, -5467984, 7586}
replyChannel := make(chan []int)
var mainRequest request
mainRequest.data = data
mainRequest.replyChannel = replyChannel
sort(&mainRequest)
result := <-replyChannel
fmt.Fprintf(os.Stderr,"sorted %s\n", result)
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment