Guest User

shlomil

a guest
Nov 25th, 2009
762
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.  
RAW Paste Data