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.