CS102 Spring 2008

Lab # 7

Insertion Sort for IList class hierarchy

In this laboratory exercise you will write a program that sorts an IList of integers.

Download starter project and launch NetBeans

  1. Download the lab 7 starter project and unzip (and untar) it in your cs102 directory.
  2. Launch NetBeans and open the project named Lab7.  
  3. The project includes the following Java source files: Main.java, IList.java,  MTList.java, and ConsList.java. 
  4. You will complete the sort() and insert() methods in both classes MTList and ConsList.  Refer to the comments for how to proceed. 
  5. Here's some helpful information: 
    1. First, it's easy to sort an empty list, and it's easy to insert an element into the empty list. Think about what the result would be in each case, and implement both of these methods for class MTList.
    2. Next, it's easy to sort a constructed list (ConsList), if you think about it: insert the first element into the sorted rest of the list. Hint: you will implement insert() next, but while implementing sort(), assume insert() is already implemented.
    3. Finally, inserting an element into a sorted list is easy, too: compare the element to be inserted with the first element of the list. It either belongs in front of it, or after it--return the appropriate newly constructed list.


  1. Save and run your project. Your output should look something like the following. When it does, have your instructor or one of the coaches check your work before you submit your lab.  Here is the sample output:

init:
deps-jar:
compile:
run:
Unsorted list:
(96, (74, (48, (29, (68, (43, (82, (23, (59, (91, (31, (72, (94, (66, (83, (99, (83, (65, (35, (60, (83, (38, (21, (90, (53, ( ))))))))))))))))))))))))))

Sorting numbers...

Sorted list:
(21, (23, (29, (31, (35, (38, (43, (48, (53, (59, (60, (65, (66, (68, (72, (74, (82, (83, (83, (83, (90, (91, (94, (96, (99, ( ))))))))))))))))))))))))))
BUILD SUCCESSFUL (total time: 0 seconds)

Submitting your work

Once you've shown your working program to your instructor or one of the coaches, and it is verified as correct, from a terminal window, type the following commands: 

        cd
        cd cs102
        submit102 Lab7

Log out

When you are done, close NetBeans, and then locate the logout button on the menu bar. Click on the logout button (red arrow pointing through an open door).  Choose "Logout..." and then click "Yes" when prompted.  Always remember to log out when you are done using the system, to ensure that no one else uses your account.