Open Source For Geeks: 02/21/14

Friday, 21 February 2014

Sort a stack using recursion in Java

Question :

Sorting a Stack using push,pop,isEmpty and peek.

Code :

 package SortingTechniques;

import java.util.Arrays;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * User: aniket
 * Date: 19/2/14
 * Time: 11:02 AM
 */
public class StackSort {

    public void sortStack(Stack<Integer> stack){

        int no = stack.pop();
        if(stack.size() != 1){
            sortStack(stack);
        }
        insert(stack,no);
    }

    private void insert(Stack<Integer> stack, int no){

        if(stack.size() == 0){
            stack.push(no);
        }
        else{
            int newPeakedNo = stack.peek();
            if(no >= newPeakedNo){
                stack.push(no);
            }
            else{
                int newPoppedNo = stack.pop();
                insert(stack, no);
                stack.push(newPoppedNo);
            }
        }
    }

    public static void main(String args[]){

        Stack<Integer> stack = new Stack<>();
        stack.push(5);
        stack.push(4);
        stack.push(3);
        stack.push(2);
        stack.push(1);
        System.out.println("Stack Before Sort : " + Arrays.toString(stack.toArray()));
        new StackSort().sortStack(stack);
        System.out.println("Stack After Sort : " + Arrays.toString(stack.toArray()));

    }

}

Output :

Stack Before Sort : [5, 4, 3, 2, 1]
Stack After Sort : [1, 2, 3, 4, 5]

Note :

A similar question was solver in previous post about how to reverse a Stack in Java. It has similar logic.

Program to reverse a stack "in place" using recursion?

Counting Sort in java

Background

Counting sort is a sorting technique based on keys between a specific range. It works by counting the number of objects having distinct key values (kind of hashing). Then doing some arithmetic to calculate the position of each object in the output sequence.

Code :

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * User: aniket
 * Date: 19/2/14
 * Time: 8:03 PM
 */
public class CountingSort {


    public int[] sort(int[] array) {

        int maxValue = getMaxValue(array);
        return countingSort(array,maxValue);

    }

    public int[] countingSort(int[] input, int maxValue){

        int[] countArray = new int[maxValue+1];
        for(int no : input){
            countArray[no] = countArray[no] + 1;
        }

        for(int i=1;i<countArray.length;i++){
            countArray[i] = countArray[i] + countArray[i-1];
        }

        int[] output = new int[input.length];

        for(int i=output.length-1;i>=0;i--){

            output[countArray[input[i]]-1] = input[i];
            countArray[input[i]] = countArray[input[i]] -1;

        }

        return output;

    }


    private int getMaxValue(int[] array){

        int maxValue = Integer.MIN_VALUE;
        for(int no : array){
            if(no > maxValue){
                maxValue = no;
            }
        }
        return maxValue;
    }


    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));
        System.out.println("Array after Sort : " + Arrays.toString(new CountingSort().sort(array)));

    }

}

Output :

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

NOTE : The modified count array indicates the position of each object in the output sequence.

Time Complexity

Time Complexity: O(n+k) where n is the number of elements in input array and k is the range of input.
Auxiliary Space: O(n+k)

Quick Sort in Java

Background

Quicksort is a divide and conquer algorithm. Quicksort first divides a large array into two smaller sub-arrays: the low elements and the high elements. Quicksort can then recursively sort the sub-arrays.

Steps :

Pick an element, called a pivot, from the array.
Partitioning: reorder the array so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
Recursively apply the above steps to the sub-array of elements with smaller values and separately to the sub-array of elements with greater values.

Code :

import java.io.IOException;
import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * User: aniket
 * Date: 19/2/14
 * Time: 8:32 PM
 */
public class QuickSort {

    public void quickSort(int[] array, int start, int end){
        int i = start;
        int j = end;

        int pivot = array[(start + end)/2];

        while (i <= j) {

            while (array[i] < pivot) {
                i++;
            }

            while (array[j] > pivot) {
                j--;
            }

            if (i <= j) {
                swap(array, i, j);
                i++;
                j--;
            }
        }

        if (start < j)
            quickSort(array, start, j);
        if (i < end)
            quickSort(array, i, end);
    }

    public static void swap(int[] array, int index1, int index2){

        if(index1 == index2)
            return;

        int temp = array[index1];
        array[index1] = array[index2];
        array[index2] = temp;

    }

    public static void main(String args[]) throws IOException {

        int[] array = new int[]{2,7,5,9,4,7,1,0};
        System.out.println("Array Before Sort : " + Arrays.toString(array));
        new QuickSort().quickSort(array,0,array.length-1);
        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]

Complexity

Quick sort like merge sort has an average complexity of O(Nlog N)

Worst-case analysis

The most unbalanced partition occurs when one of the sublists returned by the partitioning routine is of size n − 1. This may occur if the pivot happens to be the smallest or largest element in the list, or in some implementations when all the elements are equal.

If this happens repeatedly in every partition, then each recursive call processes a list of size one less than the previous list. Consequently, we can make n − 1 nested calls before we reach a list of size 1. This means that the call tree is a linear chain of n − 1 nested calls. The ith call does O(n − i) work to do the partition, and

\textstyle \sum _{i=0}^{n}(n-i)=O(n^{2})

, so in that case, Quicksort takes O(n²) time.

Best-case analysis

In the most balanced case, each time we perform a partition we divide the list into two nearly equal pieces. This means each recursive call processes a list of half the size. Consequently, we can make only log2 n nested calls before we reach a list of size 1. This means that the depth of the call tree is log2 n. But no two calls at the same level of the call tree process the same part of the original list; thus, each level of calls needs only O(n) time all together (each call has some constant overhead, but since there are only O(n) calls at each level, this is subsumed in the O(n) factor). The result is that the algorithm uses only O(n log n) time.

Average-case analysis

To sort an array of n distinct elements, quicksort takes O(n log n) time in expectation, averaged over all n! permutations of n elements with equal probability. We list here three common proofs to this claim providing different insights into quicksort's workings.

Other Info

As of Perl 5.8, merge sort is its default sorting algorithm (it was quicksort in previous versions of Perl). In Java, the Arrays.sort() methods use merge sort or a tuned quicksort depending on the datatypes and for implementation efficiency switch to insertion sort when fewer than seven array elements are being sorted. Python uses Timsort, another tuned hybrid of merge sort and insertion sort, that has become the standard sort algorithm in Java SE & on the Android platform, and in GNU Octave.

Merge Sort in java

Background

Mergesort is a divide and conquer algorithm that was invented by John von Neumann in 1945.

Conceptually it works as follows -

Divide the unsorted list into n sublists, each containing 1 element (a list of 1 element is considered sorted).
Repeatedly merge sublists to produce newly sorted sublists until there is only 1 sublist remaining. This will be the sorted list.

Code :

import java.util.Arrays;

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

    public void sort(int[] array) {
        mergeSort(array,0,array.length-1);

    }

    private void mergeSort(int[] array, int start, int end){

        if(start == end){
            return;
        }
        int mid = (start + end)/2;
        mergeSort(array, start, mid);
        mergeSort(array, mid+1, end);
        merge(array,start,mid,end);

    }

    private void merge(int[] array, int start, int mid, int end){

        int[] leftArray = Arrays.copyOfRange(array,start,mid+1);
        int[] rightArray = Arrays.copyOfRange(array,mid+1,end+1);

        int i = 0;
        int j = 0;

        int counter = start;

        while(i<leftArray.length && j<rightArray.length){
            if(leftArray[i] < rightArray[j]){
                array[counter] = leftArray[i];
                i++;
            }
            else {
                array[counter] = rightArray[j];
                j++;
            }
            counter++;
        }

        if(i == leftArray.length){
            while(j != rightArray.length){
                array[counter] = rightArray[j];
                j++;
                counter++;
            }
        }
        else{//j == rightArray.length
            while(i != leftArray.length){
                array[counter] = leftArray[i];
                i++;
                counter++;
            }

        }

    }

    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 MergeSort().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]

Complexity

In sorting n objects, merge sort has an average and worst-case performance of O(n log n).

You can visualize it with the following diagram -

Handling very large data

If the data set is very large (large that what can fit into RAM/main memory) then above approach will not work. In that case, you need to do what is popularly known as -

External sorting

External merge sort is one such external sorting algorithm

Sort chunks that each fit in RAM, then merges the sorted chunks together.
First divide the file into runs such that the size of a run is small enough to fit into main memory. Then sort each run in main memory using merge sort sorting algorithm.
Finally merge the resulting runs together into successively bigger runs, until the file is sorted.

Example -

For example, for sorting 900 megabytes of data using only 100 megabytes of RAM:

Read 100 MB of the data in main memory and sort by some conventional method, like quicksort.
Write the sorted data to disk.
Repeat steps 1 and 2 until all of the data is in sorted 100 MB chunks (there are 900MB / 100MB = 9 chunks), which now need to be merged into one single output file.
Read the first 10 MB (= 100MB / (9 chunks + 1)) of each sorted chunk into input buffers in main memory and allocate the remaining 10 MB for an output buffer. (In practice, it might provide better performance to make the output buffer larger and the input buffers slightly smaller.)
Perform a 9-way merge and store the result in the output buffer. Whenever the output buffer fills, write it to the final sorted file and empty it. Whenever any of the 9 input buffers empties, fill it with the next 10 MB of its associated 100 MB sorted chunk until no more data from the chunk is available. This is the key step that makes external merge sort work externally -- because the merge algorithm only makes one pass sequentially through each of the chunks, each chunk does not have to be loaded completely; rather, sequential parts of the chunk can be loaded as needed.

You can use the following approach to sort sorted runs -

Merge k sorted arrays

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.

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];
    }

Friday, 21 February 2014

Sort a stack using recursion in Java

Question :

Code :

Output :

Note :

Counting Sort in java

Background

Code :

Output :

Time Complexity

Related Links

Quick Sort in Java

Background

Code :

Output :

Complexity

Worst-case analysis

Best-case analysis

Average-case analysis

Other Info

Related Links

Merge Sort in java

Background

Code :

Output :

Complexity

Handling very large data

Related Links

Insertion Sort in Java

Background

Code :

Output :

Complexity

Related Links

Bubble Sort in Java

Background

Code :

Complexity

Output :

Bubble Sort Optimization

Code :

Output :

Related Links