Sorting a sub array makes the whole array sorted

Given an unsorted array.
Find the positions of two elements in it, sorting which the whole array will be in sorted order.

Algorithm:
1. Starting from first index, find the position of element which is less than its previous element.
Call it as "start".
If there is no such element, then the array is already in sorted form.
2. Starting from last index, find the position of element which is less than its next element.
Call it as "end".
3. Now find min and max elements in the sub array of [start, end] inclusive.
Call them as min and max.
4. Find the position of first element in [0, start-1], which is greater than "min" ==> index1
5. Find the position of first element in [len-1, end-1], which is less than "max" ==> index2

Now if we sort the sub array formed by [index1, index2], then the whole array will be sorted.

Code:

class MinSortArray {
static public void printPositions(int[] ar) {
int st = -1, end = -1;

for(int i=0; i<ar.length-1; i++) {
if(ar[i+1] < ar[i]) {
st = i+1;
break;
}
}

if(st == -1) {
System.out.println("Array is in sorted form...");
return;
}

for(int i=ar.length-1; i>1; i--) {
if(ar[i-1] > ar[i]) {
end = i-1;
break;
}
}

int min = ar[st], max = ar[end];

for(int i=st; i<=end; i++) {
if(ar[i] < min)
min = ar[i];

if(ar[i] > max)
max = ar[i];
}

int p1 = 0, p2 = 0;

for(int i=0; i<st; i++) {
if(ar[i] > min) {
p1 = i;
break;
}
}

for(int i=ar.length-1; i>end; i--) {
if(ar[i] < max) {
p2 = i;
break;
}
}

System.out.println("min=" + p1 + ", max=" + p2);
}

static public void main(String[] args) {
int[] ar = {10, 12, 20, 30, 25, 40, 32, 31, 35, 50, 60};

printPositions(ar);
}
}

Example:
Lets the input array be: {10, 12, 20, 30, 25, 40, 32, 31, 35, 50, 60}

Step 1:
30 < 25 ==> start=4

Step 2:
32 > 31 ==> end = 6

Step 3:
sub array: {25, 40, 32}
min = 25, max = 40

Step 4:
in [0, 3] sub array, 30 > 25 ==> index1 = 3

Step 5:
in [7, 10] sub array, 35 < 40 ==> index2 = 8

So sorting the sub array [3, 8], makes the whole array sorted.

Move All spaces to the begining of the array (or) move all zeros to the begining of the array

class MoveSpacesToBeg {
        static public String moveSpacesToBeg(String str) {
                char[] a = str.toCharArray();

                int n = a.length-1;
                int count = n;

                for(int i=n; i>=0; i--)
                        if(a[i] != ' ')
                                a[count--] = a[i];

                while(count>=0)
                        a[count--] = ' ';

                return new String(a);
        }

        static public void main(String[] args) {
                String str = "Suresh Reddy M";
                System.out.println(str);

                str = moveSpacesToBeg(str);
                System.out.println(str);
        }
}

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: