CISC2200 Spring 2026 Lab on Sorting & Recursion

In this lab assignment, we practice implementing bubble sort, binary search iteratively and recursively, and implement insertion sort iteratively.

Download starter code

For this lab, there is no starter code. You need to create the following three files yourself:

1. A simple Makefile
2. A util.cpp in which you implement five functions (detailed below) for binary search, bubble sort and insertion sort.
3. A main.cpp in which you test your five functions by calling them on different arrays and print out the return values.

Requirements:

Please implement the following member functions in the util.cpp, and test each of them in the main.cpp.

1.iterative (non-recursive) bubble sort. See the slides for the code, note that you need to implement the checking to see if there is no swap during a bubbling round, if so, skip the rest bubbling round.

//Sort a[0...len-1] into ascending order, a is the array, len is the
// length of array a 
void bubble_sort (int a[], int len)

2. recursive bubble sort. See the slides for the pseudocode.

//Sort a[0...len-1] into ascending order, a is the array, len is the
// length of array a 
void bubble_sort_recursive (int a[], int len)

3. implement binary search iteratively (see the slides on sortedList, in which binary search is implemented as a private member function of sortedList, here you are asked to implement it as a standard alone function).

// Given that a[0...len-1] is already sorted in ascending order,
// return insert_pos for value t (i.e., if value t is to be inserted
// into array a, the correct pos t should be inserted into). 
int binary_search (int a[], int len, int t)

4. implement binary search recursively. Hint: instead of using a loop to repeat the search on left (or right) halves of the array, we make a recursive call on the left (or right) half to continue the search.

// Given that a[left...right] is already sorted in ascending order,
// return insert_pos for value t (i.e., if value t is to be inserted
// into array a, the correct pos t should be inserted into).
int binary_search (int a[], int left, int right, int t)

5. (Extra credit) implement insertion sort (see the pseudocode given below, noted that its basic component is how to insert a new value into a sorted list, which we learn in sortedList).

void insertion_sort (int a[], int len)

   for i in 1, 2, ... len-1
   {
       //given that a[0...i-1] is sorted, we insert a[i]
       // into this sorted array
       v = a[i];
       pos = binary_search (a, 0, i-1, a[i]);
       //shift every element in a[pos...i-1] backward to
       // a[pos+1 ... i]
       a[pos]=v;
   }

Submission:

This lab is due April 12th, by midnight 11:59pm. Please submit your Makefile, util.cpp, main.cpp on BB.