Solutions week 4 - Sorting

2

3

Insertion sort

|4 6 8 2 9 5 1 7 3
 4|6 8 2 9 5 1 7 3
 4 6|8 2 9 5 1 7 3
 4 6 8|2 9 5 1 7 3
 2 4 6 8|9 5 1 7 3
 2 4 6 8 9|5 1 7 3
 2 4 5 6 8 9|1 7 3
 1 2 4 5 6 8 9|7 3
 1 2 4 5 6 7 8 9|3
 1 2 3 4 5 6 7 8 9|

Selection sort

|4 6 8 2 9 5 1 7 3
 1|6 8 2 9 5 4 7 3
 1 2|8 6 9 5 4 7 3
 1 2 3|6 9 5 4 7 8
 1 2 3 4|9 5 6 7 8
 1 2 3 4 5|9 6 7 8
 1 2 3 4 5 6|9 7 8
 1 2 3 4 5 6 7|9 8
 1 2 3 4 5 6 7 8|9
 1 2 3 4 5 6 7 8 9|

Quicksort (picking the first element as the pivot)

 4 6 8 2 9 5 1 7 3
 4|6 8 2 9 5 1 7 3|
 4 3|8 2 9 5 1|7 6
 4 3 1 2|9 5 8 7 6
 2|3 1|   4   9|5 8 7 6|
 2 1|3   4   9 5 8 7 6|
 1   2   3   4   6|5 8 7|   9
 1   2   3   4   6 5|8 7    9
 1   2   3   4   5   6   8 7    9
 1   2   3   4   5   6   7   8   9

Quicksort (using the median-of-three pivot)

 4 6 8 2 9 5 1 7 3
   pivot is 4 (median of [4, 9, 3])
 4|6 8 2 9 5 1 7 3|
 4 3|8 2 9 5 1|7 6
 4 3 1 2|9 5 8 7 6
 2 3 1    4   9 5 8 7 6
   pivot is 2 (median of [2,3,1]) and 8 (median of [9,8,6])
 2|3 1|   4   8|5 9 7 6|
 2 1|3    4   8 5|9 7 6|
 1   2   3   4   8 5 6 7|9
 1   2   3   4   7 5 6   8   9
   pivot is 6 (median of [7,5,6])
 1   2   3   4   6|5 7|   8   9
 1   2   3   4   6 5|7    8   9
 1   2   3   4   5   6   7   8   9

Mergesort

 4 6 8 2 9 5 1 7 3
   (splitting)
 4 6 8 2   9 5 1 7 3
   (splitting)
 4 6   8 2   9 5   1 7 3
   (splitting)
 4 6   8 2   9 5   1   7 3
   (sorting in base cases)
 4 6   2 8   5 9   1   3 7
   (merging)
 4 6   2 8   5 9   1 3 7
   (merging)
 2 4 6 8   1 3 5 7 9
   (merging)
 1 2 3 4 5 6 7 8 9

4

Bubble sort: stable

Only swaps when the order is wrong.

Insertion sort: stable

When inserting, the search only continues until the next element is less than or equal to what is being inserted, so an element is always inserted at higher indices than all equal elements.

Mergesort: usually stable

Depends on implementation e.g if splitting so that all elements in the left part came before the elements in the right part, and then merging by preferring elements from the left part when equal, then it will be stable.

Selection sort: not stable

The swapping can cause an element to be moved past equal elements.

Quicksort: not stable

One can swap so that equal elements get a different order when partitioning or moving the pivot.

Heapsort: not stable

Removal from the heap gives the equal elements in any order.

5

public static void boolSort(boolean[] bs) {
  int f = 0;  // O(1) extra memory

  // O(n)
  for (boolean b : bs)      // count falses
    if (!b) f++;

  // O(n) for next two loops
  for (int i = 0; i < f; i++)
    bs[i] = false;

  for (int i = f; i < bs.length; i++)
    bs[i] = true;
}

public static void boolSort1(boolean[] a) {
  int low = 0;
  int high = a.length - 1;
  
  while (true) {
    while (high >= 0 && a[high])
      high--;

    while (low < a.length && !a[low])
      low++;

    if (low >= high)
      break;

    // swap true and false
    a[low]  = !a[low];
    a[high] = !a[high];
  }
}

6

See week 2. :-|

7

splitInHalf :: [a] -> ([a], [a])
splitInHalf xs = case xs of
  []       -> ([], [])
  [x]      -> ([x],[])
  (a:b:cs) -> let (as, bs) = splitInHalf cs in (a:as, b:bs)

splitInHalf' = snd . foldr f (True, ([], []))
 where
  f x (b, (xs, ys)) | b         = (False, (x:xs, ys)) 
                    | otherwise = (True,  (xs, x:ys))

Complexity of recursive functions

Recurrence relation: \[ \begin{align} T(0) = & 1\\ T(n) = & O(1) + 2T(n-1) = O(2^n) \end{align} \]

That is: \(T(n)\) is \(O(2^n)\)

-- Returns a list of all sublists.
subsets :: [a] -> [[a]]
subsets []     = [[]]
subsets (x:xs) = [ x : s | s <- ss ] ++ ss
  where ss = subsets xs

We do a map (x:) over the recursive call to subsets with xs (which is \(T(n-1)\), and we concatenate ((++)) the resulting list to the result of the recursive call, which is again \(T(n-1)\). So we traverse the resulting list of the recursive call twice! So that means \(2T(n-1)\). Pattern matching on (x:xs) and returning the result of the concatenation is \(O(1)\).

Menu