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)

BubbleSort 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;
/**
 *
 * @author Harit
 */
public class BubbleSort {
    private static int[] input = new int[]{5,1,4,2,8};

    public static void main(String args[]){
        for(int i=0; i<input.length; i++){
            System.out.print(input[i] + " ");
        }
        System.out.println("");

        for(int i=0; i<input.length; i++){
            for(int j=1; j<input.length; j++){
                if(input[j] < input[j-1]){
                    int temp = input[j];
                    input[j] = input[j-1];
                    input[j-1] = temp;
                }
            }
        }
        for(int k =0; k<input.length; k++){
            System.out.print(input[k] + " ");
        }
        System.out.println("");
    }
}

Output:

run:

5 1 4 2 8

1 2 4 5 8

BUILD SUCCESSFUL (total time: 0 seconds)