Sorts

gistfile1.java

/**
	Inner class to handle different sorting algorithms
*/
private class Sort {
	
	private int data[];
	private int size;
	
	/**
		Constructor
	*/
	public Sort(int data[])
	{
		this.data = data;
		this.size = data.length;
	}
	
	/**
		Swaps the data of two indexed positions

		@param pos1 The first indexed position
		@param pos2 The second indexed position

		@return true
	*/
	private void swapIndexedData(int pos1, int pos2)
	{
		int data = this.data[pos1];
		this.data[pos1] = this.data[pos2];
		this.data[pos2] = data;
	}
	
	/**
		Sorts the elements of the list into ascending order
		using the quick sort algorithm
	*/
	public void quickSort()
	{
		this.quickSortWrapper(0, this.size - 1);
	}
	
	/**
		Wrapper method to apply the recursion to
		
		@param low The index at which to start sorting from the left
		@param high The index at which to start sorting from the right
	*/
	private void quickSortWrapper(int low, int high)
	{
		// Base case
		if(low >= high)
			return;
		
		// Middle elements data
		int pivot = this.data[(low + high) / 2];
		
		// Counters for the low/high indexes
		int l = low;
		int r = high;
		
		// Divide the array into two parts
		while(l < r)
		{
			// Find the high and low values
			while(this.data[l] < pivot) ++l;
			while(this.data[r] > pivot) --r;
			
			// Make sure we didn't go too far
			if(l > r) break;		
			
			// Swap the two indices
			this.swapIndexedData(l, r);
			++l; --r;			
		}
		
		// Sort the two seperate arrays
		quickSortWrapper(low, r);
		quickSortWrapper(l, high);
	}
	
	/**
		Sorts the elements of the list into ascending order
		using the selection sort algorithm.
	*/
	public void selectionSort()
	{
		this.selectionSortWrapper(0);
	}

	/**
		Wrapper method to apply the recursion to
		
		@param sortedTail The position of the end of the sorted list
	*/
	private void selectionSortWrapper(int sortedTail)
	{
		// Base case
		if(sortedTail >= this.size)
			return;

		// Generic case, find the min element and put it at the sorted tail
		int minElement = sortedTail;
		
		for(int i = sortedTail + 1; i < this.size; ++i)
			if((this.data[minElement] - this.data[i]) > 0)
				minElement = i;

		// Swap the first element after the sorted elements with the minElement
		this.swapIndexedData(sortedTail, minElement);

		// Sort the rest of the elements
		this.selectionSortWrapper(sortedTail + 1);
	}
	
	/**
		Sorts the elements of the list into ascending order
		using the insertion sort algorithm.
	*/
	public void insertionSort()
	{
		this.insertionSortWrapper(1);
	}

	/**
		Wrapper method to apply the recursion to
		
		@param inPosTail The position of the 'in position' elements tail
	*/
	private void insertionSortWrapper(int inPosTail)
	{
		// Base case
		if(inPosTail == this.size)
			return;
		
		//Generic case, swap until its in the correct position
		for(int i = inPosTail - 1; i >= 0; --i)
			if((this.data[i] - this.data[i +1]) > 0)
				this.swapIndexedData(i, i +1);
			else
				break;

		// Sort the rest of the elements
		this.insertionSortWrapper(inPosTail + 1);
	}

	/**
		Sorts the elements of the list into ascending order
		using the bubble sort algorithm.
	*/
	public void bubbleSort()
	{
		this.bubbleSortWrapper(0);
	}
	
	/**
		Wrapper method to apply the recursion to
		
		@param top The indexed position of the end of the ordered elements
	*/
	private void bubbleSortWrapper(int top)
	{	
		// Base case
		if(top >= this.size)
			return;

		// Generic case, Bubble the smallest up to the top
		for(int i = this.size - 1; i != top; --i)
			if((this.data[i] - this.data[i - 1]) < 0)
				this.swapIndexedData(i, i - 1);

		// Next pass
		this.bubbleSortWrapper(top + 1);
	}
	
	/**
		Sorts the elements of the list into ascending order
		using the shaker sort algorithm.
	*/
	public void shakerSort()
	{
		this.shakerSortWrapper(0, this.size - 1);
	}

	/**
		Wrapper method to apply the recursion to
		
		@param front Index of the sorted front-end
		@param back Index of the sorted end-front
	*/
	private void shakerSortWrapper(int front, int back)
	{
		// Base case
		if(front == back || back + 1 == front)
			return;
		
		// Generic case, bubble up min elements and sink large elements
		// Move the largest element to the end
		for(int i = front; i != back; ++i)
			if((this.data[i] - this.data[i + 1]) > 0)
				this.swapIndexedData(i, i + 1);

		// Move the smallest element to the begining
		for(int i = back - 1; i != front; --i)
			if((this.data[i] - this.data[i - 1]) < 0)
				this.swapIndexedData(i, i - 1);

		// Next pass
		this.shakerSortWrapper(front + 1, back - 1);	
	}

}