Selection sort in Java

In-place sorting

Complexity: O(n^2)

/** To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package careercup.google;
<div id="_mcePaste">/**
 *
 * @author Harit
 */
public class SelectionSort {
    //private static int[] input = new int[]{5,1,4,2,8};
    private static int[] input = new int[]{9,8,7,4,5,6,3,2,1};

    public static void main(String args[]){
        int last_index = 0;
        int swap_index = -1;

        printArray();

        for(int i=1; i<input.length; i++){
            swap_index = returnIndex(i);
            if(input[last_index] <= input[swap_index]){
                continue;
            }
            int temp = input[last_index];
            input[last_index] = input[swap_index];
            input[swap_index] = temp;
            last_index += 1;
        }
            printArray();
    }

    private static int returnIndex(int index){
        int rindex = index;
        int smallest = input[index];
        for(int i=index+1; i<input.length; i++){
            if(input[i] < smallest){
                rindex = i;
                smallest = input[i];
            }
        }
        return rindex;
    }

    private static void printArray(){
        for(int j=0; j<input.length; j++){
            System.out.print(input[j] + " ");
        }
        System.out.println("");
    }
}

Output:

run:

9 8 7 4 5 6 3 2 1

1 2 3 4 5 6 7 8 9

BUILD SUCCESSFUL (total time: 0 seconds)

Java InsertionSort

In-place sorting

Complexity: O(n^2)

/*
* To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package careercup.google;
/**
 *
 * @author Harit
 */
public class InsertionSort {
    private static int[] input = new int[]{5,1,2,4,8};

    public static void main(String args[]){
        printArray();

        for(int i=1; i<input.length; i++){
            int key = input[i];
            int j = i-1;

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

    private static void printArray(){
        for(int k=0; k<input.length; k++){
            System.out.print(input[k] + " ");
        }
        System.out.println("");
    }
}

Output:

run:

5 1 2 4 8

1 2 4 5 8

BUILD SUCCESSFUL (total time: 0 seconds)

Insertion Sort implementation in Javaal

I am learning algorithm these days and trying to inplement them in Java at the same time to get them clear from implementation aspect as well. Feel free to use the code and let me know in case any changes can make the program better.

Code:

package com.bundle.algos;

import java.util.*;
public class InsertionSort {
public static void main(String args[]){
//int[]_array = {4,3,2,1};
int[]_array = {4,5,8,7,9,0,6,3,2,1};
for(int i=0;i<_array.length;i++){
System.out.println(“Array at ” + i + “: ” + _array[i]);
}
//int[] _insertionSortedArray = insertionSort(_array);
insertionSort(_array);

}
public static int[] insertionSort(int[] _inputArray){
//int[] resultSort;
int key = 0,i=0;
for(int j=1;j<_inputArray.length;j++){
key = _inputArray[j];
i = j – 1;
while(i>=0 && _inputArray[i] > key){
_inputArray[i + 1] = _inputArray[i];
i = i – 1;
}
_inputArray[i + 1] = key;

}
for(int k=0;k<_inputArray.length;k++){
System.out.println(“After insertion sort : ” + _inputArray[k]);
}
return _inputArray;
}
}