Insertion Sort in Java

Background

 Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. Each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.

At any iteration i, elements 0 to i-1 will be sorted and with each increment in i previous list of sorted elements will grow.

Code :

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * User: aniket
 * Date: 12/2/14
 * Time: 11:14 AM
 */
public class InsertionSort {


    public void sort(int[] array) {

        for(int i=1;i<array.length;i++){
            int j = i;
            while(j>0 && array[j-1]>array[j]){
                Swapper.inMemorySwap(array,j-1,j);
                j--;
            }
        }

    }

    public static void main(String args[]){

        int[] array = new int[]{2,7,5,9,4,7,1,0};
        System.out.println("Array Before Sort : " + Arrays.toString(array));
        new InsertionSort().sort(array);
        System.out.println("Array after Sort : " + Arrays.toString(array));

    }
}

Output :

Array Before Sort : [2, 7, 5, 9, 4, 7, 1, 0]
Array after Sort : [0, 1, 2, 4, 5, 7, 7, 9]

A slightly better version would be where you don't have to swap numbers every time -

    public static int[] insertionSort(int[] array) {
        
        for(int i=1; i <array.length; i++) {
            int key = array[i];
            int j = i - 1;
            while(j>=0 && array[j] > key ) {
                array[j+1] = array[j];
                j--;
            }
            array[j+1] = key;
        }
        return array;
    }

Complexity

 Worst case complexity is O(N2) like bubble sort. However the best case is O(N) - already sorted array. Both bubble sort and insertion sort are not suitable for sorting large numbers.

Related Links

• Insertion sort(Wiki)
  

Bubble Sort in Java

Background

 In bubble sort the largest elements goes to the end of the array and the remaining array (0 - array.length-i) is sorted again. It's like a bubble where on each iteration largest element goes to the end.

Code : 

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * User: aniket
 * Date: 11/2/14
 * Time: 8:29 PM
 */
public class BubbleSort {

    public void sort(int[] array) {

        int arrayLength = array.length;
        for(int i=0;i<arrayLength;i++){
            for( int j=0;j<arrayLength-i-1;j++){
                if(array[j] > array[j+1]){
                    Swapper.inMemorySwap(array,j,j+1);
                }
            }
        }
    }

    public static void main(String args[]){

        int[] array = new int[]{2,7,5,9,4,7,1,0};
        System.out.println("Array Before Sort : " + Arrays.toString(array));
        new BubbleSort().sort(array);
        System.out.println("Array after Sort : " + Arrays.toString(array));

    }

}

Complexity

Bubble sort has worst-case and average complexity both O(n2), where n is the number of items being sorted.

Output :

Array Before Sort : [2, 7, 5, 9, 4, 7, 1, 0]
Array after Sort : [0, 1, 2, 4, 5, 7, 7, 9]

 As we know that bubble sort runs in O(N^2) time complexity. If this question is asked(mostly in the 1st round to make sure you know basic sorting algorithms)  then it will mostly be followed by a counter question. How can you optimize bubble sort ?

Bubble Sort Optimization

If you notice we iterate over all the indexes and for each outer iteration we bubble out the largest number to the end. Now if at some index the array is completely sorted we need to proceed iterating on further indexes. That is precisely what we are going to do. Keep a boolean flag denoting if array is completely sorted or not. At the outer loop initialize it to true and make it false if any iteration of inner for loop happens denoting array is not completely sorted yet. When inner loop does not execute it means array is completely sorted and there is no need to proceed. In this case flag will be true which we initialized in outer loop. If such condition happens i.e if flag is true than break from the loops and print the sorted array.

Code :

package Sorts;

import java.util.Arrays;

/**
 * Created by Aniket on 2/19/14.
 */
public class BubbleSort {

    public void sort(int[] array) {

        int arrayLength = array.length;
        for(int i=0;i<arrayLength;i++){
            boolean isSorted = true;
            for( int j=0;j<arrayLength-i-1;j++){
                if(array[j] > array[j+1]){
                    isSorted = false;
                    Swapper.inMemorySwap(array,j,j+1);
                }
            }
            if(isSorted){
                System.out.println("Breaking at index : " + i);
                break;
            }
        }
    }

    public static void main(String args[]){
        int[] array = new int[]{2,7,5,9,4,7,1,0,1,2,3,};
        System.out.println("Array Before Sort : " + Arrays.toString(array));
        new BubbleSort().sort(array);
        System.out.println("Array after Sort : " + Arrays.toString(array));
    }


}

Output :

Array Before Sort : [2, 7, 5, 9, 4, 7, 1, 0, 1, 2, 3]
Breaking at index : 7
Array after Sort : [0, 1, 1, 2, 2, 3, 4, 5, 7, 7, 9]


NOTE :  Swapper.inMemorySwap in a normal swap function where data at two indexes are swapper. You can choose to use a temporary variable or not (see swapping of variables in related links section).

Sample method could be -

    public void swap(int[] array, int x, int y) {
         array[x] = array[x] + array[y];
        array[y] = array[x] - array[y];
        array[x] = array[x] - array[y];
    }

Related Links

• Swapping two numbers without using temporary variable
• Bubble Sort(Wiki) 

Finding minimum window containing given subsequence

Question : 

It was long description for a DNA problem. Main DNA sequence(a string) is given (let say strDNA) and another string to search for(let say strPat). You have to find the minimum length window in strDNA where strPat is subsequence. (GeeksForGeeks)

Code : 

package Miscellaneous;

/**
 * Created by Aniket on 2/8/14.
 */
public class SmallestCommonSubSequenceFinder {

    String strDna;
    String strPat;


    char[] patternArray;
    char[] dnaArray;


    int bestLength;
    int bestStart;
    int bestEnd;

    public int getBestEnd() {
        return bestEnd;
    }

    public void setBestEnd(int bestEnd) {
        this.bestEnd = bestEnd;
    }

    public int getBestStart() {
        return bestStart;
    }

    public void setBestStart(int bestStart) {
        this.bestStart = bestStart;
    }

    public int getBestLength() {
        return bestLength;
    }

    public void setBestLength(int bestLength) {
        this.bestLength = bestLength;
    }


    public SmallestCommonSubSequenceFinder(String strDna, String strPat){
        this.strDna = strDna;
        this.strPat = strPat;
        this.patternArray = strPat.toCharArray();
        this.dnaArray = strDna.toCharArray();
    }

    public int getStartIndex(int start){
        for(int i=start;i<dnaArray.length;i++){
            if(dnaArray[i] == patternArray[0]){
                return i;
            }
        }
        return -1;
    }

    public void findMinSubSeqDNAWindow(int start,int currIndex, int comparingIndex, boolean isStart){

        if(start >= dnaArray.length || currIndex >= dnaArray.length){
            return;
        }

        while(currIndex < dnaArray.length && dnaArray[currIndex] != patternArray[comparingIndex]){
            currIndex++;
        }

        //check if currIndex has exceeded the array length

        if(currIndex >= dnaArray.length){
            //element not found
            return;
        }

        if(isStart){
            start = currIndex;
            isStart = false;
        }

        if(comparingIndex == patternArray.length-1){
            int lengthOfSubSeq = currIndex - start + 1;
            if(bestLength == 0 || lengthOfSubSeq < bestLength){
                bestLength = lengthOfSubSeq;
                bestStart = start;
                bestEnd = currIndex;
            }
            //start finding new sub sequence
            findMinSubSeqDNAWindow(start + 1, start + 1, 0, true);
        }
        else {
            //go for next character
            findMinSubSeqDNAWindow(start, currIndex+1, comparingIndex+1, isStart);
        }
    }

    public static void main(String args[]){
        String strPat = "bdf";
        String strDna = "abcdefgbdf";

        SmallestCommonSubSequenceFinder finder = new SmallestCommonSubSequenceFinder(strDna,strPat);
        finder.findMinSubSeqDNAWindow(0,0,0,true);
        System.out.println("Best Length : " + finder.getBestLength());
        System.out.println("BestStart : " + finder.getBestStart());
        System.out.println("Best End : " + finder.getBestEnd());
    }
}

Output :

Best Length : 3
BestStart : 7
Best End : 9

Finding Earnings of a Zoo Driver

Question : 

There is a zoo and there are several groups(number of groups:K) of people for tour. Each group is having different size (g1,g2,g3…gK). There is one bus with capacity C. Journey starts from a point and bus will come back to the same point. A group can only be included in the bus if all the members of the groups can be accumulated in bus. After coming back from the tour, each group in the bus will again wait in the queue at the bus-stand. Bus-driver earns a rupee for each person travelled. You have to find the earning of the bus driver after R rounds.

Example : 

Number of groups G = 4

 Group size for each group : 2 4 3 5

 Bus capacity : 7

 Number of rounds R : 4



 queue : (from front side) 2 4 3 5

 First round : 2 4 (we can’t take 3rd group as 3 members can’t be accumulated after 2 and 4.)

 queue : 3 5 2 4 (1st and 2nd group are enqueued. i.e. 2 and 4)

 Second round : 3

 queue : 5 2 4 3

 Third Round : 5 2

 queue : 4 3 5 2

 Fourth Round : 4 3

 After 4 rounds, total earning is 6+3+7+7 = 23.

Code : 

 import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/**
 * Created by Aniket on 2/8/14.
 */
public class ZooDriverEarningsFinder {

    int numberOfGroups;
    int[] groupSizes;
    int busCapacity;
    int noOfRounds;

    public ZooDriverEarningsFinder(int numberOfGroups, int[] groupSizes,int busCapacity,int noOfRounds){
        this.numberOfGroups = numberOfGroups;
        this.groupSizes = groupSizes;
        this.busCapacity = busCapacity;
        this.noOfRounds = noOfRounds;
    }

    public int calculateEarnings(){

        Queue<Integer> groupsQueue = new LinkedList<Integer>();
        for(int grpSize : groupSizes){
            groupsQueue.offer(grpSize);
        }

        int roundsCount = 0;
        int earnings = 0;

        while(roundsCount < noOfRounds){

            int currentCapacity = 0;

            while(currentCapacity <= busCapacity){
                int nextGrpSize = groupsQueue.peek();
                if((currentCapacity + nextGrpSize) <= busCapacity){
                    currentCapacity = currentCapacity + nextGrpSize;
                    groupsQueue.offer(groupsQueue.poll());
                }
                else {
                    //bus is full. Commence journey
                    break;
                }
            }
            //capacity is full. Add earning.
            earnings = earnings + currentCapacity;
            //increment rounds
            roundsCount++;
        }
        return earnings;
    }

    public static void main(String args[]){

        Scanner scanner = new Scanner(System.in);

        //get number of groups
        int numberOfGroups = scanner.nextInt();

       int[] groupSizes = new int[numberOfGroups];

        //get group sizes
        for(int i=0; i<numberOfGroups; i++){
            groupSizes[i] = scanner.nextInt();
        }

        int busCapacity = scanner.nextInt();

        int noOfRounds = scanner.nextInt();

        ZooDriverEarningsFinder earningsFinder = new ZooDriverEarningsFinder(numberOfGroups,groupSizes,busCapacity,noOfRounds);
        System.out.println("Total Earnings : " + earningsFinder.calculateEarnings());
    }
}

Output : 

4
2
4
3
5
7
4
Total Earnings : 23

Search an element in a sorted and pivoted array

Question : 

Link of Question : (GeeksForGeeks)
An element in a sorted array can be found in O(log n) time via binary search. But suppose I rotate the sorted array at some pivot unknown to you beforehand. So for instance, 1 2 3 4 5 might become 3 4 5 1 2. Devise a way to find an element in the rotated array in O(log n) time.

Algorithm :

Find the pivot point, divide the array in two sub-arrays and call binary search.
The main idea for finding pivot is – for a sorted (in increasing order) and pivoted array, pivot element is the only only element for which next element to it is smaller than it.
Using above criteria and binary search methodology we can get pivot element in O(logn) time

• Input arr[] = {3, 4, 5, 1, 2}

• Element to Search = 1

1.  Find out pivot point and divide the array in two 

   sub-arrays. (pivot = 2) /*Index of 5*

2. Now call binary search for one of the two sub-arrays.

   • If element is greater than 0th element then search in left array

   • Else Search in right array (1 will go in else as 1 < 0th element(3))

3. If element is found in selected sub-array then return index 
        Else return -1.

Code : 

package Arrays;

/**
 * Created with IntelliJ IDEA.
 * User: aniket
 * Date: 5/2/14
 * Time: 12:08 PM
 */
public class RotatedBinarySearcher {

    public int pivotedBinarySearch(int[] array, int no){

        int endIndex = array.length - 1;

        int pivot = findPivot(array,0,endIndex);

        System.out.println("Pivot Index : " + pivot);


        if(pivot == -1){    //Array is just sorted and not rotated
            return binarySearch(array,0,endIndex,no);
        }

        if(array[pivot] == no){
            return pivot;
        }
        else if(array[0] <= no){    //If number is greater than array[0] then it is must be left side of pivot
            return binarySearch(array,0,pivot-1,no);
        }
        else {
            return binarySearch(array,pivot+1,endIndex,no);
        }
    }


    private int findPivot(int [] array, int start, int end){

        if(start > end){
            return -1;
        }

        if(start == end){
            return start;
        }

        int mid = (start + end) / 2;

        if(mid > start && array[mid] < array[mid-1]){
            return mid - 1;
        }
        if(mid < end && array[mid] > array[mid + 1]){
            return mid;
        }

        if(array[mid] <= array[start]){
            return findPivot(array, start, mid-1);
        }
        else {  //array[mid] > array[end]
            return findPivot(array, mid + 1, end);
        }
    }

    private int binarySearch(int[] array, int start, int end, int number){

        if(start > end){
            return -1;
        }

        int mid = (end + start)/2;

        if(array[mid] == number){
            return mid;
        }

        if(number < array[mid]){
            return binarySearch(array, start, mid - 1, number);
        }
        else{
            //number > array[mid]
            return binarySearch(array, mid + 1, end, number);
        }
    }

    public static void main(String args[]){

        int[] array = new int[]{3,4,5,1,2};
        int searchIndex = new RotatedBinarySearcher().pivotedBinarySearch(array,1);
        System.out.println("Number is at index : " + searchIndex);

    }

}

Output : 

Pivot Index : 2
Number is at index : 3