Archive

Archive for the ‘Java Sorting’ Category

Bubble sort in Java

Bubblesort is one of the simplest sorting methods. It also very inefficient. Though in the best case when the elements are already sorted, then its run time is O(n). Otherwise it is O(n^2).

package com.labeltop.sort;

public class BubbleSort {
	public void sort(Comparable[] comparables) {

		int size = comparables.length;

		// loop till swaps are being done
		while (true) {
			// reset it
			boolean foundSwap = false;

			// loop over values
			int i = 0;
			while (i < size) {
				// don't care about last value
				if (i == size - 1)
					break;

				// check for swap i.e. c1 > c2
				if (comparables[i].compareTo(comparables[i + 1]) > 0) {
					Comparable temp = comparables[i];
					comparables[i] = comparables[i + 1];
					comparables[i + 1] = temp;
					foundSwap = true;
				}

				// keep on...
				i++;
			}

			// check if there were any swaps
			if (!foundSwap)
				break;
		}
	}
}
Categories: Java, Java Misc, Java Sorting

Quicksort in Java

QuickSort is one of best sorting algorithms. While the worst case scenario is O(n^2), the average case is O(nlgn). Additionally, it is possible to implement in highly optimized way as well do several of its parts in parallel.

package com.labeltop.sort;

public class QuickSort {

	public void sort(Comparable[] c) {
		quicksort(c, 0, c.length-1);
	}

	private void quicksort(Comparable[] comparables, int start, int end) {

		// get a pivot point
		int pivot = start + ((int) (Math.random() * (end - start)));
		Comparable cPivot = comparables[pivot];

		// where to start on either side of pivot
		int left = start;
		int right = end;

		// loop till they overlap
		while (left <= right) {
			// find first on left that is bigger than pivot
			while (cPivot.compareTo(comparables[left]) > 0) {
				// more towards pivot
				left++;
			}

			// find first on right that is less than pivot
			while (cPivot.compareTo(comparables[right]) < 0) {
				// more towards pivot
				right--;
			}

			// exchange them
			if (left <= right) {
				Comparable temp = comparables[left];
				comparables[left] = comparables[right];
				comparables[right] = temp;
				//go to next ones towards the pivot
				left++;
				right--;
			}			
		}
		
		//recurse on left
		if (right > start) {
			quicksort(comparables, start, right);
		}
		//recurse on right
		if (left < end) {
			quicksort(comparables, left, end);
		}
	}

}
Categories: Java, Java Misc, Java Sorting

Merge Sort in Java

Here it is:

package com.labeltop.sort;

public class MergeSort {

	public void sort(Comparable[] c) {
		mergesort(c, 0, c.length-1);
	}

	private void mergesort(Comparable[] c, int start, int end) {
		//check if sort is needed
		if (c.length <= 1)
			return;
		
		//find middle
		int middle = start + ((end-start)/2);
		
		//create left list
		Comparable[] cLeft = new Comparable[middle-start+1];
		
		//create right list
		Comparable[] cRight = new Comparable[end-middle];
		
		//sort first half
		mergesort(cLeft, 0, cLeft.length-1);
		//sort second half
		mergesort(cRight, 0, cRight.length-1);
		
		//check the last on left iwth first on right to see if we need to merge
		if (cLeft[cLeft.length-1].compareTo(cRight[0]) <= 0) {
			System.arraycopy(cLeft, 0, c, 0, cLeft.length);
			System.arraycopy(cRight, 0, c, cLeft.length, cRight.length);
		}
		else {
			//now merge left and right
			mergeIt(c, cLeft, cRight);	
		}
	}
	
	private void mergeIt(Comparable[] merged, Comparable[] cLeft, Comparable[] cRight) {		
		//loop till both are done
		int iMerged = 0;
		int iLeft = 0;
		int iRight = 0;
		while (iLeft < cLeft.length && iRight < cRight.length)
		{
			if (cLeft[iLeft].compareTo(cRight[iRight]) <= 0)
			{
				//copy from left
				merged[iMerged] = cLeft[iLeft];
				iLeft++;				
			}
			else
			{
				//copy from right
				merged[iMerged] = cRight[iRight];
				iRight++;
			}
			
			iMerged++;
		}
		
		//check for remaining elements on left
		if (iLeft <= cLeft.length-1) {
			System.arraycopy(cLeft, iLeft, merged, iMerged, cLeft.length-iLeft);
			iMerged = iMerged + (cLeft.length-1-iLeft);
		}
		//check for remaining elements on right
		if (iRight <= cRight.length-1) {
			System.arraycopy(cRight, iRight, merged, iMerged, cRight.length-iRight);
			iMerged = iMerged + (cRight.length-1-iRight);
		}		
	}
}
Categories: Java, Java Misc, Java Sorting