Week 6: Exercises

1. Average Partition Size

In quicksort, suppose that use Hoare partitioning and choose pivot elements randomly. In each partition operation, let f be the size of the smaller partition, as a fraction of the number of elements being partitioned in that step. What value do you think f will have, on average? Perform experiments to determine whether your intuition is correct.

2. Incomplete Partitioning

Consider the Hoare partitioning function for quicksort that we saw in the lecture:

def partition(a, lo, hi):
    p = a[randrange(lo + 1, hi)]  # choose random pivot  

    i = lo
    j = hi - 1

    while True:
        # Look for two elements to swap.
        while a[i] < p:
            i += 1
        while a[j] > p:
            j -= 1

        if j <= i:             # nothing to swap
            return i
        
        a[i], a[j] = a[j], a[i]
        i += 1
        j -= 1

Suppose that we remove the last two lines from the function above. Show that the function will no longer behave correctly with this change. Specifically, give an example of an input array on which the function will fail.

3. Adjacent Elements

We can use this class to represent a linked list node:

class Node:
    def __init__(self, val, next):
        self.val = val
        self.next = next

Write a function has_adjacent(n) that takes a pointer to the first Node in a linked list and returns True if any two adjacent elements in the list have the same value, otherwise False.

4. Prepend

You are given a class LinkedList with an attribute head that points to the head of a linked list of Node objects:

class LinkedList:
    def __init__(self, head):
        self.head = head

Write a method that prepends a value to a LinkedList.

5. Append

Write a method that appends a value to a LinkedList.

6. Delete First

Write a method that deletes the first node (if any) in a LinkedList.

7. Delete Last

Write a method that deletes the last node (if any) in a LinkedList.

8. Split a List

Write a function split() that takes a pointer to the the first Node in a linked list and splits the list into two linked lists of roughly equal size. Return a pair containing these lists. The elements in the returned lists may appear in any order.

9. Merge Lists

Write a function merge() that takes pointer to the first Nodes of two sorted lists and combines them into a single sorted list.

10. Linked List Merge Sort

Write a function merge_sort() that performs a merge sort on a linked list, returning a pointer to a sorted list. Do not allocate any new list nodes while sorting.