Skip to content

Activity: Simple Sorts

Learning Objectives

  • Trace through bubble, insertion, and selection sort algorithms
  • Analyze and compare the performance of sorting algorithms

Time to Complete: 45 minutes

To Receive Credit: Submit individual PDF to Canvas

Complete the simple_sorts_questions.pdf and submit to Canvas.

Instructions

For these activities, follow the steps closely. Your goal is to complete all parts of the activity within the time provided.

Solution

Try these on your own before looking at the solution pdf.

Collaboration Required

You will need at least one partner for this activity.

  • One person will be the Sorter
  • The other will be the Counter

You will switch roles throughout the activity.

Your Name(s):

Part 1: Bubble Sort (Warmup)

Time: 10 minutes

1. Roles

  • The Sorter manipulates the array.
  • Track indices i and j while tracing.
  • Say "comparison" when comparing elements.
  • Say "swap" when swapping elements.

The Counter: - Tallies comparisons - Tallies swaps - Checks that the algorithm is followed exactly.

Both partners must trace the algorithm exactly as written.

Don't have Physical Objects? Use a virtual deck of cards online: Deck of cards

2. Setup

Using cards, pieces of paper, dice, or other objects, arrange the following numbers in an array like so: Arrange the numbers:

Index 0 1 2 3

Value 4 2 5 3

Treat: arr.length = 4 Only change values at indices 0--3.

3. Bubble Sort Code

public static void bubbleSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        for (int j = 1; j < arr.length - i; j++) { // Note the (length - i)
            if (arr[j - 1] > arr[j]) { // This is a "comparison"
                swap(arr, j - 1, j);
            }
        }
    }
}

The swap() method is not shown but swaps two elements in the array.

  1. Trace through bubbleSort and physically sort the array. Count the number of comparisons and swaps (separately) you make:

Again, treat arr.length as 4 when tracing through the code, meaning you should only change values between indices 0 through 3

Questions

What is the Final Order(just list the numbers): ____________________________

Number of Comparisons: ____________________________

Number of Swaps: ____________________________

5. Concept Question

What basic operation should we count when analyzing Bubble Sort? Justify your choice.

Takeaway

Bubble Sort repeatedly swaps adjacent elements that are out of order, causing the largest unsorted element to bubble to the end of the array.

Part 2: Insertion Sort

Time: 15 minutes

  1. Arrange the array:

Index 0 1 2 3

Value 4 2 5 3

2. Insertion Sort Code

public static void insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        for (int j = i; j > 0; j--) {
            if (arr[j - 1] > arr[j]) { // comparison
                swap(arr, j - 1, j);
            } else {
                break;
            }
        }
    }
}

3. Switch roles, then trace through the code and sort the elements. Count the number of comparisons and swaps you make:

Comparisons: ____________________________

Swaps: ____________________________

4. Arrange the array:

Index 0 1 2 3

Value 5 4 3 2

  1. Repeat sorting and counting.

Comparisons: ____________________________

Swaps: ____________________________

  1. Now use:

Index 0 1 2 3 4

Value 5 5 4 3 2

Ensure duplicate numbers are distinguishable (colors, suits, etc.).

Order of the two 5s: ____________________________

  1. Repeat sorting and counting.

Comparisons: ____________________________

Swaps: ____________________________

8. Before we move on, take a look at the final order of your numbers. Remember that we had multiple elements with the same number but unique in some way.

Take a look at the original order of the 5's. Let's look and see if this is still the case in the final order...

Does the final order preserve the original order of duplicate elements? Explain. ____________________________

Stable Sorting

Insertion Sort is a stable sorting algorithm, This means that it preserves the relative order of equal elements in the sorted array.

9. Worst Case Input (n = 5)

Think about the worst-case scenario for Insertion Sort. What would it look like? For n=5, give an example of input that would result in the worst-case:

Answer: ____________________________

Best Case Input (n = 5)

Now, think about the best-case scenario for Insertion Sort. What would it look like? For n=5, give an example of input that would result in the best-case:

Answer: ____________________________

10. Time Complexity (Comparisons)

Look at the code and think about what happens in the worst- and best-case scenarios. Consider comparisons as your basic operation to count.

Comparisons: What is the worst-case Big-θ time complexity of Insertion Sort? Worst-case Big-Θ:

Answer: ____________________________

Comparisons: What is the best-case Big-θ time complexity of Insertion Sort?

Best-case Big-Θ:

Answer: ____________________________

Time Complexity (Swaps)

Now consider swaps as your basic operation. Swaps: What is the worst-case Big-θ time complexity of Insertion Sort?

Worst-case Big-Θ:

Answer: ____________________________

Swaps: What is the best-case Big-θ time complexity of Insertion Sort? Best-case Big-Θ:

Answer: ____________________________

Takeaway

How Insertion Sort works is that it maintains a sorted "subarray" on the left. We then go through each element in the right and move it to its correct position in the sorted subarray. This is repeated until the entire array is sorted.

It is stable and has a best-case time complexity of Θ(n) when considering the number of comparisons. However, in the worst-case, it has a time complexity of Θ(n^2).

  • Stable
  • Best case: Θ(n)
  • Worst case: Θ(n²)

Part 3: Selection Sort

Time: 15 minutes

  1. Arrange:

Index 0 1 2 3

Value 4 2 5 3

Selection Sort Code

  1. Review the code:
public static void selectionSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {

        int bigindex = 0;

        for (int j = 1; j < arr.length - i; j++) {
            if (arr[j] > arr[bigindex]) {
                bigindex = j;
            }
        }

        swap(arr, bigindex, (arr.length - 1) - i);
    }
}
  1. Switch roles, then trace through the code and sort the elements. Count the number of comparisons and swaps you make:

Trace the algorithm.

Questions

Comparisons: ____________________________

Swaps: ____________________________

  1. Now, arrange the elements like so:

Index 0 1 2 3

Value 5 4 3 2

  1. Repeat the process of sorting and counting.

Comparisons:\ ____________________________

Swaps:\ ____________________________

How does this compare with the previous run? Anything to note?

  1. Now, arrange the following elements like so:

Index 0 1 2 3 4

Value 5 5 4 3 2

Again, make sure the duplicate numbers are unique.

Order of the two 5s:\ ____________________________ For example, "the green 5 is before the red 5".

  1. Repeat sorting.

Comparisons:\ ____________________________

Swaps:\ ____________________________

Stability Question

  1. Is Selection Sort a stable sorting algorithm? Justify your answer.

Answer: ____________________________

Time Complexity

  1. Think about the worst-case scenario for Selection Sort. What would it look like? Comparisons Big-Θ: For n=4, give an example of input that would result in the worst-case:

____________________________

  1. Arrange the following elements like so:

Index 0 1 2 3 4

Value 2 3 4 5 5

11.

Comparisons:\ ____________________________

Swaps:\ ____________________________

** Same or different from previous run? ____________________________

  1. Now, analyze the code and answer the following questions:

Comparisons: What is the Big-θ time complexity of Selection Sort? ____________________________

Now consider swaps as your basic operation. Swaps: What is the Big-θ time complexity of Selection Sort? ____________________________

13. Finally, Describe the Algorithms in your own words:

Selection Sort:\ ____________________________

Insertion Sort:\ ____________________________

Bubble Sort:\ ____________________________

Part 4: Exact Time Complexity

  1. Consider comparisons as the basic operation. Work out the exact time complexity for each algorithm. Use B(n) for best-case and W(n) for worst-case.

Bubble Sort (Best / Worst): ____________________________

Insertion Sort (Best / Worst): ____________________________

Selection Sort (Best / Worst): ____________________________

  1. Now consider swaps as the basic operation.

Work out the exact time complexity for each algorithm.

Use B(n) for best-case and W(n) for worst-case.

Bubble Sort (Best / Worst): ____________________________

Insertion Sort (Best / Worst): ____________________________

Selection Sort (Best / Worst): ____________________________

3. Visualization Tool

You may find it helpful to visualize sorting algorithms:

VisuAlgo -- Sorting

Try selecting different algorithms and clicking Sort to see how they work.

4. Swap Method Exercise

Write a method that swaps two elements in an integer array.

public static void swap(int[] arr, int i, int j) {
    // Your code here
}

What is the code for the swap method?

5. Advanced Challenge

Instead of counting comparisons and swaps, count array accesses.

Assume: - Each comparison = 2 array accesses - Each swap = 4 array accesses

Determine exact time complexity in terms of array accesses.

Bubble Sort (Best / Worst): ____________________________

Insertion Sort (Best / Worst): ____________________________

Selection Sort (Best / Worst): ____________________________

Submission

Complete the simple_sorts_questions.pdf and submit to Canvas.

Everyone must submit their own copy to receive credit.