Lab 4: Sorted Lists

In this lab, you will complete the implementations of sorted lists based on arrays (the SortedAList class). In particular, you should implement the put and the remove functions in SortedAList.h.

1. Open lab folder in VSCode

Follow the instructions from Lab 1 to open the lab folder in VSCode.

The new files in this lab are

• SortedList.h: definition of the SortedList class
• SortedAList.h: definition of the SortedAList class, as subclass of SortedList based on arrays

You should modify SortedAList.h to add your code for the 2 methods (search in the file for TODO) and upload it to the autograding system.

2. Remove and return the i-th item from the list

The remove(i) function in SortedAList is the same as in AList. Please refer to the slides for solution ideas and examples.

🧁 Tips: Adding and removing an item in the middle of an array requires shifting other items.

3. Put items into sorted lists

You should give your own implementation of the put function in the SortedAList class. This function takes one parameter it, finds a proper position in the sorted list, and inserts it at the position. The resulting list should remain sorted.

For example, say we have a sorted list l=[1,2,3,4].

• Calling l.put(5) will add 5 to the end of l, so that l now becomes [1,2,3,4,5].
• Calling l.put(0) will add 0 to the start of l, so that l now becomes [0,1,2,3,4].
• If we call l.put(2), in order to maintain the order, we should put 2 either between 1 and 2 or between 2 and 3. The resulting l will be [1,2,2,3,4].

🦄 Challenge: Can you implement the “finding proper position” part using binary search algorithm?

❗️ NOTE: You are not allowed to include the <algorithm> header to use any built-in sorting functions. Otherwise, the autograder will complain.

4. Build and test

A sample doctest test case is given in main.cpp. It invokes put several times but does not call remove. You should add your own tests for more comprehensive testing. The test cases will not be used for grading.

You can run make clean test to run the doctest cases.

5. Submitting the code

After testing the program locally, you should submit SortedAList.h to the autograding system. There will be 10 test cases in total to evaluate your implementation. For each passing test case, you will get 3 points if there is no memory error and 2 points if there are memory errors.

You may refer to the instructions from Lab 1 for more instructions.