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 arbitrary
items are inserted one at a time, can be called
insertion sort.
Array Implementation.
The simplest form of insertion 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.
Binary Search Tree Implementation.
An alternative is to use a binary search tree to store the sorted portion.
The tree is initialized to empty. Items are inserted one at a time,
in arbitrary order.
After all items are inserted, the items are written into an array (or to
output) in sorted order using inorder traversal of the binary search tree.
AVL Tree Implementation.
An AVL Tree can be used as the binary search tree. This guarantees
better performance in the worst case.
