MoS Interpretation ~ Sorting Algorithms

0. Be an IT Manager Find a labor intensive job in the organization that is ripe for automation. Is the job to be automated costly in terms of human resources? Is it a job for unskilled, semi-skilled, skilled, or clerical workers? Is the automation technology capable of doing the job? In this example, the IT Manager decides that having clerks sorting records, or having workers sort inventory is the kind of job to be automated.

1. Be a Computer Scientist Devise a method for doing the sorting job. Is the proposed method systematic, reliable, and efficient? Can the method be reduced to a collection of automated steps that can be carried out by automation technology? In this example, the Computer Scientist decides that the clerical task of sorting records into sequential order can be accomplished by an automated sorting method called Selection Sort. The Computer Scientist assigns a Computer Programmer to craft a precise set of instructions for the automation equipment to perform the Selection Sort on an arbitrary collection of records.

2. Be a Computer Programmer The Computer Programmer must translate the method of sorting (in this case a Selection Sort) into detailed instructions for an automaton to follow. How big a batch of records can be processed together? What detailed instructions are required for each step in the Selection Sort? How can these instruction steps be spelled out so that the automaton can execute them faithfully to implement the Selection Sort? Assemble all the requisite steps into a Program and hand off the Program to an Automaton to carry them out.

3. Be an Automaton The Automaton executes the Program exactly as instructed.

Can you carry out the program, as if you were an automaton?

The Selection Sort

The Basic Idea 1. For a batch of items or records to be sorted into a sequential order, scan the batch and pick out the smallest element that goes first in the collection. Put this item down in a new location where the sorted collection will be assembled. 2. Having removed the first element, now go back and again find the smallest element in the remaining collection, and place it after the last item previously put into its place in the new sorted collection. 3. Repeat Step 2 until every item has been moved from the unsorted collection to the new sorted collection.

The Method Lay out the collection of items to be sorted into a row or stack so that they can be scanned, one by one. Pick up the first two items and compare them. Keep the smaller of them and put the other one back. Pick up the next item and compare it to the one you are holding. Keep the smaller one and put the other one back. Continue to move on down the line (row or stack) in this fashion, each time holding onto the smaller of the two and putting the other one back. When you have reached the end of the line, you should be holding the smallest item. Put it down in a new row or new stack where you will build the new sorted collection. Repeat the above procedure until every item in the original unsorted collection has been selected and placed in order in the new row or stack of items in their sorted order.

The Program (We will use the stack version, rather than the row version.) 1. Take a packet of cards and place them face down on the table. 2. Pick up the top card with your left hand and pick up the next card with your right hand. 3. Compare the two cards. Keep the smaller of them and discard the other into a new discard pile, face down. 4. Again draw a new card from the first pile so that you have two cards to compare. Again discard the larger onto the discard pile, and keep the smaller. (If they are equal, discard either one of them.) 5. When there are no more cards to draw, you are holding the smallest card from the original pile. Put it down (face down) into a new pile that will become the finished pile of sorted cards. 6. Now go back to the discard pile and repeat steps 1 through 4 with it as your new source pile. Do step 5, too, but put the selected card down on the pile that is becoming the finished pile of sorted cards. 7. Repeat step 6 until the stack of unsorted cards is empty. 8. Deliver the finished stack of cards in sorted order.

Reference: Wikipedia article on Selection Sort (includes animations).

Reference: David Martin's Animation of Sorting Algorithms (additional animations and comparisons)

The Execution

Pretend you are an automaton, and see if you can execute the above program with a stack of seven cards.  

Does it work?

Discussion

Selection Sort is one of the easiest sorting algorithms to spell out as a methodical program, but it is also one of the most inefficient ones, compared to the more ingenious methods that have been developed over the past 60 years.  Two of the more popular efficient sorting methods are called Merge Sort and Quick Sort, but they are much harder to understand and to spell out as a step-by-step program.   Selection Sort is very similar to one called Bubble Sort.  Here is an animation comparing Bubble Sort to Quick Sort:

Unordered Sort - Orbo Puzzle Toy

Not every sort puts items into a sequential order. When sorting parts or inventory items, one puts identical parts into a bin or shelf, but the bins or shelves themselves don't necessarily have any intrinsic order. That is, one can compare two items to see if they are identical or not, but the concept of one being less than or greater than the other is not meaningful.