List three basic sorting algorithms,

Bubble sort, selection sort and insertion sort. with java implementations.

Stability of the algorithm means :

before sorting:

if (a[i1] == a[j1] && i1 < j1)

after sorting:

i2 < j2

Bubble Sort

• compare adjacent element, if previous is greater, swap them
• each run gets the biggest at the end,
• best case: o(n) with the flag, worst case: o(n2)
• stable: Yes, cause it only swaps adjacent elements

public static void bubbleSort(int [] a) {
	    for (int i = 0; i < a.length; i++) {
	        int flag = 0;
	        for (int j = 1; j < a.length - i; j++) {
	            if ((a[j - 1])  > a[j] ) {
	        	    int temp = a[j];
	                a[j] = a[j - 1];
	                a[j - 1] = temp;
	                flag = 1;
	            }
	        }
	        if (flag == 0) {
	            return;
	        }
	    }
	}

Selection Sort

• each run finds index of smallest and swap it to correct position,
• best case/worst case: o(n2),
• stable: No, cause it has non adjacent swap.

public static void selectionSort(int [] a) {
	    for (int i = 0; i < a.length; i++) {
	    	int min = i;
	        for (int j = i + 1 ; j < a.length; j++) {
	        	if( a[j] < a[min]) {
	        		min = j;
	        	}
	        }
	        if (min != i ) { // if not at the same position
	        	int temp = a[i];
                a[i] = a[min];
                a[min] = temp;
            }
	    }
	}

Insertion Sort

• for each run, assumes the elements before current position are sorted and inserts current element into correct position.
• best case: o(n) no swaping, worst case: o(n2)
• stable: Yes, cause it only swaps adjacent elements

public static void insertionSort(int[] a) {
	    for (int i = 1; i < a.length; i++) {
	        int current = a[i];
	        int j;
	        for ( j = i ; j > 0 && current < a[j -1] ; j--) {
	        	a[j] = a[j-1];
	        }
	        a[j] = current;
	    }
	}