Week 03 Tutorial Notes

Sorting

Group Question

  1. Consider the following sorted data, where each data item consists of a number and a colour:

    Input Data

    Index 0 1 2 3
    Value 2 4 1 2

    Mystery Sorting Algorithm

    Index 0 1 2 3
    Value 1 2 2 4

    Is the mystery algorithm stable or unstable? Why?

  2. Investigating Selection Sort:

    Input Data

    Index 0 1 2 3 4
    Value 3 1 2 4 2

    After Sorting with Selection Sort

    Index 0 1 2 3 4
    Value 1 2 2 3 4
    • Is selection sort a stable sorting algorithm?
    • Unstable sorting algorithms can sometimes get lucky and preserve the relative order of duplicates. Using the same input values find an ordering that demonstrates selection sort is unstable.
    • What other sorting algorithm is unstable? Hint: Large swaps often introduce instability.
    • What is the worst-case time complexity for selection sort?
    • What inputs result in the worst case performance of selection sort? Give more than one.

  3. Analysing time complexity:

    Compare the performance of bubble sort and insertion sort on the following types of input:

    • Sorted (e.g., \([1, 2, 3, \ldots, n]\))
    • Reverse-sorted (e.g., \([n, n - 1, n - 2, \ldots, 1]\))
    • Sorted, except the first and last numbers are swapped (e.g., \([n, 2, 3, \ldots, n - 1, 1]\))

  4. Analysing data:
    Input Sizes Sort A Sort B Sort C
    10000 0.25 1.33 0.00
    20000 1.06 2.86 0.00
    40000 3.98 6.12 0.00
    80000 15.81 13.03 0.01
    160000 65.2 27.66 0.02
    • What is the growth rate for Sort A?
    • What is the growth rate for Sort B?
    • What is the issue with Sort C timing data?
  5. What are some advantages of using merge sort compared to other sorting algorithms?

      Demonstrate how merge sort would merge the two sorted halves of this array into a single sorted array after invoking merge(A, 0, 4, 9):

                  //    0  1  2  3  4   5  6  7  8  9
            A = { 3, 4, 5, 8, 10, 1, 2, 3, 6, 13 }
            //    ^           ^               ^
            //    lo          mid             hi


Group Work Answers:

Click each section to reveal.

The mystery algorithm is unstable.

This is because the relative order of the duplicate 2's were switched. Before sorting blue was before red. And after sorting red is before blue.

Selection Sort is an unstable algorithm. An input that demonstrates this is:

Input Data

Index 0 1 2 3 4
Value 2 2 1 3 4

After Sorting

Index 0 1 2 3 4
Value 1 2 2 3 4

Another sorting algorithm that is unstable is quick sort.

The worst case for selection sort is \(O(n^2)\).

Any input order gives \(O(n^2)\) for selection sort.

  • Sorted (e.g., \([1, 2, 3, \ldots, n]\))
    • Bubble Sort: \(O(n)\).
    • Insertion Sort: \(O(n)\).
  • Reverse-sorted (e.g., \([n, n - 1, n - 2, \ldots, 1]\))
    • Bubble Sort: \(O(n^2)\).
    • Insertion Sort: \(O(n^2)\).
  • Sorted, except the first and last numbers are swapped (e.g., \([n, 2, 3, \ldots, n - 1, 1]\))
    • Bubble Sort: \(O(n^2)\).
    • Insertion Sort: \(O(n)\).

    • The growth rate for Sort A is \(O(n^2)\).

    The growth rate for Sort B is \(O(n \log(n)\).

    There is not enough data to determine the growth rate for Sort C. We need non-zero times and more than two data points to clearly show the trend line.

    Merge sort has a Worst-Case Time Complexity \(O(n \log(n))\) which is better than other algorithms with Worst Case \(O(n^2)\).

    Merge sort is also stable, unlike Quick sort which is Unstable.

    Final sorted Array : { 1, 2, 3, 3, 4, 5, 6, 8, 10, 13 }


    Bonus Group Question:

  • Given a linked list can you implement a sorting algorithm using recursion? Write pseudocode for it.