Algorithms - Sorting

Bubble Sort:

 public void bubbleSort()

{
int out, in;
for(out=nElems-1; out>1; out--) // outer loop (backward)
for(in=0; inif( a[in] > a[in+1] ) // out of order?
swap(in, in+1); // swap them
} // end bubbleSort()

The bubble sort routine works like this: You start at the left end of the line and
compare the two kids in positions 0 and 1. If the one on the left (in 0) is taller, you
swap them. If the one on the right is taller, you don’t do anything. Then you move
over one position and compare the kids in positions 1 and 2. Again, if the one on
the left is taller, you swap them.You continue down the line this way until you reach the

 right end. You have by no means finished sorting the kids, but you do know that the tallest kid is
on the right.This is why it’scalled the bubble sort: As the algorithm progresses, the biggest items “bubble
up” to the top end of the array.

-------------------------------------------------------------------------------------------------
 Selection Sort:

public void selectionSort()
{
int out, in, min;
for(out=0; out{
min = out; // minimum
for(in=out+1; inif(a[in] < a[min] ) // if min greater,
min = in; // we have a new min

swap(out, min); // swap them
} // end for(out)
} // end selectionSort()
//Swap Function
private void swap(int one, int two)
{
long temp = a[one];
a[one] = a[two];
a[two] = temp;
}

 What’s involved in the selection sort is making a pass through all the players and
picking (or selecting, hence the name of the sort) the shortest one. This shortest
player is then swapped with the player on the left end of the line, at position 0. Now
the leftmost player is sorted and won’t need to be moved again. Notice that in this
algorithm the sorted players accumulate on the left (lower indices), whereas in the
bubble sort they accumulated on the right.
The next time you pass down the row of players, you start at position 1, and, finding
the minimum, swap with position 1. This process continues until all the players are
sorted.

The selection sort improves on the bubble sort by reducing the number of swaps
necessary from O(N^2) to O(N). Unfortunately, the number of comparisons remains
O(N^2).

---------------------------------------------------------------------------------------------------

Insertion Sort:

public void insertionSort()
{
int in, out;
for(out=1; out{
long temp = a[out]; // remove marked item
in = out; // start shifts at out
while(in>0 && a[in-1] >= temp) // until one is smaller,
{
a[in] = a[in-1]; // shift item right,

--in; // go left one position
}
a[in] = temp; // insert marked item
} // end for
} // end insertionSort()