Sorts.java

package com.learn.dbhakuni.ds;

import java.util.Arrays;
import java.util.Collections;

/**
 * Created with IntelliJ IDEA.
 * User: dbhakuni
 * Date: 31/8/14
 * Time: 12:35 PM
 * To change this template use File | Settings | File Templates.
 */
public class Sorts {



    public static int[] bubbleSort(int[] arr){

        System.out.println("bubbleSort()");
       int temp = 0;
       for(int i = 0 ; i<arr.length; i++){
            for(int j=0;j<arr.length-1;j++){
                if(arr[j] > arr[j+1]){
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
                mc++;
            }
            printArr(arr);
        }

       return arr;
    }

    public static int[] selectionSort(int[] arr){

        System.out.println("selectionSort()");
        int loc = 0;
        int min = 0;
        boolean swap = false;
        for(int i = 0 ; i<arr.length; i++){
            min = arr[i];
            for(int j=i+1;j<arr.length;j++){
                if(arr[j] < min){
                    min = arr[j];
                    loc = j;
                    swap = true;
                }
                mc++;
            }
            if(swap){
            arr[loc] = arr[i];
            arr[i] = min;
            }
            swap = false;
            printArr(arr);
        }

        return arr;
    }


    public static int[] insertionSort(int[] arr){

        System.out.println("insertionSort()");
        int x=0;
        for(int i=1; i < arr.length; i++){
            x=arr[i];
            for(int j = i; j > 0 && arr[j-1] > x ; j-- ){
                arr[j] = arr[j-1];
                arr[j-1] = x;
                mc++;
            }
            printArr(arr);
        }
        return arr;
    }

    public static int[] mergeSort(int[] arr){

        System.out.println("mergeSort()");
        return mergeSort(arr,0,arr.length-1);
    }
    static int mc = 0;
    public static int[] mergeSort(int[] arr,int l,int h){
        mc++;
        int sp = l;
        //if((h-l)>=1){
        if(!(l >= h)){
            int m = (l+h)>>>1;
            //System.out.println(l+" "+m+" "+h);
            mergeSort(arr,l,m);
            mergeSort(arr,m+1,h);
            //mergeParts(l, m, h, arr);

            //System.out.println(l+" "+m+" "+h);
            //sortMerge(arr,l,m);
            //sortMerge(arr,m,h);
            //printArr(arr,l,h);
            int i = l;
            int j = m+1;
            int temp = 0;
            while(sp<=m && j<=h){
                mc++;
                //System.out.println(arr[i]+" == "+arr[j]+" i:"+i+" j:"+j+" l:"+l+" m:"+m+" h:"+h);
                if(arr[i] < arr[j]){
                    i++;
                }else{
                    temp = arr[j];

                    for (int k = j - 1; k >= i; k--) {
                        arr[k + 1] = arr[k];
                    }
                    //arr[j] = arr[i];
                    arr[i]= temp;
                    j++;
                    m++;
                    i++;
                }
                                                                                                                                                                                              printArr(arr,l,h);
                //break;
            }

        }
        //printArr(arr,l,h);
        return arr;
    }

    private static int[] sortMerge(int[] arr,int l,int h){
        //System.out.println(l+"  "+h);
        int temp=0;
        for(int i=l;i<h-1;i++){
           if(arr[i] > arr[i+1]){
               temp = arr[i];
               arr[i] = arr[i+1];
               arr[i+1] = temp;
           }
           mc++;
        }

        return arr;
    }

    private static int[]  mergeParts(int l, int m, int h, int[] arr){

        System.out.println(l+" "+m+" "+h);
        //sortMerge(arr,l,m);
        //sortMerge(arr,m,h);
        //printArr(arr,l,h);
        int i = l;
        int j = m+1;
        int temp = 0;
        while(l<=m && j<h){
            System.out.println(arr[i]+" == "+arr[j]+" i:"+i+" j:"+j+" l:"+l+" m:"+m+" h:"+h);
            if(arr[i] < arr[j]){
                i++;
            }else{
                temp = arr[j];

                for (int k = j - 1; k >= i; k--) {
                    arr[k + 1] = arr[k];
                }
                //arr[j] = arr[i];
                arr[i]= temp;
                j++;
                m++;
                i++;
            }
            printArr(arr,l,h);
            //break;
        }
        return arr;
    }

    public  static  void main(String... args){

        int[] arr = {4,8,885,96,25,36,14,593,2,7,5,18,17,58,95,10,75,1,9,6,0,3,59,59,45,01};

        printArr(arr);
        //bubbleSort(arr);
        //selectionSort(arr);
        //insertionSort(arr);
        mergeSort(arr);
        System.out.println(mc+" mc");
        printArr(arr);

        //arr = new int[]{4, 2, 5, 7, 8};
    }

    public static void printArr(int[] arr){

        if(arr==null){
            System.out.println("Empty Array");
            return;
        }

        for(int i : arr){
            System.out.print(i);
            System.out.print(", ");
        }

        System.out.println("");
    }

    public static void printArr(int[] arr,int s,int e){

        if(arr==null){
            System.out.println("Empty Array");
            return;
        }
        System.out.print("-------------------------------------------------\n | ");
        for(int i=s;i <  e; i++){
            System.out.print(arr[i]);
            System.out.print(" | ");
        }
        System.out.println("\n-------------------------------------------------");

    }
}