InsertSort Program Assignment
Program Insert Sort
This program will sort a list of numbers into ascending order. You will first program a function named insert whose purpose is to insert a number into an already sorted list maintaining the ascending order property. Function insert will use two functions named FindLoc and ShiftItems which will respctively, find the location in the list in which to insert the next number and shift the following numbers forward in the list to make space for the new number.
By repeatedly using insert to insert the next number you will create a sorted list from an unsorted list. The final function to sort the entire list will be called insertsort. In the description below, L is the entire list of numbers and S is the sorted sublist. In the examples at the end U is the unsorted sublist.
pseudocode for FindLoc
- FindLoc takes three parameters; the first is a number, N. The second parameter is the list, L and the third is the total number of items currently in the sorted sublist, S
FindLoc will find the proper position of the number, N, in the list, L.
- FindLoc will start at location 0 in the list and inspect each element of the list until it finds an element of L that is greater that N.
- FindLoc will return the location in L where it finds the first number larger than N. If all of the numbers in L are smaller than N then FindLoc will return the location after the last element in the list.
pseudocode for ShiftItems
- ShiftItems takes three parameters; the first is a location (index), I, where the new number will be inserted. The second parameter is the entire list, L and the third is the total number of items currently in S, the sublist of sorted numbers.
ShitItems will shift the items from position I to the end of the sublist S one location so that location I is now empty. The shift should begin at the end of S and work its way up to I. Now the total number of items in the sublist (S) should be increased by one. At this point we are ready to insert the new item into location I. This is done in function insert.
pseudocode for insert
- insert takes three parameters; the first is a number, N. The second parameter is the list, L and the third is the total number of items currently in the sorted sublist, S. The sort is finished when S = L; i.e., S grows to consume all of L.
insert will insert N into L in its proper position thus increasing the size of S by one. To do this
- insert will call FindLoc to determine where to place N.
- insert will then call ShiftItems in order to free up the proper location in which to place N
- insert will then place N into the position determined by FindLoc.
pseudocode for insertsort
- insertsort takes two parameters; the first is an unsorted list, L and the second is the total number of items currently in sorted sublist S.
- insertsort will divide L into two sublists. The first sublist, S, represents the items of L, beginning at location 0, that constitute a sorted list. Initially S wll contain only one number, the one at location 0. Obviously a one item list is sorted. The second sublist, U, is a list of the remaining numbers that need to be sorted. Each iteration of the main loop will take a number from U and insert it into S, thus decreasing U by one and increasing S by one. The main loop will terminate when U is empty. At which time S will consist of all of the numbers in sorted order.
- while sizeof(U) > 0
- call insert to insert the first element of U into S
-end while
Your program (also called insertsort) will do the following
while the user indicates he/she wants to sort another list
1. read in a list of numbers from the user and place them into an array.
2. call insertsort to sort the array
3. display the sorted array of numbers
end while
Suggestions for programming insertsort
1. Code a function, readints, to read in a list of numbers from the user and store the numbers in an array.
2. code a function, displayints, to write the contents of an array of numbers to the monitor
3. Write a program to test readints and writeints. I.e., at this point in time your insertsort program will only read a list of numbers from the keyboard, store them in an array and then display them on the monitor.
4. Code the function, FindLoc and test it using readints and writeints.
5. Code the function, ShiftItems and test it using FindLoc, readints and writeints.
6. Code the function, insert and test it using ShiftItems, FindLoc, readints and writeints.
7. Code the function insertsort and test it using insert, ShiftItems, FindLoc, readints and writeints.
You will also need functions to read in data and display data. The function to read in data you might name ReadInts and the one to display data you might name DisplayInts. ReadInts will take two parameters, an array and the number of elements in the array. The number of elements parameter will be a reference parameter. Input will be assumed to be from the console. Similarly DisplayInts will take two parameters, the array and the number of elements.
Example Run:
Initially S = (5), U = (2, 9, 7)
S = (2, 5), U = (9, 7)
S = (2, 5, 9), U = (7)
S = (2, 5, 7, 9), U = (), list is sorted
Top of
this page 
Home
page 
