N² Sorting

Comparison based sorting: the process to arrange a data collection involves comparing pairs of elements.

Selection Sort (textbook version)

public static int minIndex (int startIndex, int endIndex)
//Returns the index of the smallest value in
// values[startIndex]..values[endIndex]
{
   int indexOfMin = startIndex;

   for (int index = startIndex + 1; index <= endIndex; index++)
      if (values[index] < values[indexOfMin])
         indexOfMin = index;   
   return indexOfMin;
}

public static void selectionSort()
// Sorts the values array using the selection sort algorithm.
{
   int endIndex = SIZE - 1;
   for (int current = 0; current < endIndex; current++)
      swap(current, minIndex(current, endIndex));
}

Analysis of selection sorting

1. count the number of comparisons: O(n²) for the selection sort
2. count the number of swaps: O(n) for the selection sort

Bubble sort

// Algorithm: an improved bubble sort

public static boolean bubbleUp2( int startIndex, int endIndex )
// Switches adjacent pairs that are out of order
// between values[startIndex]..values[endIndex]
// beginning at values[endIndex]
//
// Returns false if a swap was made; otherwise, returns true.
{
   boolean sorted = true;
   for (int index = endIndex; index > startIndex; index--)
      if (values[index] < values[index - 1]
      {
         swap(index, index - 1);
         sorted = false;
      }
   return sorted;
}

public static void shortBubble()
// Sorts the values array using the bubble sort algorithm
// The process stops as soon as values is sorted.
{
   int current = 0;
   boolean sorted = false; 

   while ( (current < (SIZE - 1)) && !sorted )
   {
      sorted = bubbleUp(current, SIZE - 1);
   }
}

Analysis of bubble sorting

1. count the number of comparisons: O(n²) for the bubble sort
2. count the number of swaps: O(n²) for the bubble sort

Insertion Sort

// Algorithm: insertion sort

public static void insertionElement(int startIndex, int endIndex)
// Upon completion, values[0]..value[endIndex] are sorted.
{
   boolean finished = false;
   int current = endIndex;
   boolean moreToSearch = true;
   while (moreToSearch && !finished)
   {
      if (values[current] < values[current - 1])
      {
         swap(current, current - 1);
         current--;
         moreToSearch = (current != startIndex);
      }
      else
         finished = true;
   }
     
}

public static void insertionSort()
// Sorts the values array using the insertion sort algorithm.
{
   for (int count = 1; count < SIZE; count++)
     insertElement(0,count);
}

On-line Sorting Demonstrations

The Complete Collection of Algorithm Animations
Use this one -->An animation site maintained by Jason Harrison at harrison@cs.ubc.ca.