Example of Coding on haXe (Quicksort, Hoarse, Random) – Part 6

In this example you will see: Regular quicksort, quicksort using random partition, quicksort using Hoarse partition, quicksort using random partition together with Hoarse partition

NOTIFICATION: These examples are provided for educational purposes. Using this code is under your own responsibility and risk. The code is given ‘as is’. I do not take responsibilities of how they are used.

example_6.hx:

/**
 * @author: Alejandro G. Carlstein R. M.
 */

enum PartitionType{
	DEFAULT;
	RANDOMIZED;
	HOARSE;
	RANDOMIZED_HOARSE;
}

class QuickSort{
	private var data : Array<Int>;
	private var partition_type : PartitionType;

	private function _sort(start_index : Int, end_index : Int) : Void{
		if (start_index < end_index){
			var partition_index : Int = getPartitionIndex(start_index, end_index);
			_sort(start_index, partition_index - 1);
			_sort(partition_index + 1, end_index);
		}
	}

	private function getPartitionIndex(start_index : Int, end_index : Int) : Int{
		switch(partition_type){
			case DEFAULT:
				return partition(start_index, end_index);
			case RANDOMIZED:
				return randomPartition(start_index, end_index);
			case HOARSE:
				return hoarsePartition(start_index, end_index);
			case RANDOMIZED_HOARSE:
				return randomizedHoarsePartition(start_index, end_index);
		}
		return -1;
	}

	private function partition(start_index : Int, end_index : Int) : Int{
		var pivot_value : Int = data[end_index];
		var i : Int = start_index - 1;

		var index : Int = start_index;
		while (index < end_index){
			if (data[index] < pivot_value)
				exchange(++i, index);
			++index;
		}
		exchange(++i, end_index);
		return i;
	}

	private function randomPartition(start_index : Int, end_index : Int) : Int{
		exchange(getRandom(start_index, end_index), end_index);
		return partition(start_index, end_index);
	}

	private function getRandom(maximum_value : Int, minimum_value : Int) : Int{
		return Math.floor(Math.random() % (maximum_value - minimum_value)) + minimum_value;
	}

	private function hoarsePartition(start_index : Int, end_index : Int) : Int{
		var pivot_value : Int = data[start_index];
		var left_index : Int = start_index;
		var right_index : Int = end_index;
		while (left_index < right_index){
			while (data[left_index] < pivot_value)
				--right_index;
			while (data[left_index] > pivot_value)
				++left_index;
			if (left_index < right_index)
				exchange(left_index, right_index);
			else
				break;
			if (data[right_index] == data[left_index]){
				--right_index;
				++left_index;
			}
		}
		return right_index;
	}

	private function randomizedHoarsePartition(start_index : Int, end_index : Int) : Int{
		exchange(getRandom(start_index, end_index), end_index);
		return hoarsePartition(start_index, end_index);
	}	

	private function exchange(index_a : Int, index_b : Int) : Void{
		var temp_value : Int = data[index_a];
		data[index_a] = data[index_b];
		data[index_b] = temp_value;
	}

	// Constructor ( ? means that items is optional)
	public function new(?data : Array<Int>, ?partition_type : PartitionType){
		this.data = (data == null) ? new Array() : data;
		setPartitionType(partition_type);
	}

	public function getData() : Array<Int> {
		return data;
	}

	public function setData(data : Array<Int>) : Void {
		this.data = data;
	}

	public function sort() : Void{
		if(data.iterator().hasNext())
			_sort(0, data.length - 1);
	}

	public function setPartitionType(parition_type : PartitionType) : Void{
		this.partition_type = (partition_type == null) ? DEFAULT : partition_type;
	}

}

class Example_6 {

	static function main(){

		var data : Array<Int> = [3, 7, 1, -1];
		printData(data);

		trace('QuickSort using regular partition:');
		var quicksort = new QuickSort(data, DEFAULT);
		quicksort.sort();
		data = quicksort.getData();
		printData(data);		

		data = [3, 7, 1, -1];
		trace('QuickSort using randomized partition:');
		var quicksort_1 = new QuickSort(data, RANDOMIZED);
		quicksort_1.sort();
		data = quicksort_1.getData();
		printData(data);		

		data = [3, 7, 1, -1];
		trace('QuickSort using Hoarse partition:');
		var quicksort_2 = new QuickSort(data, HOARSE);
		quicksort_2.sort();
		data = quicksort_2.getData();
		printData(data);		

		data = [3, 7, 1, -1];
		trace('QuickSort using randomized Hoarse partition:');
		var quicksort_3 = new QuickSort(data, RANDOMIZED_HOARSE);
		quicksort_3.sort();
		data = quicksort_3.getData();
		printData(data);
	}

	private static function printData(data : Array<Int>){
		var iter = data.iterator();
		var index : Int = 0;
		trace('[DATA]');
		while (iter.hasNext()){
			trace('data[' + index++ + ']: ' + iter.next());
		}
	}

}

If you encounter any problems or errors, please let me know by providing an example of the code, input, output, and an explanation. Thanks.

© 2010, Alejandro G. Carlstein Ramos Mejia. All rights reserved.