Computer Science 269
Introduction to Data Structures
Spring 2000
Assignment 4 and 5 Hints for Insertion Sort

Due Friday, March 3, and Friday, March 10, 2000.

Any sorting algorithm whose fundamental action is to maintain a sorted data structure which is initialized to empty and into which items are inserted in sorted order one at a time, can be called selection sort. Array Implementation. The simplest form of selection sort uses an array.
The main loop of the algorithm iterates n times. After i iterations, the smallest i items occupy their final positions at the left of the array. The remaining items, in arbitrary order, occupy the right portion of the array, which we call the unprocessed portion.
Each iteration consists of one pass over the unprocessed portion. The minimum item in that portion is identified and swapped into position i of the sorted portion. Heapsort is a more sophisticated version of selection sort. Bubblesort is also a version of selection sort, but a very poor one.