# shlomil

a guest
Nov 25th, 2009
962
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. //Filename: mtquicksort.go  - By Shlomil 2009 - public domain
2. package main
3.
4. import "fmt"
5.
6. func partition(arr [] int, pivot int) int
7. {
8.     if len(arr)==0 {
9.         return pivot;
10.     }
11.     pivotval := arr[pivot];
12.     arr[pivot] , arr[0] = arr[0] , arr[pivot];
13.     var store = len(arr)-1;
14.     for i:=len(arr)-1; i>=1; i-- {
15.         if arr[i] >= pivotval {
16.             arr[i] , arr[store] =  arr[store] , arr[i];
17.             store--;
18.         }
19.     }
20.     arr[store] , arr[0] =  arr[0] , arr[store];
21.     return store;
22. }
23.
24. func quicksort(arr [] int, done chan bool) {
25.     if len(arr) < 2 {
26.         done <- true;
27.         return;
28.     }
29.     var done_left = make(chan bool);
30.     var done_right = make(chan bool);
31.     pivot := partition(arr, len(arr)/2);
32.     go quicksort(arr[0:pivot],done_left);
33.     go quicksort(arr[pivot+1:len(arr)],done_right);
34.     done <- ((<-done_left) && (<-done_right));
35.     return;
36. }
37.
38. func parallel_quicksort(arr [] int) {
39.     var d = make(chan bool);
40.     go quicksort(arr,d);
41.     <-d;
42. }
43.
44. func main()
45. {
46.     var a = [7]int{1,5,3,8,2,2,0};
47.
48.     parallel_quicksort(&a);
49.
50.     for _,v := range a {
51.         fmt.Printf("%d,",v);
52.     }
53.     fmt.Printf("\n");
54. }
55.