Bi-Directional Bubble Sort Implementation in Java

[Note: This article was originally published in my another blog and has been migrated over here]

Definition:
Cocktail sort, also known as bidirectional bubble sort, cocktail shaker sort, shaker sort (which can also refer to a variant of selection sort), ripple sort, shuttle sort or happy hour sort, is a variation of bubble sort that is both a stable sorting algorithm and a comparison sort. The algorithm differs from bubble sort in that sorts in both directions each pass through the list. This sorting algorithm is only marginally more difficult than bubble sort to implement, and solves the problem with so-called turtles in bubble sort.

Differences From Bubble Sort:
Cocktail sort is a slight variation of bubble sort. It differs in that instead of repeatedly passing through the list from bottom to top, it passes alternately from bottom to top and then from top to bottom. It can achieve slightly better performance than a standard bubble sort. The reason for this is that bubble sort only passes through the list in one direction and therefore can only move items backward one step each iteration.

An example of a list that proves this point is the list (2,3,4,5,1), which would only need to go through one pass of cocktail sort to become sorted, but if using an ascending bubble sort would take four passes. However one cocktail sort pass should be counted as two bubble sort passes. Typically cocktail sort is less than two times faster than bubble sort.

Another optimization can be that the algorithm remembers where the last actual swap has been done. In the next iteration, there will be no swaps beyond this limit and the algorithm has shorter passes. As the Cocktail sort goes bidirectionally, the range of possible swaps, which is the range to be tested, will reduce per pass, thus reducing the overall running time.

[Source of above Text: Wikipedia.
Text is available under the Creative Commons Attribution/Share-Alike License]

The following is my implementation of Bidirectional Bubble Sort in Java.

/**
 * BidirectionalBubbleSort.java
 *
 * Author: Kushal Paudyal
 * www.icodejava.com
 *
 * Last Modified On: 2009-06-22
 */
package com.kushal.sort;

public class BidirectionalBubbleSort {

	/**
	 * The bidirectional bubble sort method that takes
	 * an array of unsorted integers, sorts them and
	 * returns a sorted array.
	 */
	public static int[] bidirectionalBubbleSort(int array[]) {
		int length = array.length;
		int j;
		int st = -1;
		while (st < length) {
			st++;
			length--;
			for (j = st; j < length; j++) {
				if (array[j] > array[j + 1]) {
					swap(array, j, j + 1);
				}
			}
			for (j = length; --j >= st;) {
				if (array[j] > array[j + 1]) {
					swap(array, j, j + 1);
				}
			}
		}
		return array;
	}

	/**
	 * Swapping The Elements at two different indexes of an Arary
	 */
	private static void swap(int[] anArray, int firstIndex, int secondIndex) {
		int temp = anArray[firstIndex];
		anArray[firstIndex] = anArray[secondIndex];
		anArray[secondIndex] = temp;
	}

	/**
	 * Method to print the content of any array.
	 */
	public static void printArray(int[] array) {
		for (int i = 0; i < array.length; i++)
			System.out.print(array[i] + "  ");

		System.out.println();
	}

	/**
	 * Testing the bidirectional bubble sort with some sample unsorted array of
	 * integers
	 */
	public static void main(String a[]) {
		int unsortedArray[] = { 121, 79, 24, 190, 203, 1, 33, 110 };

		System.out.print("Unsorted: \t");
		printArray(unsortedArray);

		int[] sortedArray = bidirectionalBubbleSort(unsortedArray);
		System.out.print("Sorted: \t");
		printArray(sortedArray);

	}
/*
* SANJAAL CORPS MAKES NO REPRESENTATIONS OR WARRANTIES ABOUT THE SUITABILITY OF
* THE SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
* TO THE IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
* PARTICULAR PURPOSE, OR NON-INFRINGEMENT. SANJAAL CORPS SHALL NOT BE LIABLE FOR
* ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING OR
* DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES.
*
* THIS SOFTWARE IS NOT DESIGNED OR INTENDED FOR USE OR RESALE AS ON-LINE
* CONTROL EQUIPMENT IN HAZARDOUS ENVIRONMENTS REQUIRING FAIL-SAFE
* PERFORMANCE, SUCH AS IN THE OPERATION OF NUCLEAR FACILITIES, AIRCRAFT
* NAVIGATION OR COMMUNICATION SYSTEMS, AIR TRAFFIC CONTROL, DIRECT LIFE
* SUPPORT MACHINES, OR WEAPONS SYSTEMS, IN WHICH THE FAILURE OF THE
* SOFTWARE COULD LEAD DIRECTLY TO DEATH, PERSONAL INJURY, OR SEVERE
* PHYSICAL OR ENVIRONMENTAL DAMAGE ("HIGH RISK ACTIVITIES"). SANJAAL CORPS
* SPECIFICALLY DISCLAIMS ANY EXPRESS OR IMPLIED WARRANTY OF FITNESS FOR
* HIGH RISK ACTIVITIES.
*/
}

=========================
Sample Output

Unsorted:     121  79  24  190  203  1  33  110
Sorted:     1  24  33  79  110  121  190  203

How to sort Alpha Numeric Strings in Java

[NOTE: This article was originally published in my another blog and has been migrated over here]

Alphanumeric is a combination of alphabetic and numeric characters (sometimes shortened to alphameric). In computing, the alphanumeric Strings can be seen very common to represent various codes etc.

Sorting the alphanumeric strings can sometimes be a trouble by using regular sort techniques. To have a proper meaning, these characters can neither be sorted numerically or alphabetically alone.

Take an example of following Strings:

“NUM10071”, “NUM9999”, “9997”, “9998”, “9996”, “9996F”

If we Sort them alphabetically, it becomes

9996, 9996F, 9997, 9998,NUM10071, NUM9999

If you observe the last two Strings, NUM10071 has come in front of NUM9999, which might not be the order we wanted to sort to. Considering NUM as the prefix, and that we wanted to sort rest of the numbers in ascending order, the proper meaningful sort would have been as follows:

9996, 9996F, 9997, 9998,NUM9999, NUM10071

If you are storing these codes in a database, writing the SQL to sort these String alphanumerically might be a huge performance issue.

So, in this tutorial, i will present you how to do the alphanumeric sorting in Java language, in a meaningful way.

Before I started writing this code, I had googled over to see the algorithms that could be applied, and I found a page by Sam Allen (http://dotnetperls.com/alphanumeric-sorting) who had implemented the same feature in C# recently.

My solution is inspired by his algorithm and I have converted the solution to Java with some changes. So I would like to appreciate his work.

Having said that, the following is a properly tested working code that I wrote in Java that can sort Alphanumeric Strings.

package com.kushal.utils;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @author Kushal Paudyal
 * www.icodejava.com
 * Last Modified On 16th July 2009
 *
 * This class is used to sort alphanumeric strings.
 *
 * My solution is inspired from a similar C# implementation available at
 * http://dotnetperls.com/alphanumeric-sorting written by Sam Allen
 */
public class AlphanumericSorting implements Comparator {
	/**
	 * The compare method that compares the alphanumeric strings
	 */
	public int compare(Object firstObjToCompare, Object secondObjToCompare) {
		String firstString = firstObjToCompare.toString();
		String secondString = secondObjToCompare.toString();

		if (secondString == null || firstString == null) {
			return 0;
		}

		int lengthFirstStr = firstString.length();
		int lengthSecondStr = secondString.length();

		int index1 = 0;
		int index2 = 0;

		while (index1 < lengthFirstStr && index2 < lengthSecondStr) {
			char ch1 = firstString.charAt(index1);
			char ch2 = secondString.charAt(index2);

			char[] space1 = new char[lengthFirstStr];
			char[] space2 = new char[lengthSecondStr];

			int loc1 = 0;
			int loc2 = 0;

			do {
				space1[loc1++] = ch1;
				index1++;

				if (index1 < lengthFirstStr) {
					ch1 = firstString.charAt(index1);
				} else {
					break;
				}
			} while (Character.isDigit(ch1) == Character.isDigit(space1[0]));

			do {
				space2[loc2++] = ch2;
				index2++;

				if (index2 < lengthSecondStr) {
					ch2 = secondString.charAt(index2);
				} else {
					break;
				}
			} while (Character.isDigit(ch2) == Character.isDigit(space2[0]));

			String str1 = new String(space1);
			String str2 = new String(space2);

			int result;

			if (Character.isDigit(space1[0]) && Character.isDigit(space2[0])) {
				Integer firstNumberToCompare = new Integer(Integer
						.parseInt(str1.trim()));
				Integer secondNumberToCompare = new Integer(Integer
						.parseInt(str2.trim()));
				result = firstNumberToCompare.compareTo(secondNumberToCompare);
			} else {
				result = str1.compareTo(str2);
			}

			if (result != 0) {
				return result;
			}
		}
		return lengthFirstStr - lengthSecondStr;
	}

	/**
	 * Testing the alphanumeric sorting
	 */
	public static void main(String[] args) {
		String[] alphaNumericStringArray = new String[] { "NUM10071",
				"NUM9999", "9997", "9998", "9996", "9996F" };

		/*
		 * Arrays.sort method can take an unsorted array and a comparator
		 * to give a final sorted array.
		 *
		 * The sorting is done according to the comparator that we have
		 * provided.
		 */
		Arrays.sort(alphaNumericStringArray, new AlphanumericSorting());

		for (int i = 0; i < alphaNumericStringArray.length; i++) {
			System.out.println(alphaNumericStringArray[i]);
		}

	}

}

=================
Here is the output:

9996
9996F
9997
9998
NUM9999
NUM10071


Update:
I got an email from one of the readers asking me if I could modify the program above so that it would treat zero padded numbers as the same such as “01”, “001” or “1” would be the same. The following is a modified version of this program that can do this. I just added a method to remove padding in the comparator.

Hello, first off, thank you for the code at: http://sanjaal.com/java/tag/sample-alphanumeric-sorting/ It is great to finally find a comparator that actually sorts 0,1,2,3,…10,12,20,…etc. The one problem is it also sorts 0,1,01,02,2,3,4…etc. Is there anyway you could update it to recognize the initial zeros and ignore them so that 000001 would be treated as 1? Again, many thanks and hope to hear back from you!

package com.kushal.utils;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @author Kushal Paudyal www.icodejava.com Last Modified On 16th July 2009
 * 
 *         This class is used to sort alphanumeric strings.
 * 
 *         My solution is inspired from a similar C# implementation available at
 *         http://dotnetperls.com/alphanumeric-sorting written by Sam Allen
 */
public class AlphanumericSorting implements Comparator {
	/**
	 * The compare method that compares the alphanumeric strings
	 */
	public int compare(Object firstObjToCompare, Object secondObjToCompare) {
		String firstString = removePadding(firstObjToCompare.toString());
		String secondString = removePadding(secondObjToCompare.toString());

		if (secondString == null || firstString == null) {
			return 0;
		}

		int lengthFirstStr = firstString.length();
		int lengthSecondStr = secondString.length();

		int index1 = 0;
		int index2 = 0;

		while (index1 < lengthFirstStr && index2 < lengthSecondStr) {
			char ch1 = firstString.charAt(index1);
			char ch2 = secondString.charAt(index2);

			char[] space1 = new char[lengthFirstStr];
			char[] space2 = new char[lengthSecondStr];

			int loc1 = 0;
			int loc2 = 0;

			do {
				space1[loc1++] = ch1;
				index1++;

				if (index1 < lengthFirstStr) {
					ch1 = firstString.charAt(index1);
				} else {
					break;
				}
			} while (Character.isDigit(ch1) == Character.isDigit(space1[0]));

			do {
				space2[loc2++] = ch2;
				index2++;

				if (index2 < lengthSecondStr) {
					ch2 = secondString.charAt(index2);
				} else {
					break;
				}
			} while (Character.isDigit(ch2) == Character.isDigit(space2[0]));

			String str1 = new String(space1);
			String str2 = new String(space2);

			int result;

			if (Character.isDigit(space1[0]) && Character.isDigit(space2[0])) {
				Integer firstNumberToCompare = new Integer(
						Integer.parseInt(str1.trim()));
				Integer secondNumberToCompare = new Integer(
						Integer.parseInt(str2.trim()));
				result = firstNumberToCompare.compareTo(secondNumberToCompare);
			} else {
				result = str1.compareTo(str2);
			}

			if (result != 0) {
				return result;
			}
		}
		return lengthFirstStr - lengthSecondStr;
	}

	/**
	 * The purpose of this method is to remove any zero padding for numbers.
	 * 
	 * Otherwise returns the input string.
	 * 
	 * 
	 * @param string
	 * @return
	 */
	private String removePadding(String string) {
		String result="";
		try{
			result+= Integer.parseInt(string.trim());
		} catch (Exception e) {
			result= string;
		}
		return result;
	}

	/**
	 * Testing the alphanumeric sorting
	 */
	public static void main(String[] args) {
		String[] alphaNumericStringArray = new String[] { "NUM10071",
				"NUM9999", "9997", "9998", "9996", "9996F", "0001", "01", "1", "001" };

		/*
		 * Arrays.sort method can take an unsorted array and a comparator to
		 * give a final sorted array.
		 * 
		 * The sorting is done according to the comparator that we have
		 * provided.
		 */
		Arrays.sort(alphaNumericStringArray, new AlphanumericSorting());

		for (int i = 0; i < alphaNumericStringArray.length; i++) {
			System.out.println(alphaNumericStringArray[i]);
		}

	}

}

Following is the output of running this program. Note that the zero padded elements of equal value are sorted as stable meaning they appear in the same order as the input.

0001
01
1
001
9996
9996F
9997
9998

Merge Sort Implementation in Java to Sort An Array of Integers

Merge Sort Animation. Source: Wikipedia / CC

Merge Sort is  comparison based divide and conquer algorithm to sort data. This sort can be implemented recursively.

Algorithm Steps:

  1. If the number of items to sort is 0 or 1, return
  2. Sort the first and second half of the array recursively
  3. Merge the two sorted halves into a sorted array.

Complexity:

  • Base Case: O(nlogn)
  • Average Case: O(nlogn)
  • Worst Case: O(nlogn)

Java Implementation Of Merge Sort:

package com.icodejava.blog;

import java.util.Arrays;

/**
 * @author Kushal Paudyal
 * www.icodejava.com
 * Created On -  Feb 20, 2014
 * Last Modified On - Feb 20, 2014
 *
 * MERGE SORT STEPS
 * If the number of items to sort is 0 or 1, return
 * Sort the first and second half of the array recursively
 * Merge the two sorted halves into a sorted array.
 *
 * COMPLEXITY:
 * Base Case: nlogn
 * Average Case: nlogn
 * Worst Case: nlogn

 */
public class MergeSort {

	public static void main(String args[]) {

		int[] numberArray = { 5, 4, 7, 3, 3, 9, 0, -11, 2, 8, 6 };

		sort(numberArray);
	}

	private static void sort(int[] numberArray) {

		System.out.println("\nINPUT ARRAY:" + Arrays.toString(numberArray));

		int[] tempArray = new int[numberArray.length];

		mergeSort(numberArray, tempArray, 0, numberArray.length - 1);

		System.out.println("SORTED ARRAY:" + Arrays.toString(numberArray));

	}

	private static void mergeSort(int[] data, int[] tempArray, int low, int high) {
		/** If low is smaller than high, array is not sorted, otherwise it is. */
		if (low < high) {

			int middle = (low + high) / 2;

			System.out.println(" Divide Step -  low:" + low + " middle:" + middle + " high:" + high);

			/** Recursively Sort the left side of the array **/
			mergeSort(data, tempArray, low, middle);

			/** Recursively Sort the right side of the array **/
			mergeSort(data, tempArray, middle + 1, high);

			/** Merge the sorted arrays **/
			merge(data, tempArray, low, middle, high);
		}
	}

	/**
	 *
	 * @param data
	 *            - Original Unsorted or Partially Sorted Array
	 * @param tempArray
	 *            - Temporary Helper Array
	 * @param low
	 *            - Starting Index of Left Array
	 * @param middle
	 * @param high
	 *            - Ending Index of Right Array
	 *
	 *            This method merges two sorted portions of an array using
	 *            temporary array.
	 */
	private static void merge(int[] data, int[] tempArray, int low, int middle, int high) {

		// Copy both parts into the temporary helper array
		for (int i = low; i <= high; i++) {
			tempArray[i] = data[i];
		}

		int i = low; // Start of Left Array
		int j = middle + 1; // Start of right Array
		int k = low;

		// Copy the smallest values from either the left or the right side back
		// to the original array
		while (i <= middle && j <= high) {
			if (tempArray[i] <= tempArray[j]) {
				data[k] = tempArray[i];
				i++;
			} else {
				data[k] = tempArray[j];
				j++;
			}
			k++;
		}
		// Copy the rest of the left side of the array into the target array
		while (i <= middle) {
			data[k] = tempArray[i];
			k++;
			i++;
		}

		System.out.println("   Merge Step (low:" + low + ",middle:" + middle + ",high:" + high + ") Original "
				+ Arrays.toString(data) + " Temporary" + Arrays.toString(tempArray));

	}

}

The output of running above program. The intermediates steps have been printed for the helping the readers understand the working of this sorting. You might have to scroll right to view the full output.

INPUT ARRAY:[5, 4, 7, 3, 3, 9, 0, -11, 2, 8, 6]
 Divide Step -  low:0 middle:5 high:10
 Divide Step -  low:0 middle:2 high:5
 Divide Step -  low:0 middle:1 high:2
 Divide Step -  low:0 middle:0 high:1
   Merge Step (low:0,middle:0,high:1) Original [4, 5, 7, 3, 3, 9, 0, -11, 2, 8, 6] Temporary[5, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0]
   Merge Step (low:0,middle:1,high:2) Original [4, 5, 7, 3, 3, 9, 0, -11, 2, 8, 6] Temporary[4, 5, 7, 0, 0, 0, 0, 0, 0, 0, 0]
 Divide Step -  low:3 middle:4 high:5
 Divide Step -  low:3 middle:3 high:4
   Merge Step (low:3,middle:3,high:4) Original [4, 5, 7, 3, 3, 9, 0, -11, 2, 8, 6] Temporary[4, 5, 7, 3, 3, 0, 0, 0, 0, 0, 0]
   Merge Step (low:3,middle:4,high:5) Original [4, 5, 7, 3, 3, 9, 0, -11, 2, 8, 6] Temporary[4, 5, 7, 3, 3, 9, 0, 0, 0, 0, 0]
   Merge Step (low:0,middle:2,high:5) Original [3, 3, 4, 5, 7, 9, 0, -11, 2, 8, 6] Temporary[4, 5, 7, 3, 3, 9, 0, 0, 0, 0, 0]
 Divide Step -  low:6 middle:8 high:10
 Divide Step -  low:6 middle:7 high:8
 Divide Step -  low:6 middle:6 high:7
   Merge Step (low:6,middle:6,high:7) Original [3, 3, 4, 5, 7, 9, -11, 0, 2, 8, 6] Temporary[4, 5, 7, 3, 3, 9, 0, -11, 0, 0, 0]
   Merge Step (low:6,middle:7,high:8) Original [3, 3, 4, 5, 7, 9, -11, 0, 2, 8, 6] Temporary[4, 5, 7, 3, 3, 9, -11, 0, 2, 0, 0]
 Divide Step -  low:9 middle:9 high:10
   Merge Step (low:9,middle:9,high:10) Original [3, 3, 4, 5, 7, 9, -11, 0, 2, 6, 8] Temporary[4, 5, 7, 3, 3, 9, -11, 0, 2, 8, 6]
   Merge Step (low:6,middle:8,high:10) Original [3, 3, 4, 5, 7, 9, -11, 0, 2, 6, 8] Temporary[4, 5, 7, 3, 3, 9, -11, 0, 2, 6, 8]
   Merge Step (low:0,middle:5,high:10) Original [-11, 0, 2, 3, 3, 4, 5, 6, 7, 8, 9] Temporary[3, 3, 4, 5, 7, 9, -11, 0, 2, 6, 8]
SORTED ARRAY:[-11, 0, 2, 3, 3, 4, 5, 6, 7, 8, 9]