Problems tagged with "quicksort"

Consider the following code, which takes in a list of integers and moves all of the odd numbers to the front and all of the even numbers to the end, in-place.

Remember that the \(\%\) operator computes the remainder of division. For example \(5 \% 2 = 1\) and \(4 \% 2 = 0\). This can be used to check if a number is even; if \(x \% 2 = 0\), then x is even.

def separate_odd_from_even(numbers):
    """Moves the odd numbers to the front, in-place."""
    n = len(numbers)

    def swap(i, j):
        numbers[i], numbers[j] = numbers[j], numbers[i]

    odd_barrier = 0
    even_barrier = n - 1

    while odd_barrier < even_barrier:
        if numbers[odd_barrier] % 2 == 0:
            # the number is even
            swap(odd_barrier, even_barrier)
            even_barrier -= 1
        else:
            # the number is odd
            odd_barrier += 1

Consider this code which partitions a list in a special way:

def is_even(i):
    """Returns True if i is even, False otherwise."""
    return i % 2 == 0

def mystery_partition(numbers):
    def swap(i, j):
        numbers[i], numbers[j] = numbers[j], numbers[i]

    barrier_ix = 0
    for i in range(len(numbers)):
        if is_even(numbers[i]):
            swap(i, barrier_ix)
            if numbers[barrier_ix] > numbers[0]:
                swap(0, barrier_ix)
            barrier_ix += 1

Which of the following loop invariants are true for this code? Select all that apply.

Note: any statement about an empty set or list is considered to be automatically true.

Which of the following are properties of Quicksort? Select all that apply.