The main goals for this lab are for you to get more comfortable with sorting algorithms.
This lab is a paired programming assignment. What exactly does that mean? You will be working in pairs on the CS lab computers. Each pair will be working on one computer. One person will be the driver and the other person will be the navigator. Here is the rule: the driver controlls the lab computer, but the driver can only type what the navigator tells them to type. For this to work well, each pair should be constantly talking among themselves. After each problem, you will switch roles, the navigator will become the driver and the driver will become the navigator.
New Partners This week you can switch partners. You will work with your partner this week and next. Your can work with a partner who you have worked with in the past.
Before leaving the lab, make sure you fill out the attendance sheet and go through your answers with a TA or instructor. You will not get full credit otherwise.
In today’s lecture we discussed Bubble Sort. We walked through an example together and discussed the algorithm.
In this part of the lab, you will implement Bubble Sort. But first, we will walk through another example together. Slide 34 form lecture 23 has the psuedocode/algorithm for Bubblesort. I’d recommend you pull it up as a reference.
Consider the following array of just 4 numbers:
9,8,7,6
. We are going to walk through BubbleSort by hand before we start implementing the algorithm.
We will be using a table to track each step of the algorithm and what the array looks like after each step.
Question 1: Fill in just the len
and j
columns below. len
represents the variable in the outerloop and j
represents the variable in the innerloop. Do not fill in any cells in the array
column yet.
Hint: You might not need every row below.
len  j  array 

4  1  
len  j  array 

4  1  
2  
3  
3  1  
2  
2  1 
Question 2: Now fill in the values in the array
column. Each value should show what the array
now looks like after len
and j
are specific values
len  j  array 

4  1  8976 
len  j  array 

4  1 
8 9 7 6 
2  8 7 9 6  
3  8 7 6 9  
3  1  7 8 6 9 
2  7 6 8 9  
2  1  6 7 8 9 
Question 3:
How many swaps do you have to make? How many pairs of elements did we consider?
Now consider the following array of 5 numbers:
5,10,6,2,7
. We are going to walk through BubbleSort by hand before we start implementing the algorithm.
We will be using a table to track each step of the algorithm and what the array looks like after each step.
Question 4: Fill in just the len
and j
columns below. len
represents the variable in the outerloop and j
represents the variable in the innerloop. Do not fill in any cells in the array
column yet.
Hint: You might not need every row below or you might need to add rows.
len  j  array 

len  j  array 

5  1  
2  
3  
4  
4  1 

2  
3  
3  1  
2  
2  1 
Question 5: Now fill in the values in the array
column. Each value should show what the array
now looks like after len
and j
are specific values
len  j  array 

len  j  array 

5  1  5 10 6 2 7 
2  5 6 10 2 7  
3  5 6 2 10 7  
4  5 6 2 7 10  
4  1 
5 6 2 7 10 
2  5 2 6 7 10  
3  5 2 6 7 10  
3  1  2 5 6 7 10 
2  2 5 6 7 10  
2  1  2 5 6 7 10 
Question 6:
How many swaps do you have to make? How many pairs of elements did we consider?
Question 7: When we had an array of size 4, we made 6 comparisons, when we had an array of size 5, we made 10 comparisons.
Imagine we have an array of size n. How many comparisons will we have to make?
Question 8: In what scenario would we make the fewest number of swaps? In what scenario would we make the most number of swaps?
We have provided starter code in Bubble.java
for you to implement. You can access the code here.
There are two methods for you to implement, swap()
and bubbleSort()
.
In today’s lecture we discussed Bubble Sort. We walked through an example together and discussed the algorithm.
In this part of the lab, you will implement Selection Sort. But first, we will walk through another example together. Slide 69 form lecture 23 has the psuedocode/algorithm for finding the minimum value, slide 37 has the algorithm for selection sort. I’d recommend you pull it up as a reference.
Consider the following array of just 4 numbers:
9,8,7,6
. We are going to walk through SelectionSort by hand before we start implementing the algorithm.
We will be using a table to track each step of the algorithm and what the array looks like after each step.
Question 9: Fill in the startIdx
, minIdx
, minVal
, and array
columns below. startIdx
represents the variable in the outerloop, minIdx
represents the index of the smallest value in the remaining parts of the list, minVal
represents the value at minIdx
, and array
represents the list after the minimum value has been moved to the current startIdx
(if needed).
Hint: You might not need every row below or you might need to add a row.
startIdx  minIdx  minVal  array 

0  
1  
2  
3 
startIdx  minIdx  minVal  array 

0  3  6  6 8 7 9 
1  2  7  6 7 8 9 
2  2  8  6 7 8 9 
Question 10: How many swaps do you have to make? How many pairs of elements did we consider?
Consider the following array of 5 numbers:
5,10,6,2,7
. We are going to walk through SelectionSort by hand before we start implementing the algorithm.
We will be using a table to track each step of the algorithm and what the array looks like after each step.
Question 11: Fill in the startIdx
, minIdx
, minVal
, and array
columns below. startIdx
represents the variable in the outerloop, minIdx
represents the index of the smallest value in the remaining parts of the list, minVal
represents the value at minIdx
, and array
represents the list after the minimum value has been moved to the current startIdx
(if needed).
Hint: You might not need every row below or you might need to add a row.
startIdx  minIdx  minVal  array 

0  
1  
2  
3 
startIdx  minIdx  minVal  array: 5, 10, 6, 2, 7 

0  3  2  2 10 6 5 7 
1  3  5  2 5 6 10 7 
2  2  6  2 5 6 10 7 
3  4  7  2 5 6 7 10 
Question 12: How many swaps do you have to make? How many pairs of elements did we consider?
SelectionSort also is an quadratic algorithm, meaning that as the size of the list increases, the amount of steps the algorithm will take in the worst case scenario increases a squared amount of times. We will discuss this in more detail on Thursday or next week.
The idea of how long an algorithm will take (or how many steps it must perform) in the worst case scenario is an important concept in Computer Science. It will be covered in detail in Data Structures and Discrete Math!
We have provided starter code in Selection.java
for you to implement. You can access the code here.
There are two methods for you to implement, swap()
and selectionSort()
.
In today’s lab we covered two sorting algorithms. This will help you for HW09.
Before leaving, make sure your TA/instructor have signed you out of the lab. If you finish the lab early, you are free to go.