Bubble Sorting A String Array in Ascending And Descending Order

In my previous article, I provided an example of how you can do integer array sorting using bubble sort. In this article, I have provided a solution on how to do String array sort.

This program:

  • Sorts a string array in ascending order
  • Sorts a string array in descending order
  • Uses String’s in-built compareTo method to compare to entities.

package com.icodejava.blog.datastructure;

/**
 * @author Kushal Paudyal
 * www.icodejava.com
 * Created On -  Feb 18, 2014
 * Last Modified On - Feb 18, 2014
 */
public class BubbleSortString {
	
	public static void main(String args []) {
		String [] unsortedArray = {"M","F","B","E","Z","F","D","Q","R","S","H","A"};
		printArray("Unsorted Array:", unsortedArray);
		
		String [] sortedArray = bubbleSortAscending(unsortedArray);
		
		printArray("Sorted Array (Ascending):", sortedArray);
		
		sortedArray = bubbleSortDescending(unsortedArray);
		
		printArray("Sorted Array (Descending):", sortedArray);
		
		
	}

	
	private static String[] bubbleSortDescending(String[] unsortedArray) {

		for (int index = unsortedArray.length - 1; index > 0; index--) {
			for (int bubbleIndex = 0; bubbleIndex < index; bubbleIndex++) {
				/**
				 * using String's compareTo method to see if one element is
				 * bigger than the other.
				 */
				if (unsortedArray[index].compareTo(unsortedArray[bubbleIndex]) > 0) {
					swap(unsortedArray, index, bubbleIndex);
				}

			}
		}

		return unsortedArray; // which is now sorted
	}

	private static String[] bubbleSortAscending(String[] unsortedArray) {

		for (int index = unsortedArray.length - 1; index > 0; index--) {
			for (int bubbleIndex = 0; bubbleIndex < index; bubbleIndex++) {
				/**
				 * using String's compareTo method to see if one element is
				 * bigger than the other.
				 */
				if (unsortedArray[index].compareTo(unsortedArray[bubbleIndex]) < 0) {
					swap(unsortedArray, index, bubbleIndex);
				}

			}
		}

		return unsortedArray; // which is now sorted
	}

	private static void swap(String[] unsortedArray, int firstIndex, int secondIndex) {
		if(unsortedArray == null 
				|| firstIndex < 0 
				|| firstIndex > unsortedArray.length 
				|| secondIndex < 0  
				|| secondIndex > unsortedArray.length) {
			return;
		}
		String tempString = unsortedArray[firstIndex];
		unsortedArray[firstIndex] = unsortedArray[secondIndex];
		unsortedArray[secondIndex] = tempString;

	}
	
	private static void printArray(String string, String[] unsortedArray) {

		if (unsortedArray != null && unsortedArray.length > 0) {
			System.out.print(string + " ");
			for (int i = 0; i < unsortedArray.length; i++) {
				System.out.print((i > 0 ? "," : "") + unsortedArray[i]);
			}
		}

		System.out.println();

	}
}

The out of running above program:

Unsorted Array: M,F,B,E,Z,F,D,Q,R,S,H,A
Sorted Array (Ascending): A,B,D,E,F,F,H,M,Q,R,S,Z
Sorted Array (Descending): Z,S,R,Q,M,H,F,F,E,D,B,A

Bubble Sorting An Integer Array In Ascending and Descending Order

Bubble Sort Working

Bubble Sort Definition:
Bubble sort is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted.

Complexity:
Worst Case: O(n^2) – reverse ordered list
Best Case: O(n) – fully sorted list

Note:

  • Bubble Sort is not a good solution if you have a large number of items to be sorted. This is due to the time Complexity.
  • Bubble Sort can however be used to quickly find if a list is already sorted.

Below is my java implementation of Bubble Sort algorithm. I have provided methods to do sorting in both ascending and descending order. This program sorts an integer array, although it can also be extended to do sorting for doubles and floats.

package com.icodejava.blog.datastructure;

/**
 * @author Kushal Paudyal
 * www.icodejava.com
 * Created On - Feb 18, 2014
 * Last Modified On - Feb 18, 2014
 */
public class BubbleSortInteger {

	public static void main(String args[]) {
		int[] unsortedArray = { 6, 5, 2, 5, 6, 3, 4, 2, 7, 8, 9, 0 };
		printArray("Unsorted Array:", unsortedArray);

		int[] sortedArray = bubbleSortAscending(unsortedArray);

		printArray("Sorted Array (Ascending):", sortedArray);

		sortedArray = bubbleSortDescending(unsortedArray);

		printArray("Sorted Array (Descending):", sortedArray);

	}

	private static int[] bubbleSortDescending(int[] unsortedArray) {

		for (int index = unsortedArray.length - 1; index > 0; index--) {
			for (int bubbleIndex = 0; bubbleIndex < index; bubbleIndex++) {

				if (unsortedArray[index] > unsortedArray[bubbleIndex]) {
					swap(unsortedArray, index, bubbleIndex);
				}

			}
		}

		return unsortedArray; // which is now sorted
	}

	private static int[] bubbleSortAscending(int[] unsortedArray) {

		for (int index = unsortedArray.length - 1; index > 0; index--) {
			for (int bubbleIndex = 0; bubbleIndex < index; bubbleIndex++) {

				if (unsortedArray[index] < unsortedArray[bubbleIndex]) {
					swap(unsortedArray, index, bubbleIndex);
				}

			}
		}

		return unsortedArray; // which is now sorted
	}

	private static void swap(int[] unsortedArray, int firstIndex, int secondIndex) {
		if (unsortedArray == null || firstIndex < 0 || firstIndex > unsortedArray.length
				|| secondIndex < 0 || secondIndex > unsortedArray.length) {
			return;
		}
		int tempInteger = unsortedArray[firstIndex];
		unsortedArray[firstIndex] = unsortedArray[secondIndex];
		unsortedArray[secondIndex] = tempInteger;

	}

	private static void printArray(String string, int[] array) {

		if (array != null && array.length > 0) {
			System.out.print(string + " ");
			for (int i = 0; i < array.length; i++) {
				System.out.print((i > 0 ? "," : "") + array[i]);
			}
		}

		System.out.println();

	}

}

The out of running above program:

Unsorted Array: 6,5,2,5,6,3,4,2,7,8,9,0
Sorted Array (Ascending): 0,2,2,3,4,5,5,6,6,7,8,9
Sorted Array (Descending): 9,8,7,6,6,5,5,4,3,2,2,0

How to split strings and separate the words with spaces

Split Your String !

Given a string with no spaces in it, how would you split the strings and insert spaces? That’s one of the simple looking yet very vague requirement and is sometimes asked in the interview.

You need to either make assumptions or seek clarifications on many things.

  1. Can the String to split be null? Can it be blank?
  2. Where are the words to compare to located? Is there a dictionary, is there a list of words? Do the words reside in a file?
  3. Can the unslpit string contain more than two words?
  4. And many others.

In the following program that I have written, I have assumed that the string to split can be null, the words to lookup are located in a HashMap and the unsplit word contains only two words (You will see that when I am passing a three word string, the program cannot split the string). Another assumption is that all the words in the HashMap are uppercase and the splitting is case insensitive.

package com.icodejava.blog.datastructure;

import java.util.HashMap;
import java.util.Map;

/**
 * @author Kushal Paudyal 
 * www.icodejava.com 
 * Created On - Feb 15, 2014 
 * Last Modified On - Feb 15, 2014
 */
public class StringSplitter {

	private static final Map<String, String> DICTIONARY = new HashMap<String, String>();

	public static void main(String args[]) {
		DICTIONARY.put("GOOGLE", "GOOGLE");
		DICTIONARY.put("INTERVIEW", "INTERVIEW");
		DICTIONARY.put("QUESTION", "QUESTIONS");

		String stringToSplit = "interviewquestions";

		splitString(DICTIONARY, stringToSplit);
		
		stringToSplit = "googleinterviewquestions";
		
		splitString(DICTIONARY, stringToSplit);
		
		//Let's try on more with null string.
		splitString(DICTIONARY, null);
		

	}

	private static void splitString(Map<String, String> LOOKUP_DICTIONARY, String stringToSplit) {

		boolean splitSuccessful = false;

		if (stringToSplit != null && stringToSplit.length() > 0) {
			for (int index = 0; index < stringToSplit.length(); ++index) {
				String leftSubstring = stringToSplit.substring(0, index);
				String rightSubString = stringToSplit.substring(index);

				System.out.println("LEFT: " + leftSubstring + " RIGHT: " + rightSubString);

				if (DICTIONARY.containsValue(leftSubstring.toUpperCase()) 
						&& DICTIONARY.containsValue(rightSubString.toUpperCase())) {
					
					System.out.println("MATCH FOUND. SPLIT SUBSTRING: " 
						+ leftSubstring + " " + rightSubString + "\n\n");
					
					splitSuccessful = true;
					break;

				}

			}
		}

		if (!splitSuccessful) {
			System.out.println("Could not split the word! Not found in dictionary\n\n");
		}

	}

}

Here is the output of running above piece of code.

LEFT:  RIGHT: interviewquestions
LEFT: i RIGHT: nterviewquestions
LEFT: in RIGHT: terviewquestions
LEFT: int RIGHT: erviewquestions
LEFT: inte RIGHT: rviewquestions
LEFT: inter RIGHT: viewquestions
LEFT: interv RIGHT: iewquestions
LEFT: intervi RIGHT: ewquestions
LEFT: intervie RIGHT: wquestions
LEFT: interview RIGHT: questions
MATCH FOUND. SPLIT SUBSTRING: interview questions


LEFT:  RIGHT: googleinterviewquestions
LEFT: g RIGHT: oogleinterviewquestions
LEFT: go RIGHT: ogleinterviewquestions
LEFT: goo RIGHT: gleinterviewquestions
LEFT: goog RIGHT: leinterviewquestions
LEFT: googl RIGHT: einterviewquestions
LEFT: google RIGHT: interviewquestions
LEFT: googlei RIGHT: nterviewquestions
LEFT: googlein RIGHT: terviewquestions
LEFT: googleint RIGHT: erviewquestions
LEFT: googleinte RIGHT: rviewquestions
LEFT: googleinter RIGHT: viewquestions
LEFT: googleinterv RIGHT: iewquestions
LEFT: googleintervi RIGHT: ewquestions
LEFT: googleintervie RIGHT: wquestions
LEFT: googleinterview RIGHT: questions
LEFT: googleinterviewq RIGHT: uestions
LEFT: googleinterviewqu RIGHT: estions
LEFT: googleinterviewque RIGHT: stions
LEFT: googleinterviewques RIGHT: tions
LEFT: googleinterviewquest RIGHT: ions
LEFT: googleinterviewquesti RIGHT: ons
LEFT: googleinterviewquestio RIGHT: ns
LEFT: googleinterviewquestion RIGHT: s
Could not split the word! Not found in dictionary


Could not split the word! Not found in dictionary