INTRODUCTION:

In this lesson, you will learn about three sorting algorithms: bubble, selection, and insertion. You are responsible for knowing how they work, but you do not necessarily need to memorize and reproduce the code. After counting the number of steps of each algorithm, you will have a relative sense of which is the fastest and the slowest sorting algorithm.

The key topics for this lesson are:

A. Sorting Template Program
B. Bubble Sort
C. Selection Sort
D. Insertion Sort
E. Counting Steps - Quadratic Algorithms

VOCABULARY:

BUBBLE SORT
SELECTION SORT
QUADRATIC
NONDECREASING ORDER

SWAP
INSERTION SORT
STUB

DISCUSSION:

A. Sorting Template Program

1. A program shell has been provided as Handout H.A.21.1, SortTemp.java.

2. The program asks the user to select a sorting algorithm, fills the array with an amount of data chosen by the user, calls the sorting algorithm, and gives an option of printing out the data after it has been sorted.

3. At this point, each sorting algorithm has been left as a function stub. A stub is an incomplete routine which can be called but does not solve anything yet. The stub will be filled in later as each algorithm is developed and understood.

4. Stub programming is a programming methodology strategy used during the implementation stage of program development. It allows for the coding and testing of algorithms in the context of a working program. As each sorting algorithm is completed, it can be added to the program shell and tested without having to complete the other sections.

5. This stepwise development of programs using stub programming will be used extensively in future lessons.

B. Bubble Sort

1. Here is a bubble sort algorithm.

public static void bubbleSort(int[] list)
{
  for (int outer = 0; outer < list.length - 1; outer++)
  {
    for (int inner = 0; inner < list.length-outer-1; inner++)
    {
      if (list[inner] > list[inner + 1])
      {
        //swap list[inner] & list[inner+1]
        int temp = list[inner];
        list[inner] = list[inner + 1];
        list[inner + 1] = temp;
      }
    }
  }
}

2. Given an array of 6 values, the loop variables outer and inner will evaluate as follows:

3. When outer = 0, then the inner loop will do 5 comparisons of values next to each other. As inner ranges from 0-4, it does the following comparisons:

4. If (list[inner] > list[inner+1]) is true, then the values are out of order and a swap takes place.

5. After the first pass (outer = 0), the largest value will be in its final resting place. When outer = 1, the inner loop only goes from 0 to 3 because a comparison between positions 4 and 5 is unnecessary. The inner loop is shrinking.

6. Because of the presence of duplicate values this algorithm will result in a list sorted in nondecreasing order. If there is a duplicate value it would be incorrect to say the list is in strictly increasing order because there will be spots in the list where the values do not increase.

7. Here is a small list of data to test your understanding of Bubble Sort. Write in the correct sequence of integers after each advance of outer.

C. Selection Sort

1. The logic of selection sort is similar to bubble sort except that fewer swaps are executed.

public static void selectionSort(int[] list)
{
  int min, temp;
  
  for (int outer = 0; outer < list.length - 1; outer++)
  {
    min = outer;
    for (int inner = outer + 1; inner < list.length; inner++)
    {
      if (list[inner] < list[min])
      {
        min = inner;
      }
    }
    //swap list[outer] & list[flag]
    temp = list[outer];
    list[outer] = list[min];
    list[min] = temp;
  }
}

2. Selection sort also uses passes to sort for a position in the array. Again, assuming we have a list of 6 numbers, the outer loop will range from 1 to 5. When outer = 1, we will look for the smallest value in the list and move it to the 1st position in the array.

3. However, when looking for the smallest value to place in position 1, we will not swap as we search the entire list. The algorithm will check from positions 2 to 6, keeping track of where the smallest value is found by using min as a state variable. After we have found the location of the largest value in index position min, we swap list[outer] and list[min].

4. By keeping track of where the smallest value is located and swapping once, we have a more efficient algorithm than bubble sort.

5. Here is a small list of numbers to test your understanding of Selection Sort. Fill in the correct numbers for each line after the execution of the outer loop.

D. Insertion Sort

1. Insertion sort takes advantage of this logic:

If A < B and B < C, then it follows that A < C. We can skip the comparison of A and C.

2. Consider the following partially sorted list of numbers:

2 5 8 3 9 7

The first three values of the list are sorted. The 4th value in the list (3), needs to move back in the list between the 2 and 5.

This involves two tasks, finding the correct insert point and a right shift of any values between the start and insertion point.

3. Following is the code:

public static void insertionSort(int[] list)
{
  for (int outer = 1; outer < list.length; outer++)
  {
    int position = outer;
    int key = list[position];
    
    // Shift larger values to the right
    while (position > 0 && list[position - 1] > key)
    {
      list[position] = list[position - 1];
      position--;
    }
    list[position] = key;
  }
}

4. By default, a list of one number is sorted. Hence the outer loop skips position 0 and ranges from positions 1 to list.length. For the sake of discussion, let us assume a list of 6 numbers.

5. For each pass of outer, the algorithm will solve two things concerning the value stored in list[outer]. It finds the location where list[outer] needs to be inserted in the list. Second, it does a right shift on sections of the array to make room for the inserted value.

6. Constructing the inner while loop is an appropriate place to apply DeMorgan's laws:

a.	The inner while loop postcondition has two possibilities:
	The value (key) is larger than its left neighbor.
	The value (key) moves all the way back to position 0.

b.	This can be summarized as:

	(0 == pos || list[pos - 1] <= key)

c.	If we negate the loop postcondition we get the while loop boundary condition:

	(0 != pos && list[pos-1] > key)

d.	This can also be rewritten as:

	((pos > 0) && (list[pos-1] > key))

7. The two halves of the boundary condition cover these situations:

(pos > 0) - we are still on the list, keep processing
list[pos-1] > temp) -	the value in list[pos-1] is larger than
                      key, keep moving left (pos--) to find 
                      the first value smaller than key.

8. This algorithm is appropriate when a list of data is kept in sorted order with very few changes. If a new piece of data is added, probably at the end of the list, it will get inserted back into the correct position in the list. All the other values in the list do not move and the inner while loop will not be used except when inserting a new value into the list.

9. Here is the same list of six integers to practice Insertion Sort.

E. Counting Steps - Quadratic Algorithms

1. These three sorting algorithms are categorized as quadratic sorts because the number of steps increases as a quadratic function of the size of the list.

2. It will be very helpful to study algorithms based on the number of steps they require to solve a problem. We will add code to the sorting template program and count the number of steps for each algorithm.

3. This will require the use of an instance variable - we'll call it steps. The steps variable will be maintained within the sorting class and be accessed through appropriate accessor and modifier methods. You will need to initialize steps to 0 at the appropriate spot in the main menu method.

4. As you type in the sorting algorithms, add increment statements for the instance variable steps. For example here is a revised version of the bubbleSort method:

void bubbleSort (int[] list)
{
  steps++;     // initialization of outer
  for (int outer = 0; outer < list.length-1; outer++)
  {
    steps += 3;
    //  1 - boundary check of outer loop;
    //  2 - increment, outer++
    //  3 - initialization of inner loop
    for (int inner = 0; inner < list.length-outer-1; inner++)
    {
      steps += 3;
      //  1 - boundary check of inner loop
      //  2 - increment, inner++
      //  3 - if comparison
      if (list[inner] > list[inner+1])
      {
        int temp = list[inner]
        list[inner] = list[inner + 1]);
        list[inner + 1] = temp;
        steps += 3;    // swap of list[inner] & list[inner + 1]
      }
    }
  }
}

5. It is helpful to remember that a for statement is simply a compressed while statement. Each for loop has three parts: initialization, boundary check, and incrementation.

6. As you count the number of steps, an interesting result will show up in your data. As the size of the data set (n) doubles the number of steps executed increases at a quadratic rate.

7. Bubble sort is an example of a quadratic algorithm in which the number of steps required increases at a quadratic rate as the size of the data set increases.

8. A quadratic equation in algebra is one with a squared term, like x^2. As the size (n) of the array increases, the number of steps required for any of the quadratic sorts increases by an n^2 factor.

SUMMARY/ REVIEW:

Sorting data by the computer is one of the best applications of computers and software. What takes hours or days by hand can be solved in seconds or minutes by a computer. However, these quadratic algorithms have problems sorting large amounts of data. More efficient sorting algorithms will be covered in later lessons.