Heap Sort

Heap is an implementation of Priority Queue data structure

There are two kinds of Heaps: Max Heap and Min Heap.
In Max Heap, every element is greater than its left and right children
In Min Heap, every element is less than its left and right children.

An array should be visualized as a Tree structure, when working with heaps.

Heap properties:
1. Each element is greater(max heap) or less (min heap) than its left and right children
2. The tree should be a complete binary tree

Complete Binary tree:
Each node should have at most two children, except leaf nodes.
If a node has right child, then it must have left child.
If a node has no left/right child, then all the next nodes in that level and in next level should not have any children.

Typical operations performed on an Heap:
1. Get parent element index
2. Get Left Child index
3. Get right child index
4. insert an element
5. delete the highest priority element
6. percolate down: Its an operation to satisfy the heap property from the given index down to all its child nodes.
7. Heapify: Given an array, which is not satisfying heap properties, make it as a heap.

Code:
import java.util.Arrays;

class Heap {
        private int array[] = new int[10];
        private int capacity = 0;
        private int count = 0;

        Heap() {}

        //Parent of element is located exactly at (i-1)/2 position
        public int getParent(int index) {
                if(index == 0)
                        return -1;
                else
                        return (index-1)/2;
        }

        //left child is located at 2*i+1 position
        public int getLeftChild(int index) {
                int left = 2 * index + 1;

                if(left > count-1)
                        return -1;
                else
                        return left;
        }

        //right child is located at 2*i+2 position
        public int getRightChild(int index) {
                int right = 2 * index + 2;

                if(right > count-1)
                        return -1;
                else
                        return right;
        }

        //gives the size of the heap
        public int getSize() {
                return this.count;
        }

        //Given an array, which is not satisfying the heap properties, 

        //this method makes the array as an heap structure

        //One important observation is that, all leaf nodes, by default satisfy the heap property

        //since they do not have any children, so not required to compare them with any one

        //so starting from (len-1)/2 index till root element, percolate down

        public void buildHeap(int[] in) {

                this.array = in;

                int len = in.length;

                this.count = len;

                for(int i=(len-1)/2; i>=0; i--)

                        percolateDown(i);

        }

        //this inserts the element one by one from the given array into heap

        //then deletes the max element from heap and keeps it back in the input array

        public void heapSort(int[] in) {

                for(int i=0; i<in.length; i++)

                        insert(in[i]);

                for(int i=0; i<in.length; i++)

                        in[i] = deleteMax();

                System.out.println(Arrays.toString(in));

        }

        //insert the element at end

        //then compare it with its parent and if the parent is less than the inserted element

        //swap the current element with its parent

        //now repeat this procedure from parent, till we reach the root element

        public void insert(int data) {

                array[count++] = data;

                if(count == 1)

                        return;

                int parent = (count-2)/2;

                int currPos = count-1;

                while(array[parent] < array[currPos]) {

                        int temp = array[parent];

                        array[parent] = array[currPos];

                        array[currPos] = temp;

                        currPos = parent;

                        parent = getParent(parent);

                }

        }

        //We need to make the array satisfy the heap property at each level

        //Given an index, check the max element index by comparing this with its left and right children

        //now swap the current index element with the max(either left/right) element

        //then repeat this procedure from the max(left/right) position till we reach leaf nodes

        public void percolateDown(int i) {

                int left = -1, right = -1;

                left = getLeftChild(i);

                right = getRightChild(i);

                int max = i;

                //compare the left and right children with current element

                //determine the max element position

                //and exchange it with current element position

                if(left != -1 && array[left] > array[max])

                        max = left;

                if(right != -1 && array[right] > array[max])

                        max = right;

                if(max != i) {

                        //exchange max and i index elements

                        int temp = array[i];

                        array[i] = array[max];

                        array[max] = temp;

                        //since at this position heap property violated

                        //Follow top-down from this element as well

                        percolateDown(max);

                }

        }

        //Deletes the highest priority element(which is at index 0)

        //To delete the max element, swap root with last element

        //now decrease the count by 1

        //percolate down from the root, to make the array satisfy the heap properties

        public int deleteMax() {

                if(count == 0)

                        return -1;

                int deletedEle = array[0];

                System.out.println("Deleting: " + deletedEle);

                if(count == 1) {

                        --count;

                        return deletedEle;

                }

                array[0] = array[--count];

                percolateDown(0);

                return deletedEle;

        }

        static public void main(String[] args) {

                int[] ar = {16, 4, 10, 14, 7, 9, 3, 2, 8, 1};

                System.out.println(Arrays.toString(ar));

                new Heap().heapSort(ar);

        }

}

eg:

Complexity Analysis:

External Sorting: K-way Merging

Problem:
Lets say we have 20GB size file, which contains a string in each line.
Now we need to sort this file, but the system RAM size is only 1GB.

Solution:
So we can't load the entire file into main memory(RAM) at once and apply sorting algorithm.

We load chunks of data from the input file, sort the chunks and then apply K way merging process.

Since RAM size is 1GB, divide the 20GB file into 25 chunks, where each chunk is of size ~800MB(800MB * 25 ~= 20GB).

Now take each chunk into memory one after another, sort them individually, and push them back to the same locations.
So now the input file contains 25 sorted chunks.

Now take 36MB(900MB/25) from each file. Call this as input chunks.
Leave the rest of the RAM 100MB to store output sorted chunk.

Now compare first lines of each chunk, take out the smallest one and push it on to the output array.
Repeat this process:
   If any chunk becomes empty, then take the next data of that input chunk(next 36MB of the sorted 800MB array)
   If the output array becomes full, empty it and push it on to the output array of hard disk.

Continue this process till all the chunks data is sorted.

References:
http://exceptional-code.blogspot.in/2011/07/external-sorting-for-sorting-large.html

Dutch National Flag Algorithm

This Algorithm is used to separate 3 different types of elements together.

For example, lets say an array contains positive, negative, zero(one or more zeros) elements, then using this algorithm, we can bring all zeros together, all positive numbers to the right of zero elements, all negative numbers to the left of zeros.

Note that the positive, negative numbers will not be in sorted order here. We care only about placing negative numbers first, then zeros and then positive numbers.

Code:

import java.util.Arrays;

class DNFAlgo {
        static public void dnfAlgo(int[] in, int pivot) {
                int equal = 0, small = 0, large = in.length - 1;

                while(equal<=large) {
                        if(in[equal] < pivot) {
                                //swap with the small index and increment both small and equal indexes
                                int temp = in[equal];
                                in[equal] = in[small];
                                in[small] = temp;

                                equal++;
                                small++;
                        } else if(in[equal] == pivot) {
                                //just increment equal index
                                equal++;
                        } else {
                                //swap with large index and decrement the large index
                                int temp = in[equal];
                                in[equal] = in[large];
                                in[large] = temp;

                                large--;
                        }
                }
        }

        static public void main(String[] args) {
                int[] in = {2, 0 , -1, -2, 0, 3, -1, 2};

                System.out.println(Arrays.toString(in));

                dnfAlgo(in, 0);

                System.out.println(Arrays.toString(in));
        }
}

eg:

[2, 0, -1, -2, 0, 3, -1, 2]
[-1, -1, -2, 0, 0, 3, 2, 2]

pivot = 0

    equal small large array
    0 0 7 [2, 0, -1, -2, 0, 3, -1, 2]
a[0]=2>0  ==> a[0]<->a[7] 0 0 6 [2, 0, -1, -2, 0, 3, -1, 2]
a[0]=2>0  ==> a[0]<->a[6] 0 0 5 [-1, 0, -1, -2, 0, 3, 2, 2]
a[0]=-1<0 ==> a[0]<->a[0] 1 1 5 [-1, 0, -1, -2, 0, 3, 2, 2]
a[1]=0==0 ==> inc equal  2 1 5 [-1, 0, -1, -2, 0, 3, 2, 2]
a[2]=-1<0 ==> a[2]<->a[1] 3 2 5 [-1, -1, 0, -2, 0, 3, 2, 2]
a[3]=-2<0 ==> a[3]<->a[2] 4 3 5 [-1, -1, -2, 0, 0, 3, 2, 2]
a[4]=0==0 ==> inc equal  5 3 5 [-1, -1, -2, 0, 0, 3, 2, 2]
a[5]=0==0 ==> inc equal  6 3 5 [-1, -1, -,2 0, 0, 3, 2, 2]

condition false

Radix Sort

Steps:
This algorithm depends on the number of digits present in a given number.
First it sorts the number based on the last digit of each number.
Then it sorts the above result based on the second last digit of each number.
This will be continued till the first digit of the number.

At the end array will be sorted.

Code:
import java.util.Arrays;

class RadixSort {
        static public void radixSort(int[] in, int numOfDigs) {
                int[][] buckets = new int[10][in.length];

                int numToDiv = 10;

                for(int i=numOfDigs; i>0; i--) {
                        for(int j=0; j<in.length; j++) {
                                int lastDigit = in[j] % numToDiv;

                                if(numToDiv > 10)
                                        lastDigit = lastDigit/(numToDiv/10);

                                int pos = 0;
                                while(buckets[lastDigit][pos] != 0)
                                        ++pos;

                                buckets[lastDigit][pos] = in[j];
                        }

                        int insIndex = 0;

                        for(int j=0; j<buckets.length; j++) {
                                //take out all elements from buckets
                                //keep then in the input array
                                //empty the bucket arrays
                                int[] bucketAr = buckets[j];

                                for(int k=0; k<in.length; k++) {
                                        if(bucketAr[k] != 0)
                                                in[insIndex++] = bucketAr[k];
                                        else
                                                break;
                                }

                                buckets[j] = new int[in.length];
                        }

                        numToDiv = numToDiv*10;
                }
        }

        static public void main(String[] args) {
                int[] in = {321, 213, 320, 111, 435, 398};

                System.out.println(Arrays.toString(in));

                radixSort(in, 3);

                System.out.println(Arrays.toString(in));
        }
}

eg:
{321, 213, 320, 111, 435, 398}
Here we are maintaining the sorted elements in the digit buckets each time, then we are moving them back to original array.
Since there can be 10 possible digits in a decimal system, we maintain 10 buckets to store each digits numbers.

1st iteration:
since last digit of 321 is "1", keep 321 in the 2nd bucket(1st index)
since last digit of 213 is "3", keep 213 in the 4th bucket(3rd index)
...
Now the buckets are:
0 --> {320}, 1--> {321, 111}, 2 --> {}, 3 --> {213}, 4 --> {}, 5 --> {435}, 6 --> {}, 7 --> {}, 8 --> 398}

Now starting from 0th bucket, retrieve all the elements in the order of insertion in each bucket and keep them back in the original array.
So the original array will now become: {320, 321, 111, 213, 435, 398}
Here you can observe that the array is now sorted by last digit.

Now based on this array, sort it again wrt second digit, which gives:
{111, 213, 320, 321, 435, 398}

Last, sort it based on first digit:
==> {111, 213, 320, 321, 398, 435}


Complexity Analysis:

Bucket Sort

Steps:
In bucket sorting technique, we maintain an array(bucket) in which we store the count of that particular indexed element.

Then in the input array, we place the elements from accordingly depending on the number of elements in each bucket.

Code:
import java.util.Arrays;

class BucketSort {
        static public void bucketSort(int[] in, int low, int high) {
                int noOfBucks = high - low + 1;

                int[] buckets = new int[noOfBucks];

                for(int i=0; i<in.length; i++) {
                        int ele = in[i];

                        buckets[ele] = buckets[ele] + 1;
                }

                int insIndex = 0;

                for(int i=0; i<buckets.length; i++) {
                        int eleCount = buckets[i];

                        while(eleCount != 0) {
                                in[insIndex++] = i;
                                --eleCount;
                        }
                }
        }

        static public void main(String[] args) {
                int[] inAr = new int[]{2, 1, 0, 4, 3, 1, 4, 3, 5};

                System.out.println(Arrays.toString(inAr));

                bucketSort(inAr, 0, 5);

                System.out.println(Arrays.toString(inAr));
        }
}

eg:
Input array: {2, 1, 0, 4, 3, 1, 4, 3, 5}

bucket array: size: 5-0+1 = 6 ==> {1, 2, 1, 2, 2, 5}

Since 0 occurred once in the input array, we keep the count as '1' in the bucket array.
Since 1 occurred twice in the input array, we keep the count as '2' in the bucket array.

Now iterating over the bucket array, we need to keep the numbers equal to its count in the given input array.

Starting from 0th index, keep one 0, since count is 1. Keep the element at index 0.
Now at 1st index, count is 2. So keep two 1's in the input array at indices 1, 2


Complexity Analysis:

Counting Sort

Steps:


Code:
import java.util.Arrays;

class CountingSort {
        static public void countingSort(int[] in, int low, int high) {
                int[] count = new int[high-low+1];
                int[] out = new int[in.length];

                for(int i=0; i<in.length; i++) {
                        int inEle = in[i];

                        count[inEle-low] = count[inEle-low] + 1;
                }

                int sum = 0;
                for(int i=0; i<count.length; i++) {
                        sum = sum + count[i];
                        count[i] = sum;
                }

                for(int i= in.length-1; i>=0; i--) {
                        int inEle = in[i];

                        --count[inEle-low];

                        out[count[inEle-low]] = inEle;
                }

                System.out.println(Arrays.toString(out));
        }

        static public void main(String[] args) {
                int[] in = {4, 7, 2, 3, 3, 7, 5, 4};

                countingSort(in, 2, 7);
        }
}

eg:
Here we have 3 arrays:
   in: contains given input array elements
   count: This maintains the count of each element for the input array
   out: This is the destination array, in which the elements will be in sorted array

So the given input array is: {4, 7, 2, 3, 3, 7, 5, 4}
since the low is 2 and high is 7, we will have elements between 2-7(2/3/4/5/6/7) only the given input array. Since there are 5 possible numbers, we need to maintain a count array of length of 5(high-low+1)

Since elements are not starting from 0, but from 2: we store the count of 2 at 0th index, count of 3 at 1st index, ..., count of n at "n-low" index.

Now iterate over the input array from first element to last element.
Element: 4: increase the count of element 4 in count array: 4-low=4-2=2 ==> count[2] = count[2] + 1
Element 7: increase the count of element 5 in count array: 7-low=7-2=5 ==> count[5] = count[5] + 1
...
If we follow like this, we get the following count array:
{1, 2, 2, 1, 0, 1}

Sum elements of count array:
Now place the sum of previous elements and current element at current element at index.
==> {1, 3, 5, 6, 6, 7}

This count array indicates that: how many number of elements less than or equals to the current element are there in the given input array.
If we observer the above count array, at 3rd index, we have the count as 6. So there are 6 elements are present in the given input array that are <= 5(countIndex + low)

Constructing the output array:
We need to iterate over the input array from last element to first element.
Element 4: count[4-low] = count[4-2] = count[2] = 5. So there are 5 elements that are <= 5. Place the element 4 in the output array at 4th index(5-1)
==> out = {0, 0, 0, 4, 0, 0, 0}
Decrease the count[4] by 1 ==> count = {1, 3, 5, 6, 5, 7}

Element 5: count[5-low] = count[5-2] = count[3] = 6. So there are 6 elements that are <= 5. Place the element 5 in the output array at 5th index (6-1)
==> out = {0, 0, 0, 4, 5, 0, 0}
Decrease the count[5] by 1 ==> count = {1, 3, 5, 5, 5, 7}
...
Element 7==> out = {0, 0, 0, 4, 5, 0, 7} ==> count = {1, 3, 5, 5, 5, 6}, out = {0, 0, 0, 4, 5, 0, 7}
...
out = {2, 3, 3, 4, 4, 5, 7, 7}



Complexity Analysis:

References:
https://www.youtube.com/watch?v=5rLrRpcBCzo

Quick Sort

Steps:

1. We select a pivot element and arrange the rest of the array such that all the elements to the left of pivot element should be less than it and to the right of pivot element should be great than it.
2. Now wrt the pivot element, divide the array into two sub arrays: One containing the elements to the left of it and another containing the elements to right of it.
3. Follow the 1st again for these two sub arrays.

Arranging the elements wrt pivot:

1. Select the last element as pivot and pivotIndex as start index.
2. Now starting from the first index of the array, compare each element with pivot. If the element < pivot, then swap the element with the element at pivotIndex element and increase the pivotIndex by 1
3. 2nd step has to be repeated till the last before element

Randomized Quick Sort:
In the above procedure we are always selecting the last element as the pivot. Instead of it, we can select the pivot element randomly in the array. Then swap that element with last element of the array.
Remaining steps are same as above.

Code:

import java.util.Arrays;
import java.util.Random;

class QuickSort {
        static public void quickSort(int[] in, int start, int end) {
                if(start < end) {
                        //int partitionIndex = partition(in, start, end);
                        int partitionIndex = randomizedPartition(in, start, end);

                        quickSort(in, start, partitionIndex-1);
                        quickSort(in, partitionIndex+1, end);
                }
        }

        static int partition(int[] in, int start, int end) {
                int pivot = in[end];
                int pIndex = start;

                for(int i=start; i<end-1; i++) {
                        if(in[i] < pivot) {
                                //exchange pIndex and i index elements
                                int temp = in[i];
                                in[i] = in[pIndex];
                                in[pIndex] = temp;

                                ++pIndex;
                        }
                }

                in[end] = in[pIndex];
                in[pIndex] = pivot;

                return pIndex;
        }

        static int randomizedPartition(int[] in, int start, int end) {

                Random random = new Random();

                int pivotIndex = start + random.nextInt(end-start);

                //swap end and pivotIndex elements

                int tmp = in[pivotIndex];

                in[pivotIndex] = in[end];

                in[end] = tmp;

                int pivot = in[end];

                int pIndex = start;

                for(int i=start; i<end-1; i++) {

                        if(in[i] < pivot) {

                                //exchange pIndex and i index elements

                                int temp = in[i];

                                in[i] = in[pIndex];

                                in[pIndex] = temp;

                                ++pIndex;

                        }

                }

                in[end] = in[pIndex];

                in[pIndex] = pivot;

                return pIndex;

        }

        static public void main(String[] args) {

                int[] in = {6, 8, 1, 4, 5, 3, 7, 2};

                System.out.println(Arrays.toString(in));

                quickSort(in, 0, in.length-1);

                System.out.println(Arrays.toString(in));

        }

}

eg:
{8, 5, 1, 4, 2, 7, 6, 3}

1st Iteration:
pivot = 3
Compare 8 with 3. Since 8 > 3, dont do anything
Compare 5 with 3. Since 5 > 3, dont do anything
Compare 1 with 3. Since 1 < 3, exchange pivotIndex(0) element with current element.
==> {1, 5, 8, 4, 2, 7, 6, 3}
Increase pivotIndex by 1 ==> pivotIndex = 1

Compare 4 with 3. Since 4 > 3, dont do anything
Compare 2 with 3. Since 2 < 3, exchange pivotIndex(1) element with current element.
==> {1, 2, 8, 4, 5, 7, 6, 3}
Increase pivotIndex by 1 ==> pivotIndex = 2

Compare 7 with 3. Since 7 > 3, dont do anything.
Compare 6 with 3. Since 6 > 3, dont do anything.

Since pivotIndex is 2, exchange the last element with element at index 2
==> {1, 2, 3, 4, 5, 7, 6, 8}

Here you can see that the pivot element is now at correct position, as like in sorted array.

Now divide the array wrt pivot element: ==> {1, 2} and {4, 5, 7, 6, 8}.
Follow the above procedure for these two arrays well.

Complexity:

Merge Sort:

Steps:

Code:
http://www.code2learn.com/2011/07/merge-sort-using-java.html



eg:
{2, 4, 1, 6, 8, 5, 3, 7}

Divide the array into half recursively, till at the end you have only one element in the array
so divisions at each step are:
1. {2, 4, 1, 6} {8, 5, 3, 7}
{2, 4} {1, 6} {8, 5} {3, 7}
{2} {4} {1} {6}  {8} {5} {3} {7}


2. Now merge two arrays: {2}, {4} into a single array in sorted order ==> {2,4}
   similarly merge two arrays: {1}, {6} into a single array in sorted order {1,6}
 
   Now merge these two arrays in sorted order. ==> {1, 2, 4, 6}
 
   Similarly you get another array: {3, 5, 7, 8}
 
   At the last step array is sorted as: {1, 2, 3, 4, 5, 6, 7, 8}
 
3. How two unsorted arrays are merged in sorted fashion.
Consider the first element of first array and first element of second array
compare these two and place the lesser number in the target sorted array
Lets say first < second.
Now increase the index of first position by 1 and compare this with right, ie. first+1 < second?

Here we are placing all smaller elements one by one in sorted array.
For eg:
left: {1, 2, 4, 6}
right: {3, 5, 7, 8}
Sorted Array:
{0, 0, 0, 0, 0, 0, 0, 0} left: {1, 2, 4, 6}, right: {3, 5, 7, 8}
{1, 0, 0, 0, 0, 0, 0, 0} left: {2, 4, 6}, right: {3, 5, 7, 8}
{1, 2, 0, 0, 0, 0, 0, 0} left: {4, 6}, right: {3, 5, 7, 8}
{1, 2, 3, 0, 0, 0, 0, 0} left: {4, 6}, right: {5, 7, 8}
{1, 2, 3, 4, 0, 0, 0, 0} left: {6}, right: {5, 7, 8}
{1, 2, 3, 4, 5, 0, 0, 0} left: {6}, right: {7, 8}
{1, 2, 3, 4, 5, 6, 0, 0} left: {}, right: {7, 8}
{1, 2, 3, 4, 5, 6, 7, 0} left: {}, right: {8}
{1, 2, 3, 4, 5, 6, 7, 8} left: {}, right: {}

Complexity:

Shell Sort

Steps:
This is improved version of insertion sort.
In insertion sort, we start from 1st index and compare each and every element with its previous adjacent element.

In Shell Sort also, we do the same.

But it is a repetitive Insertion Sort.

We select the gap and keep on performing insertion sort.
First we select gap as: len/2 = 4
then perform insertion sort at this gap*i indices(for example: if gap=4, we compare (4, 0), (5, 1), (6, 2), (7, 3)

Now divide the gap again by 2 ==> gap = gap/2 = len/4 = 2
Now comparisons are:
(2, 0), (3, 1), (4, 2), (5, 3), (6, 4), (7, 5)

Now divide the gap again by 2 ==> gap = gap/2 = len/8 = 1
Now comparisons are: (1, 0), (2, 1), (3, 2), (4, 3), (5, 4), (6, 5), (7, 6)

Here we can observe that the last step is same as the Insertion Sort, but by this step the array is almost sorted, so there will be less number of swap operations.

Code:
import java.util.Arrays;

class ShellSort {
        static public void shellSort(int[] in) {
                int len = in.length;

                for(int gap = len/2; gap > 0; gap = gap/2) {
                        System.out.println("Gap=" + gap);

                        for(int i=gap; i<len; i++) {
                                int key = in[i];

                                int j = i;

                                while(j>=gap && in[j-gap] > key) {
                                        in[j] = in[j-gap];
                                        j = j-gap;
                                }

                                in[j] = key;
                        }
                }
        }

        static public void main(String[] args) {
                int[] in = {6, 8, 1, 4, 5, 3, 7, 2};

                System.out.println(Arrays.toString(in));

                shellSort(in);

                System.out.println(Arrays.toString(in));
        }
}

eg:

6 8 1 4 5 3 7 2

Gap=4
index=4, key=5
index=5, key=3
index=6, key=7
index=7, key=2

Sorted:[5, 3, 1, 2, 6, 8, 7, 4]

Gap=2
index=2, key=1
index=3, key=2
index=4, key=6
index=5, key=8
index=6, key=7
index=7, key=4

Sorted:[1, 2, 5, 3, 6, 4, 7, 8]

Gap=1
index=1, key=2
index=2, key=5
index=3, key=3
index=4, key=6
index=5, key=4
index=6, key=7
index=7, key=8

Sorted:[1, 2, 3, 4, 5, 6, 7, 8]

Complexity Analysis:

Selection Sort

Steps:

Code:

import java.util.Arrays;

class SelectionSort {
        static public void selectionSort(int[] in) {
                int len = in.length;

                for(int i=0; i<len; i++) {
                        int minPos = i;

                        for(int j=i; j<len; j++) {
                                if(in[minPos] > in[j])
                                        minPos = j;
                        }

                        //swap minPos element and ith element
                        int temp = in[minPos];
                        in[minPos] = in[i];
                        in[i] = temp;
                }
        }

        static public void main(String[] args) {
                int[] in = {6, 5, 3, 1, 8, 7, 2, 4};

                System.out.println(Arrays.toString(in));

                selectionSort(in);

                System.out.println(Arrays.toString(in));
        }
}

eg:

Complexity Analysis:

Bubble Sort

Steps:

Code:

import java.util.Arrays;

class BubbleSort {

        static public void bubbleSort(int[] in) {

                int len = in.length;

                for(int i=len; i>1; i--) {

                        for(int j=0; j<i-1; j++) {

                                if(in[j] > in[j+1]) {

                                        //swap

                                        int temp = in[j];

                                        in[j] = in[j+1];

                                        in[j+1] = temp;

                                }

                        }

                }

        }

        static public void optimizedBubbleSort(int[] in) {

                int len = in.length;

                for(int i=len; i>1; i--) {

                        boolean swapped = false;

                        for(int j=0; j<i-1; j++) {

                                if(in[j] > in[j+1]) {

                                        swapped = true;

                                        int temp = in[j];

                                        in[j] = in[j+1];

                                        in[j+1] = temp;

                                }

                        }

                        if(!swapped)

                                return;

                }

        }

        static public void main(String[] args) {

                int in[] = {6, 5, 3, 1, 8, 7, 2, 4};

                System.out.println(Arrays.toString(in));

                optimizedBubbleSort(in);

                System.out.println(Arrays.toString(in));

        }

}

eg:

Complexity Analysis:

Insertion Sort

In Insertion sort, first select a key and insert it at its correct position.

Steps:
1. Select one key in each iteration starting from 2nd element(1st index)
2. Now compare the key with all its previous elements, starting from [keyPos-1] index.
Store the key in a temp variable.
At any index, if the key is less than the element at that index, move that element to its next position.
Continue this till 0th index.
3. By this time/earlier, key's index will be decided.
So place the key at that index.
4. Repeat the steps 2 and 3 for next indices.

Code:

import java.util.Arrays;

class InsertionSort {
        static public void insertionSort(int[] a) {
                int len = a.length;

                for(int i=0; i<len; i++) {
                        int key = a[i];

                        int j = i;

                        while(j>0 && a[j-1] > key) {
                                a[j] = a[j-1];
                                j--;
                        }

                        a[j] = key;
                }
        }

        static public void main(String[] args) {
                int[] in = {6, 8, 1, 4, 5, 3, 7, 2};

                System.out.println(Arrays.toString(in));

                insertionSort(in);

                System.out.println(Arrays.toString(in));
        }
}

eg:

Input: 6 8 1 4 5 3 7 2

1st iteration:

key = 8

compare 6 & 8: 6 < 8. Dont move.

2nd iteration:

key = 1

compare 8 & 1: 8 > 1. So move 8 to its next position.

==> 6 8 8 4 5 3 7 2

Now compare 6 & 1: 6 > 1. So move 6 to its next position.

==> 6 6 8 4 5 3 7 2

Now we are at index 0. So replace 0th index element with key

==> 1 6 8 4 5 3 7 2

....

....

Complexity Analysis: TODO