University of Cincinnati logo and link   Sorting and Searching
 
 

Sorting and Searching

UC ingot A sorting algorythm rearranges elements of a collection so that they are arranged in a sorted order.

A simple selection sort finds the smallest element of a collection.  It moves that to the front location, and swaps the value at that location with the small value.  In other words, if we started with:
  • 5
  • 4
  • 8
  • 7
  • 1
Our first iteration would give us:

  • 1
  • 4
  • 8
  • 7
  • 5
(bold indicates swapped values).

On our next iteration, we would have:

  • 1
  • 4
  • 8
  • 7
  • 5

No need to swap the 4 - it is already where it needs to be.
We continue with this process until we end up with:

  • 1
  • 4
  • 5
  • 7
  • 8
This sort works correctly, and is easy to program.  But, it is slow and inefficient.  It is given a factor of n2 performance.

 

Merge Sort