Array Max Integer Finder (With Big O Analysis)

This tutorial shows you an implementation of three different methods of searching for the maximum number in an Integer array. The array is assumed to hold positive integers.

  1. First method findMaxCompareMax() assumes the first number on the array to be maximum and the loops through other numbers in sequence and replaces the current maximum with the new maximum. When all the elements are checked, we have a maximum number.
  2. The second method findMaxCompareAll() takes an array element and compares it with every other element in the array to see if it is maximum. If it is not, then it proceeds with the next element.
  3. The third method findMaxCompareAfterIndex() This method takes an array element and compare it with other elements in the array to see if it is maximum. If it is not, then it proceeds with the next element. However, this method does not compare every element from the beginning. To avoid redundant comparing, it only compares with the remaining elements in the array (i.e. position + 1 onwards)

Check the code comments for the Big O Analysis of these three methods.

package com.icodejava.blog.published.search;

import java.util.Arrays;

/**
 * 
 * This class is used to demonstrate 3 different ways of finding a maximum
 * number in an Integer Array holding positive integer numbers.
 * 
 * Also provides a Big O analysis.
 */
public class MaxIntegerFinder {

    public static void main(String args[]) {

        int[] numbers = {5, 4, 9, 2, 2, 1, 10, 21, 6 };
        
        System.out.println("Source Array " + Arrays.toString(numbers));

        findMaxCompareMax(numbers);

        findMaxCompareAll(numbers);

        findMaxCompareAfterIndex(numbers);

    }


    /**
     * This method assumes the first number on the array to be the maximum
     * You can also assume the last one to be the max and compare it in reverse.
     * It then loops through other numbers in the array and replaces the 
     * current maximum with the new maximum it finds.
     * 
     * Complexity: O(n) where n is the number of elements in the array
     */
    private static int findMaxCompareMax(int[] numbers) {

        if (numbers.length < 1 ) {
            return 0;
        }
        
        int currentMax = numbers[0];
        for (int i = 1 ; i < numbers.length; i++) { if(numbers[i] > currentMax) {
                currentMax = numbers[i];
            }
        }
        
        System.out.println("Max Number using findMaxCompareMax -> " + currentMax);
        return currentMax;
        
    }
    
    /**
     * This method takes an array element and compare it with 
     * every other element in the array to see if it is maximum.
     * 
     * If it is not, then it proceeds with the next element
     * 
     * Complexity: O(n^2) in worst case and O(n) in best case 
     * where n is the number of elements in the array
     * 
     * Best case scenario is where the first element itself is maximum
     * Worst case scenario is where the last element is maximum.
     */
    private static int findMaxCompareAll(int[] numbers) {

        if (numbers.length < 1) {
            return 0;
        }

        int max = -1;

        for (int i = 0; i < numbers.length; i++) {
            for (int j = 0; j < numbers.length; j++) {
                if (max < numbers[j]) { max = numbers[j]; break; } } } System.out.println("Max Number using findMaxCompareAll -> " + max);
        return max;

    }
    
    /**
     * This method takes an array element and compare it with 
     * other elements in the array to see if it is maximum.
     * 
     * If it is not, then it proceeds with the next element. 
     * 
     * However, this method does not compare every element from the beginning. 
     * To avoid redundant comparing, it only compares with the remaining elements
     * in the array (i.e. position + 1 onwards)
     * 
     * Complexity: O(n^2) in worst case and O(n) in best case 
     * where n is the number of elements in the array
     * 
     * Best case scenario is where the first element itself is maximum
     * Worst case scenario is where the last element is maximum.
     */
    private static int findMaxCompareAfterIndex(int[] numbers) {

        if (numbers.length < 1 ) {
            return 0;
        }
        
        int max=-1;
        
        for (int i = 0 ; i < numbers.length; i++) {
            for(int j = i ; j< numbers.length; j++) {
                if(max < numbers [j]) { max = numbers[j]; break; } } } System.out.println("Max Number using findMaxCompareAfterIndex -> " + max);
        return max;
    }

}

OUTPUT:

Source Array [5, 4, 9, 2, 2, 1, 10, 21, 6]
Max Number using findMaxCompareMax -> 21
Max Number using findMaxCompareAll -> 21
Max Number using findMaxCompareAfterIndex -> 21

Java Implementation – ROT-13 Encoding Algorithm

ROT-13 is the simplest of all encoding algorithms. The idea is simple, rotate the characters by 13. If you assume characters A-Z (or a-z) to be in a circle, for any characters, go to 13 characters ahead in the circle and replace it with that character.

The following diagram taken from Wikipedia (under wikipedia commons license), demonstrates the character substitution fact clearly.

Interestingly, if you encode a plain text, to decode it, you need to re-encode it.

That means for a character ABC, encode (encode( ABC)) is ABC

The following is the Java Implementation of ROT-13 Algorithm. Since having only A-Z or a-z characters may not suffice, I have added a condition where other characters will remain the same.

/**
 * @author Kushal Paudyal
 * www.sanjaal.com/java
 * Last Modified on 5th September 2008
 */
package com.kushal.utilities;
/**Java Implementation of ROT-13 Encoding algorithm**/
public class Rot13Encryption {

	public static void main(String args[]) {
		//Original Text
		String plainText=&quot;Sanjaal.Com&quot;;
		//Let's Encode It
		String encodedText=rot13Encode(plainText);
		//Then Decide It
		String decodedText=rot13Encode(encodedText);

		System.out.println(&quot;Original Text: tt&quot;+plainText);
		System.out.println(&quot;After ROT-13 Encoding: t&quot;+encodedText);
		System.out.println(&quot;After ROT-13 Decoding: t&quot;+decodedText);
	}

	/**
	 * @param textToEncode
	 * @return encoded (or decoded)text.
	 * Note: if you encode a text, and encode the result again,
	 * you will get the original text.
	 */
	public static String rot13Encode(String textToEncode) {
		String encodedText = &quot;&quot;;
		int textLength = textToEncode.length();

		for (int i = 0; i &amp;lt; textLength; i++) {
			char currentChar = textToEncode.charAt(i);
			if ((currentChar &amp;gt;= 65 &amp;amp;&amp;amp; currentChar &amp;lt;= 77)
					|| (currentChar &amp;gt;= 97 &amp;amp;&amp;amp; currentChar &amp;lt;= 109)) {
				encodedText += (char) (currentChar + 13);
			} else if ((currentChar &amp;gt;= 78 &amp;amp;&amp;amp; currentChar &amp;lt;= 90)
					|| (currentChar &amp;gt;= 110 &amp;amp;&amp;amp; currentChar &amp;lt;= 122)) {
				encodedText += (char) (currentChar - 13);
			} else {
				encodedText += currentChar;
			}
		}
		return encodedText;
	}

}


—————————————-
Here is the sample output:
—————————————-

Original Text:                     Sanjaal.Com
After ROT-13 Encoding:     Fnawnny.Pbz
After ROT-13 Decoding:     Sanjaal.Com

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