In CMSC 114, you learned four sorting algorithms: insertion sort, selection sort, bubble sort, and quick sort. The code for three of the sorting algorithms will be provided below, as well as a brief description.

Insertion Sort

void insertionSort( int arr[], int size )
{
  for ( int i = 1 ; i < size ; i++ )
    {
       for ( int j = i ; j > 0 ; j-- )
         if ( arr[ j - 1 ] > arr[ j ] )
            swap( arr[ j - 1 ], arr[ j ] ) ;
         else
            break ; // can stop now
    }
}

int swap( int & first, int & second )
{
   int temp ;
   temp = first ;
   first = second ;
   second = temp ;
}

Here's the idea of insertion sort. You have a list of numbers that are not sorted. Think of an array as consisting of a sorted portion and an unsorted portion. For example, initially, element 0 is sorted while element 1 through n - 1 is not sorted.

At each step, you will attempt to add element i to the sorted part. For example, the first step is to add element 1 in sorted order, so that elements 0 and 1 are sorted. Then, you add element 2, so that elements 0, 1, and 2 are sorted. You do this until you reach element n - 1, in which case, the whole list is sorted.

Let's pretend that the first four elements of the array are sorted, but the remaining elements have yet to be processed. At this point, index i is at 4 (for element 4).

Assume the array contains { 1, 3, 7, 9, 2, ... }. Element 4 is 2. To place 2 in the correct sport, we will compare element 4 with element 3. If element 3 is larger than element 4, swap, then check element 2 with element 1.

It turns out 2 is bigger than 9, so we swap. The array looks like { 1, 3, 7, 2, 9 }. Then, compare 2 to 7. Again, 7 is bigger than 2, so swap: { 1, 3, 2, 7, 9 }. Compare element 1 and 2. 3 is bigger than 2, so swap to get: { 1, 2, 3, 7, 9 }. Finally, compare element 0 to element 1. Since 1 is smaller than 2, there's no swap, and we stop.

Basically, once you reach a point where a swap does NOT occur, then the element is in the correct location (it behaves very much like a bubble sort in reverse), and there's no need to continue swapping.

Selection Sort

Here's the code for selection sort.

void selectionSort( int arr[], int size )
{
  for ( int i = 0 ; i < size - 1 ; i++ )
    {
       int minIndex = findMinIndex( arr, i, size ) ;
       if ( i != minIndex )
          swap( arr[ i ], arr[ minIndex ] ) ;
    }
}

int findMinIndex( int arr[], int start, int last ) 
{
   int minIndex = start ;
   for ( int i = start + 1 ; i < last ; i++ )
      if ( arr[ i ] < arr[ minIndex ] )
        minIndex = i ;

   return minIndex ;
}

This code uses the same swap() code as in insertion sort. The basic idea of insertion sort is to insert element i correctly within elements 0 to i, which is done by swapping element i backwards until the correct position is found.

In selection sort, the idea is to find the minimum value from elements i to n - 1 and swapping that value with element i. Initially i starts at 0, and you find the minimum value of the entire array, and swap that to element 0.

Then, you find the minimum element from 1 to n - 1 and swap it with element 1. Once you do this n - 1 times, the array should be sorted (you don't need to do it n times, because once n - 1 elements are correctly placed in element 0 to n - 2, the final remaining element must be in its correct spot).

Bubble Sort

Here's the code for bubble sort.

void bubbleSort( int arr[], int size )
{
  for ( int i = 0 ; i < size - 1 ; i++ )
    {
      bool hasSwapped = false;
      for ( int j = 0 ; j < ( size - 1 ) - i ; j++ )
        if ( arr[ j ] > arr[ j + 1 ] )
           {
              hasSwapped = true ;
              swap( arr[ j ], arr[ j + 1 ] );
           }
      if ( ! hasSwapped ) // sorted
         break;
    }
}

Bubble sort works as follows. In each pass, bubble sort compares elements i and i + 1, while incrementing i. The effect is to bubble the largest number to index n - 1. In the next pass, the next largest number is bubbled to index n - 2. If, during a pass, no swaps are made, then the list is sorted, and bubble sort can stop.

Run-Time Efficiency

In all three sorting algorithms, the running time is O(n²) (in the worst case). That's because there are roughly n loops, and within each loop, there's roughly n / 2 elements looked at or swapped. So, multiply together to get n²).

As far as sorting algorithms go, these are considered slow, although they work fast enough for small inputs.

The following are faster algorithms.

• quicksort O(n²)
• heapsort O(n lg n)
• mergesort O(n lg n)

While quicksort has a worst-case behavior of O(n²), in practice, this worst-case appears very infrequently (at least, compared to insertion, selection, or bubble sort), and typically runs O(n lg n). Like bubble sort, a reverse sorted list is the worst behavior for quicksort.

The other two sorting algorithms will be covered later, and while they have faster worst-case behavior, they generally run slower than quicksort in practice.