Handout 10A

The purpose of this exercise is to study a LOGO procedure that sorts the items in an array.

It is easy to imagine a situation in which a user has an array of numbers that need to be sorted from smallest to largest. If you've ever alphabetized a stack of homework papers or sorted exams by score you will know that there are many different ways to do this. A few methods include:

Make two stacks, one with names that appear early in the alphabet and one of names that appear at the end of the alphabet. Sort each stack (applying this method recursively if you want to), then combine them.
Go through the stack from top to bottom. If the name on the paper you're looking at is earlier in the alphabet than the one on top of the stack, move the paper you're looking at to the top of the stack. When you finish one pass through the stack, set aside the paper on the top of the stack and repeat the process.
Split the stack into two smaller stacks. Sort each stack (applying this method recursively if you want to), then combine the two stacks.

Each of these methods of sorting a stack of homework papers can be refined into an algorithm that precisely describes the steps needed to sort the papers. Some of the algorithms work faster than others. Some require more desk space than others (the computer analog of desk space is memory.)

Some of these algorithms work well when made into computer programs, some don't. Since computers must frequently sort lists of data as large as a phone book, programmers try to use the fastest algorithm they can find which doesn't also require the computer to have large amounts of memory (laying all the homework papers out on the surface of your desk and then picking them up in order might be a fast way to sort them, but you probably don't have enough desk space to try this!)

In this exercise we learn about a moderately fast sort algorithm called an insertion sort. You can see how it compares to four other sort algorithms by viewing the web page at http://max.cs.kzoo.edu/~abrady/java/sorting/.

Imagine you have a stack of exams which you want to sort so that the exam with the lowest score is on the top of the stack and the one with the highest score is at the bottom. To use the insertion sort algorithm to do this you could:

Hold the stack between your index and middle fingers.
Take the top exam from the stack between your index and middle fingers and hold it between your thumb and index finger.
Take the top exam from the (lower) stack between your index and middle finger. If it has a higher score than the exam between your thumb and index finger (we'll call this "the upper stack"), put it below that exam. If it has a lower score, put it above the exam in the upper stack.
Take the top exam from the lower stack and leaf through the upper stack, starting from the bottom, until you have gone through all the exams with higher scores than the one on the exam from the lower stack. Put the exam from the lower stack into the upper stack above the last exam with a higher score.
Repeat step four until there are no exams left in the lower stack.

Try using this algorithm to sort exams by score, the handouts from this class by number, your phone bills by date, or your students' homework assignments by name. Although it is somewhat complicated to write down, this is a simple and obvious way to sort a short stack of papers if you have limited desk space.

Once you understand how the insertion sort algorithm works for papers you can start thinking about how to write a LOGO program to sort numbers. The stack of exams becomes an array whose elements are the exam score. Your "index finger" is like the index of a FOR command; as each exam is sorted your index finger comes to lie above the next exam to be sorted. The score of the exam being sorted can be stored as a separate variable for ease of comparision. Moving an exam from the top of the lower stack into the upper stack changes the position of all the scores in the array that were between where it started and where it was moved to. (Be sure you understand this last sentence. It's a simple idea that is very important in programming the algorithm!)

This description of the insertion sort is enough for most people, but not for a computer. Below is an even more detailed description of the insertion sort algorithm, written more terms of arrays and variables.

If you're at the end of the array (if there are no exams below your index finger), you're done.
Let INDEX stand for the index of the exam below the index finger and let I stand for the index of the lowest exam in the upper stack.
Then the SCORE on the exam below the index finger is item INDEX of the list of SCORES.
If the exam in the upper stack has a score higher than SCORE (i.e. if (ITEM :I :SCORES) > :SCORE), move that exam down to make room for the the new exam to be placed above it (i.e. SETITEM :I+1 :SCORES (ITEM :I :SCORES)).
Look at the next exam in the upper stack (MAKE "I :I-1).
Repeat from step 4 until we reach an exam in the sorted portion of the array (the stack above the index finger) that has a lower score than the exam being sorted or until we run out of exams.
If none of the exams already sorted have a lower score than the new one, put the new exam on the top of the stack and get another exam from the top of the lower stack (SETITEM 1 :SCORES :SCORE). Go back to step 1.
If we found a exam that's already been sorted which has a score lower than SCORE, insert the new one below it. (SETITEM :I+1 :SCORES :SCORE). Go back to step 1.

Programmers often write outlines like the one above before they write their programs. This is called a pseudocode description of the program. The purpose of pseudocode is to break the program down into small chunks; each individual chunk should be easy to translate into LOGO (or any other language) and so it should be easy to construct a working program from a good pseudocode description of an algorithm.

In practice it is difficulty to write good pseudocode, and it can also be difficult to translate pseudocode into LOGO. Statements like "insert the new one below it" require some interpretation. (Will the index of that location be I, I-1 or I+1?)

Although the insertion sort is a simple and natural method of sorting, it is surprisingly difficult to program. It helps to break the program into two parts; one part to handle the insertion of a value into the sorted portion of the list and one part to step through all the values needing sorting.

An example of a LOGO program that implements the insertion sort algorithm is given below. This is not the only way to implement this algorithm. Could you suggest any improvements to the code below?

TO INSERTIONSORT :ARRAY
  PRINT [The unsorted array is:]
  PRINT :ARRAY

  FOR [INDEX 2 [COUNT :ARRAY]] [        ; Go through each item in the array. ~

    MAKE "NEWSCORE (ITEM :INDEX :ARRAY)

    MAKE "POINTER :INDEX - 1            ; Points to end of sorted subarray.

    INSERT :POINTER :NEWSCORE :ARRAY    ; Insert new item in sorted subarray.  

    PRINT (SENTENCE [After sorting the first] :INDEX [values, the array is:])
    PRINT :ARRAY
  ]

  PRINT [The sorted array is:]
  PRINT :ARRAY
END

TO INSERT :I :SCORE :SCORES             ; Inserts value in sorted subarray.

  WHILE [((ITEM :I :SCORES) > :SCORE)][ ; Look until values are below :SCORE ~

                                        ; Move old values down by one.
    SETITEM :I+1 :SCORES (ITEM :I :SCORES)

    MAKE "I :I-1                        ; Move to next value in the array.
    IF :I < 1 [                         ; If we've looked at all the values, ~
      SETITEM 1 :SCORES :SCORE          ; insert :SCORE at start of array
      STOP                              ; and stop.
    ]
  ]
  SETITEM :I+1 :SCORES :SCORE           ; Insert :SCORE in its proper place.
END

; It may be possible to rewrite this in a simpler way.

Paste this program into LOGO and run the insertion sort a few times with a few different input arrays. For example:

MAKE "ARRAY1 {1 3 7 5 4 2}
INSERTIONSORT :ARRAY1

Carefully read the output of the program. Compare the changing values in the array to the changing order of the exams in a stack of papers being sorted. The print statements provide a window into the workings of the program. This helps us see how the program works, and helps even more when trying to figure out why a program doesn't work!

Once you think you understand how the program works, try running the INSERT procedure independently of the INSERTIONSORT procedure. What arguments do you need to provide to it? In a non-working program that uses different sub-procedures, we can test each procedure individually to find the problem. This is one way in which modular programming makes a programming simpler and more efficient.

Mtht420