Sorting

- 3 mins

Sorting

Bubble

Java implementation

static void bubble_sort(int [] data) {
        int i,j;
        for(i=0; i < data.length; i++) {
            for(j = data.length-1; j > i; j--) {
                if(data[j] < data[j-1]) {
                    int tmp = data[j];
                    data[j] = data[j-1];
                    data[j-1] = tmp;
                } 
            } 
        } 
    }

If no swaps in one pass then you are done (No need check again)

With Optimization

static void bubble_sort_opt(int [] data) {
        int i,j;
        boolean quit = false;
        for(i=0; i < data.length; i++) {
            quit = true;
            for(j = data.length-1; j > i; j--) {
                if(data[j] < data[j-1]) {
                    int tmp = data[j];
                    data[j] = data[j-1];
                    data[j-1] = tmp;
                    quit = false;
                } 
            } 
        } 
    }

Selection

Find the smallest item in the unsorted list put it at the end of the sorted list. Continue until sorted.

static void selection_sort(int [] data) {
        int i,j;
        for(i=0; i < data.length-1; i++) {
            int m = i;
            for(j = i+1; j < data.length; j++) {
                if(data[j]<data[m])m=j;

            } 
            
            int tmp = data[m];
            data[m] = data[i];
            data[i] = tmp;
             
        } 
    }

Insertion

Find i th item and insert into the correct place amongst the already sorted (i-1) items. Placed by moving all items one location upwards.

static void insertion_sort(int [] data) {
        int i;
        for(i=1; i < data.length; i++) {
            int k = data[i];
            int j = i-1;

            /* Move elements of data[0..i-1] that are greater than key, to one position 
            ahead of the current position*/
            while(j>=0 && data[j]>k){
                data[j+1]=data[j];
                j = j-1;
            }

            data[j+1]=k;
        } 
    }

Merge Sort

Topological Sort