CIS 3223 Lab06 – Sorting with lists

DUE: (before the next lab, 10:30am Friday, March 7, 2008)

 

Sorting with lists

 

Sorting is one of the fundamental problems in computer science. While effective sorting algorithms are usually described in terms of sorting arrays it is also possible to perform sorting on lists. In this lab your assignment is to read data one element at a time and place the element into its adequate position in a list.

 

The list is a dually linked list, to be implemented as shown in class with three arrays, next, prev and key. The list contains information about its elements and also keeps track of available free space. The following figure illustrates how the list works.

 

 

Array Index

1

2

3

4

5

next

null

3

1

5

null

prev

3

null

2

 

 

key

“C”

“A”

“B”

 

 

list
 

free
 

 

 

 

 

 

 


The entire structure is based around three arrays and two pointers; the top row is the array index and is shown only for clarity. The list shown in the figure above contains three elements, “A”, “B” and “C” in that order. The prev field of the first element is null because there is no previous element, analogously the next field of the last element is null.

 

The pointer list points to the first element in the used list. All other elements in this list can be found by traversing the list. The pointer free points to the first element of the free list, the list of free, unused, locations. The list shown is a dually linked list that allows both forward and backward traversal. The free list is a singly liked list that allows only forward traversal.

 

TASKS

  1. Write the pseudocode for using the list data structure for sorting. The pseudo code should include the following operations:

 

    1. [list, listp, freep] = initialize(size)

 

Before using the list it needs to be initialized so that the entire list is marked as free and the indices freep for the first element of free and listp for the first element of list are set correctly. Use the parameter size for the number of rows in the list array. list should be an array of size size*3.

Hint: null pointer can be represented with 0. You should set list = 0 and free = 1.  The challenge is what should be the initial content of the list array.

 

    1. [list, listp, freep] = insert_sort(list, listp, freep, x)

 

Inserts element x into list so that all elements that come before x in the resulting list are smaller than x. The function returns the updated list, listp, freep. The pointers need to be adjusted so that the new element is correctly connected to its previous and following element.

Hint: the challenge is in finding the right place to insert the new element and to update the list properly. If you wish, you could also handle the overflow situation when the list is full (i.e. freep is null)

 

  1. Estimate the theoretical worst case running time for insert, and provide detailed justification of the analysis. Prove (any way you can) that insertion of elements using insert_sort guarantees that keys are sorted in the increasing order.

 

  1. Implement the functions Initialize and Insert. Test the code for correctness and submit the code. For your own good, it is preferable if the implementation is in Matlab.

 

  1. Test the real running time of inserting N randomly generated elements (using rand function in Matlab) into the list. Use N = {10, 100, 1000, 10000, 100000} and make sure that size > N. List the results and discuss if they are consistent with your theoretical runtime estimate in part 2.