Home Page
The Basics
Arrays
Classes
Abstract Data Types
Dynamic Memory Allocation
Operator Overloading
Lists
C++ Style Strings
Linked Lists
Stacks and Queues
Variable Data Types
Templates
Sorting
You may think that one sorting routine is better than another but the speed of the sort really depends on what you are sorting.

There are two types of sorting          1)  internal sorting          2) external sorting
Internal sorting is done in the main memory of the program while external sorting is done by bringing in and sending data to a file of some sort.  In this class we will only be dealing with internal sorting.

A sort is an algorithm that deals with a sequence of elements.  It can be dealt with in two ways.
as an array
as a linked list

functions in sorting
internal     vs      external
representation:       array        vs.     linked list
data:                      sorted     vs.     unsorted data

we are going to deal with array sorting.

Bubble Sort:
be careful when using a bubble sort.  It has advantages in only a few cases but in general is a lousy sort.  We use it because it is fairly easy to understand how it works.

You start with an array of numbers.               (5,3,7,9,0)

You move down the list until you find one out of order and change it.  In this instance you swap position of the 5 and 3 which gives the array               (3,5,7,9,0)

you then continue down the array until you encounter another instance which needs to be swapped.  This happens when you get to the 9 and 0          (3,5,7,0,9)

This completes the first pass.  Continue until the smallest number (0) has "bubbled up" to the top of the list.  The list then moves to loop starting at the next number in list and continues through the entire array.

Let's code this using templates for practice:

#include <iostream>
#include <cstdlib>

template <class T>
void swap (T &a, T &b)
{
     T temp;
     temp = a;
     a = b;
     b = temp;
}

template <class T>
void bubble_sort( T ar[], int n)
{
bool swapped = true;

while (swapped)
{
     swapped = false;
for (int i=0; i<n-1; i++)     // note n-1 because of checking i to i+1 below
{
if (ar[i] > ar[i+1])
{
swap(ar[i], ar[i+1]);
swapped = true;
}
}
}
}
You can alternate the outer loop of a bubble sort to cut down the number of iterations it performs by replacing the while loop with:


for (end = n-2; end >=0; end--)
{
for (int i=0; i<= end; i++)
{
     same code as before…
}
}

Now you don't have to go through the entire loop each time.  It will go one position less each time through.

In general, a bubble sort is something you would really never want to use because it is an n2 algorithm.  The only time you would really want to use this is when you are sorting a list that is already sorted and are inserting something into it.  In this case the modification we showed above would fail.

Insertion Sort:                                   sorted                    unsorted
                                                             destination

An array is broken into two parts.  Sorted and unsorted.  Insertion sort will copy the first element in the unsorted section of the array into a temporary variable.  It will then find out where to put it in the list.  It has to move everything down, one at a time, until it finds the position to place the item and then inserts it.

Example:


for (int i=0; i<n; i++)
{
temp = ar[i];

for (j=i; j>0; j--)
{
if (temp < ar[j-1])
     ar[j] = ar[j-1];
else
     break;
}
ar[j] = temp;
}


To demonstrate how this works, lets say that   ^   will indicate the seperation between the sorted and the unsorted sections of the list.


^ 5 3 0 7 9          - starting position of all numbers
5 ^ 3 0 7 9          - (first pass) it places the five in the top position
3 5 ^ 0 7 9          - (second pass)  checks and swaps in the following order:

1)   it pulls out the first unsorted number (3) into a temporary variable.
2)   checks the temporary variable with the first in the sorted list (5)
3)   sees it's smaller and moves 5 to the old position of 3
4)   inserts temporary variable (3) into the j position

0 3 5 ^ 7 9          - (third pass)

Even though at this point you see that the list is sorted, the computer won't know that because it hasn't looked at the 7 or 9 yet.  When your data is already sorted you still have to copy the value out but only have to do one comparison and then re-insert it back into the list and  go to the next one.  This is still an n2 algorithm and is fairly awful as algorithm efficiency goes.


Selection Sort:                              sorted                         unsorted
                                                                                                       destination position


Selection sort works on the same principle of dividing the array into a sorted and unsorted section.  What it does is to search for the smallest value in the entire unsorted list and swap it with the first element in the unsorted section of the array.  It goes without saying that the smallest of the unsorted values will be greater than all of the sorted values.

for (int i=0; i< n-1; i++)
{
min_val = ar[i];
min_index = i;

for (j=i+1; j<n; j++)
{
if (ar[j] < min_val)
{
min_val = ar[j];
min_index = j;
}
}
temp = ar[i];
ar[i] = min_value;
ar[min_index] = temp;
}


if you started with the same array:

^ 5 3 0 7 9
0 ^ 3 5 7 9          When you start this sort:
1)   the min_value takes on the value of 5 and min_index is set to 1
2)   you start to loop from the position of min_index +1 to the number of elements
3)   if the next item is less than your min_value, you set min_value to that item and  the min_index to that position of the array.  Then continue through the rest of the unsorted list.
4)    once you reach the bottom, swap the min_value with ar[i] and continue another loop