quickSortParallel.chpl

quickSortParallel.chpl

// // Qucksort psudo-code taken from http://en.wikipedia.org/wiki/Quicksort

// For speedup information, see https://docs.google.com/a/knox.edu/spreadsheets/d/1I3ReQhltJn6DObg3Lm9uQ4T49QOb3qXgf3biW6Q-oj4/edit?usp=sharing
// See comment on cell A1 ^

use Random;
use Time;

// n - size of the random array to be sorted
config const n: int = 50;
// debug - set to true if debugging program
config const debug: bool = false;
// numCores - number of cores available
config const numCores = here.numCores;

proc swap(array: []real, i: int, j: int) {
	var temp: real = array[i];
	array[i] = array[j];
	array[j] = temp;
}

proc partition(array: []real, start: int, end: int): int {
	var pivotIndex: int = (start + end)/2;
	var pivotValue: real = array[pivotIndex];
	swap(array, pivotIndex, end);
	var storeIndex: int = start;
	for i in start..end {
		if array[i] < pivotValue {
			swap(array, i, storeIndex);
			storeIndex = storeIndex + 1;
		}
	}
	swap(array, storeIndex, end);
	return storeIndex;
}

proc quickSort(array: []real, start: int, end: int, parallelThreshhold: int) {
	if(start < end) {
		var p: int = partition(array, start, end);
		if(((array.domain.high - array.domain.low)/numCores)*10 > parallelThreshhold) {
	    cobegin {
	  		quickSort(array, start, p - 1, parallelThreshhold);
	  		quickSort(array, p + 1, end, parallelThreshhold);
	    }
	  }
	  else {
  		quickSort(array, start, p - 1, parallelThreshhold);
  		quickSort(array, p + 1, end, parallelThreshhold);
	  }
	}
}

// Can get the domain of an array param with [?DOMAIN_NAME]TYPE syntax
proc verifyArraySorted(array: [?D]real) {
  for i in (D.low)..(D.high-1) {
  	if array[i] >= array[i+1] {
  		writeln("Array not ordered at index " + i+1);
  		return;
  	}
  }
}

// proc main() {
// 	var timer = new Timer();
// 	var array: [0..n-1] real;
// 	for i in 0..50 {
// 		for j in 0..100 {
// 			fillRandom(array);

// 			timer.start();
// 			quickSort(array, array.domain.low, array.domain.high, i);
// 			timer.stop();
// 		}
// 		writeln("" + i + "," + timer.elapsed());
// 		timer.clear();
// 	}
// }

proc main() {
	var array: [0..n-1] real;
	fillRandom(array);
	quickSort(array, array.domain.low, array.domain.high, numCores);
}