Simple Sorting(Bubble, Selection & Insertion Sort)

Question:

input array:

output array:

---

Solution:

Bubble Sort:

Strategy:

1. Compare two players
2. If the one on the left is taller, swap them
3. Move one position right
4. When you reach the first sorted player, start over at the left end of the line

Code:

public void bubbleSort() {
    int out, in;
    for(out=nElems-1; out>1; out--) {
	    for(in=0; in<out; in++) {
		    if( a[in] > a[in+1] ) {
			    swap(in, in+1);
		    }
	    }
    }
}

private void swap(int one, int two) {
    long temp = a[one];
    a[one] = a[two];
    a[two] = temp;
}

Efficiency: O(N²)

---

Selection Sort:

Strategy:

1. Making a pass through all the players and picking the shortest one
2. This shortest player is then swapped with the player on the left end of the line, at position 0
3. The next time pass down the row of players, start at position 1, and, finding the minimum, swap with position 1
4. This process continues until all the players are sorted

Code:

public void selectionSort() {
    int out, in, min;
    for(out=0; out<nElems-1; out++) {
	    min = out;
	    for(in=out+1; in<nElems; in++) {
		    if(a[in] < a[min] ) {
			    min = in;
		    }
		    swap(out, min);
	    }
    }
}

private void swap(int one, int two) {
    long temp = a[one];
    a[one] = a[two];
    a[two] = temp;
}

Efficiency: O(N²)

(*For smaller values of N, the selection sort may in fact be considerably faster, especially if the swap times are much larger than the comparison times.)

---

Insertion Sort:

Strategy:

public void insertionSort() {
    int in, out;
    for(out=1; out<nElems; out++) {
	    long temp = a[out];
	    in = out;
	    while(in>0 && a[in-1] >= temp) {
		    a[in] = a[in-1];
			--in;
	    }
	    a[in] = temp;
    }
}

Efficiency: O(N²)

(Images Source: Data Structures and Algorithms in Java)