Code: third_year_project/sort/SorterMethods.java

Abstract: A project investigating and developing an implicitly concurrent programming language, based on a metaphor taken from the physical world is reported. Uses a programming paradigm where programs consist of systems of autonomous agents, or active objects which communicate via message passing. A language enhancing Java with actors and linear types is presented. Example programs are written, compiled, and executed to evaluate the usefulness of the language. The language found to provide a familiar notation for implicit parallelism, and a compelling new model for concurrency, combining the performance of shared variables with the elegance of message passing.

import org.taj.ajava.util.*;
import java.util.*;

/**
 * Useful helper methods for sorting arrays.
 */
public class SorterMethods {
	
    public static final int MIN_PARTITION_SIZE = 500;
	
	private static Random rng = new Random();
	
	public static void copyArray(IntegerArray a, IntegerArray b) {
		for (int c = 0; c < a.size(); c++)
	         b.set(c, a.get(c));
	}
	
	/**
	 * Initializes an array with random values.
	 * @param array
	 */
	public static void seedArray(IntegerArray array) {
		
		for (int i = 0; i < array.size(); i++) 
			array.set(i, rng.nextInt(array.size()));
	}
	
	/**
	 * Display array
	 * @param array
	 */
	public static void printArray(IntegerArray array) {
		for (int i = 0; i < array.size(); i++) {
			System.out.print(array.get(i));
			System.out.print(" ");
		}
	}
	
	/**
	 * Sorts this array using quicksort.
	 * @param array
	 */
	public static void sortArray(IntegerArray array) {
		sortArray(array, 0, array.size()-1);
	}
	
	/**
	 * Sorts the array range using quicksort.
	 * @param array
	 * @param left
	 * @param right
	 */
	protected static void sortArray(IntegerArray array, int left, int right) {
		if (right > left) {
			int pivotIndex = choosePivotIndex(array, left, right);
			int pivotNewIndex = partitionArray(array, left, right, pivotIndex);
			sortArray(array, left, pivotNewIndex-1);
			sortArray(array, pivotNewIndex+1, right);
		}
	}
	
	/**
	 * Chooses a good pivot value to partition the array range around.
	 * @param array the array 
	 * @return a good pivot index
	 */
	public static int choosePivotIndex(IntegerArray array) {
		return choosePivotIndex(array, 0, array.size()-1);
	}
	
	/**
	 * Chooses a good pivot value to partition the array range around.
	 * @param array the array 
	 * @param left the leftmost array index
	 * @param right the rightmost array index
	 * @return a good pivot index
	 */
	protected static int choosePivotIndex(IntegerArray array, int left, int right) {
		/*int mid = ((right-left)/2)+left;
		int lv = array.get(left), 
		    rv = array.get(right), 
		    mv = array.get(mid);
		int av = (lv + rv + mv) / 3;
		lv -= av; lv *= lv;
		rv -= av; rv *= rv;
		mv -= av; mv *= mv;
		if (lv < rv) {
			if (mv < lv) return mid;
			else return left;
		} else {
			if (mv < rv) return mid;
			else return right;
		}*/
		return rng.nextInt(right-left)+left;
	}
	
	/**
	 * Partition the array around the value at pivotIndex
	 * and return the new index of this pivot value.
	 * @param array the array to partition
	 * @param pivotIndex the element to pivot around
	 * @return the index of the pivot element
	 */
	public static int partitionArray(IntegerArray array,
			int pivotIndex) {
		return partitionArray(array, 0, array.size()-1, pivotIndex);
	}
	
	/**
	 * Partition the array around the value at pivotIndex
	 * and return the new index of this pivot value.
	 * @param array the array to partition
	 * @param left the array section's left index
	 * @param right the array sections right index
	 * @param pivotIndex the element to pivot around
	 * @return the index of the pivot element
	 */
	protected static int partitionArray(IntegerArray array, 
			int left, int right, int pivotIndex) {
		int pivotValue = array.get(pivotIndex);
		// move pivot to end
		array.set(pivotIndex, array.get(right));
		array.set(right, pivotValue);
		// reorganise around pivot
		int storeIndex = left;
		for (int i = left; i < right; i++) {
			int iValue = array.get(i);
			if (iValue <= pivotValue) {
				array.set(i, array.get(storeIndex));
				array.set(storeIndex, iValue);
				storeIndex++;
			}
		}
		// move pivot to its final place
		array.set(right, array.get(storeIndex));
		array.set(storeIndex, pivotValue);
		return storeIndex;
	}
	
}

ActiveJava

SorterMethods.java