Lecture "Divide and conquer algorithms", exercise 3

[essepuntato]

Implement the divide and conquer quicksort algorithm in Python – i.e. the recursive def quicksort(input_list, start, end)​. First, it takes a list and the positions of the first and last elements to consider as inputs. Then, it calls partition(input_list, start, end, start) (defined in the previous exercise) to partition the input list into two slices. Finally, it executes itself recursively on the two partitions (neither includes the pivot value since it has already been correctly positioned through the partition execution). In addition, define the base case of the algorithm appropriately to stop if needed before running the partition algorithm. Accompany the implementation of the function with the appropriate test cases. As supporting material, Fekete and Morr released a nonverbal definition of the algorithm [Fekete, Morr, 2018c], which is helpful to understand the rationale of the binary search steps.

[krzywonos]

More efficient alternative using list comprehension

def test_quicksort(input_list, expected):
    result = quicksort(input_list);
    if result == expected:
        print(True);
    else:
        print(False);

def quicksort(input_list):
    if len(input_list) <= 1:
        return input_list;
    pivot = input_list[len(input_list)//2]
    left = [x for x in input_list if x < pivot]
    middle = [x for x in input_list if x == pivot]
    right = [x for x in input_list if x > pivot]
    return quicksort(left) + middle + quicksort(right) 

test_quicksort(["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens", "American Gods"], ["American Gods", "Coraline", "Good Omens", "Neverwhere", "The Graveyard Book"]);

[valetedd]

This algorithm is horribly inefficient, but seems to work for now. I'll keep testing.

#Ex 3 D&C algorithms: Quicksort algorithm
def partition(input_list, start, end, pivot_position):
    if not (start <= pivot_position <= end) or len(input_list) == 0:
        return None
    pivot_element = input_list[pivot_position]

    for i in input_list[start : end + 1]:
        curr_index = input_list.index(i)
        if  i > pivot_element and curr_index < pivot_position:
            input_list.remove(i)
            input_list.insert(pivot_position, i)
            pivot_position -= 1
        elif i < pivot_element and curr_index > pivot_position:
            input_list.remove(i)
            input_list.insert(pivot_position, i)
            pivot_position += 1
        else: 
            pass
    return pivot_position

def test_quicksort(input_list, start, end, expected):
    if quicksort(input_list, start, end) == expected:
        return True
    else:
        return False

def quicksort(input_list, start, end):
    piv_pos = partition(input_list, start, end, (end + start) // 2)
    if 0 < len(range(start, end + 1)) < 3 or piv_pos == None:
        return input_list 
    else:
        quicksort(input_list, start, piv_pos - 1)
        quicksort(input_list, piv_pos + 1, end)
        return input_list

print(test_quicksort([2,-2, 9, 7, 5, 1, 11], 0, 6, [-2, 1, 2, 5, 7, 9, 11]))
print(test_quicksort(["bobcat", "cat",  "lion", "deer","beetle" , "albatros"], 0, 5, ['albatros', 'beetle', 'bobcat', 'cat', 'deer', 'lion']))
print(test_quicksort(['bobcat', 'beetle', 'cat', 'deer', 'lion', 'albatros'], 0, 5, ['albatros', 'beetle', 'bobcat', 'cat', 'deer', 'lion']))
print(test_quicksort(["bobcat", "cat",  "lion", "deer","beetle" , "albatros"], 0, 3, ['bobcat', 'cat', 'deer', 'lion', 'beetle', 'albatros'])) 
print(test_quicksort(["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens", "American Gods"], 0, 3, ['Coraline', 'Good Omens', 'Neverwhere', 'The Graveyard Book', 'American Gods']))
print(test_quicksort(["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens", "American Gods"], 0, 4, ['American Gods', 'Coraline', 'Good Omens', 'Neverwhere', 'The Graveyard Book']))
print(test_quicksort(['Coraline', 'Coraline', 'The Graveyard Book', 'American Gods', 'Good Omens', 'Neverwhere'], 0, 4, ['American Gods', 'Coraline', 'Coraline', 'Good Omens', 'The Graveyard Book', 'Neverwhere']))
print(test_quicksort(['Coraline', 'Coraline', 'The Graveyard Book', 'American Gods', 'Good Omens', 'Neverwhere'], 0, 5, ['American Gods', 'Coraline', 'Coraline', 'Good Omens', 'Neverwhere', 'The Graveyard Book']))

Improved version:

def quicksort(input_list, start, end):
    piv_pos = partition(input_list, start, end, (end + start) // 2)
   if 0 < len(range(start, end + 1)) < 3:
        return input_list
    else:
        if (piv_pos - 1) > start:
            quicksort(input_list, start, piv_pos - 1)
        if (piv_pos + 1) < end:
            quicksort(input_list, piv_pos + 1, end)
        return input_list

[Liber-R]

[frammenti]

import random

def test_quicksort(input_list, start, end):
    # Input-list order is randomized to repeat the test
    random.shuffle(input_list)
    expected = input_list[:start]+sorted(input_list[start:end+1])+input_list[end+1:]
    result = quicksort(input_list, start, end)
    if expected == result:
        return True
    else:
        return False

def quicksort(input_list, start, end):
    # Partition is iterated until base case is reached: if the sliced list has length of 1, it is already ordered
    if start < end:
        # Pivot is selected randomly as suggested by "Idea" tutorial
        pivot_position = random.randint(start, end)
        new_position = partition(input_list, start, end, pivot_position)
        quicksort(input_list, start, new_position-1) #quicksort is end inclusive as partition is end inclusive
        quicksort(input_list, new_position+1, end)
        return input_list
    else:
        # If input_list is empty or has only one element
        return input_list

def partition(input_list, start, end, pivot_position):
    # Input conditions are no longer necessary because inputs are defined by quicksort function
    i = start - 1
    pivot = input_list.pop(pivot_position)
    for j in range(start,end):
        if input_list[j] < pivot:
            i += 1
            input_list[i], input_list[j] = input_list[j], input_list[i]
    new_position = i + 1
    input_list.insert(new_position, pivot)
    return new_position

num_list = [7, 2, 1, 8, 6, 3, 5, 4]
book_list = ["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens", "American Gods"]
binary_list = [0, 0, 1, 1, 0, 1, 0, 0, 1]

# 5 tests full range
print(test_quicksort(list(num_list), 0, 7))
print(test_quicksort(list(num_list), 0, 7))
print(test_quicksort(list(num_list), 0, 7))
print(test_quicksort(list(num_list), 0, 7))
print(test_quicksort(list(num_list), 0, 7))
# Tests with different range
print(test_quicksort(list(num_list), 2, 5))
print(test_quicksort(list(num_list), 2, 5))
print(test_quicksort(list(num_list), 2, 5))
print(test_quicksort(list(num_list), 2, 5))
print(test_quicksort(list(num_list), 2, 5))
# Tests with range of 2, first and last positions
print(test_quicksort(list(num_list), 0, 1))
print(test_quicksort(list(num_list), 0, 1))
print(test_quicksort(list(num_list), 0, 1))
print(test_quicksort(list(num_list), 0, 1))
print(test_quicksort(list(num_list), 0, 1))
print(test_quicksort(list(num_list), 6, 7))
print(test_quicksort(list(num_list), 6, 7))
print(test_quicksort(list(num_list), 6, 7))
print(test_quicksort(list(num_list), 6, 7))
print(test_quicksort(list(num_list), 6, 7))
# Tests with other kinds of list
print(test_quicksort(list(book_list), 1, 4)) # First example
print(test_quicksort(list(binary_list), 1, 7)) # List with repetitions
print(test_quicksort([1], 0, 0)) # One-item list
print(test_quicksort([], 0, 0)) # Empty list

[qwindici]

import random

def partition(input_list, start, end, pivot_position):
    i = start - 1
    j = start
    pivot = input_list[pivot_position]
    while j <= end:
        if input_list[j] > pivot:
            j += 1
        elif input_list[j] < pivot:
            i += 1
            # swap j and i
            input_list[j], input_list[i] = input_list[i], input_list[j]
            j += 1
        else:
            j += 1
        input_list.remove(pivot)
        input_list.insert(i + 1, pivot)
        return i + 1

def quicksort(input_list, start, end):
    if not input_list:
        return []
    if start >= end:
        return
    else:
        pivot_position = random.randint(start, end)
        sorted_pivot_position = partition(input_list, start, end, pivot_position)
        # left
        quicksort(input_list, start, sorted_pivot_position)
        # right
        quicksort(input_list, sorted_pivot_position + 1, end)
    return input_list

def test_quick_sort(input_list, start, end, expected):
    if quicksort(input_list, start, end) == expected:
        return True
    else:
        return False

# tests
# numbers
print(test_quick_sort([90, 7, 9, 2, 4, 1], 0, 5, expected=[1, 2, 4, 7, 9, 90]))
print(
    test_quick_sort(
        [94, 67, 11, 32, 70, 72, 88], 0, 6, expected=[11, 32, 67, 70, 72, 88, 94]
    )
)
print(test_quick_sort([3, 5, 2, 8, 1, 1, 4], 1, 5, expected=[3, 1, 1, 2, 5, 8, 4]))
print(test_quick_sort([3, 5, 2, 1, 1, 4, 8], 2, 6, expected=[3, 5, 1, 1, 2, 4, 8]))

# letters
print(
    test_quick_sort(
        ["b", "z", "s", "l", "m", "a"], 0, 5, expected=["a", "b", "l", "m", "s", "z"]
    )
)

# empty list
print(test_quick_sort([], 0, 5, expected=[]))

[rufferbaraldi]

def test_quicksort(input_list, start, end, expected):
    result = quicksort(input_list, start, end)
    if result == expected:
        return True
    else:
        return False

def quicksort(input_list, start, end):
    if start < end:
        p = partition(input_list, start, end, end)
        quicksort(input_list, start, p-1)
        quicksort(input_list, p+1, end)
    return input_list

def partition(input_list, start, end, pivot_position):
    i = start-1
    pivot_position = end
    for j in range(start,end):
        if input_list[j] < input_list[pivot_position]:
            i = i + 1
            (input_list[j], input_list[i]) = (input_list[i], input_list[j])
    (input_list[i+1], input_list[pivot_position]) = (input_list[pivot_position], input_list[i+1])
    return i+1

print(test_quicksort(["The Graveyard Book", "American Gods", "Good Omens", "Coraline", "Neverwhere"], 1, 4, ["The Graveyard Book", "American Gods", "Coraline", "Good Omens", "Neverwhere"]))
print(test_quicksort([2, 8, 9, 3, 5, 1, 7], 0, 6, [1, 2, 3, 5, 7, 8, 9]))
print(test_quicksort([2, 2, 9, 3, 5, 1, 5], 0, 6, [1, 2, 2, 3, 5, 5, 9]))

[Sergpoipoip]

def test_quicksort(input_list, start, end, expected):
    return quicksort(input_list, start, end) == expected

def partition(input_list, start, end, pivot_position):
    el = input_list[pivot_position]
    for i in input_list[start:end+1]:
        if i < el:
            input_list.remove(i)
            input_list.insert(start, i)
        elif i > el:
            input_list.remove(i)
            input_list.insert(end, i)
    return input_list.index(el)

def quicksort(input_list, start, end):
    if end < start:
        return
    pivot_position = partition(input_list, start, end, start)
    quicksort(input_list, start, pivot_position-1)
    quicksort(input_list, pivot_position+1, end)
    return input_list

my_list = ["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens", "American Gods"]
my_list_1 = [0, 23, 11, -3, 20, 18, -1, 34]
my_list_2 = ['A', 'Z', 'X', 'P', 'B', 'F', 'Q']
print(test_quicksort(my_list, 1, 4, ["The Graveyard Book", "American Gods", "Coraline", "Good Omens", "Neverwhere"]))
print(test_quicksort(my_list_1, 0, 6, [-3, -1, 0, 11, 18, 20, 23, 34]))
print(test_quicksort(my_list_2, 0, 6, ['A', 'B', 'F', 'P', 'Q', 'X', 'Z']))

[simocasaz]

def test_quicksort(input_list, start, end, expected):
    result = quicksort(input_list, start, end)
    if result == expected:
        return True
    else:
        return False

def swap(pos_1, pos_2, input_list):
    prov = input_list[pos_1]
    input_list[pos_1] = input_list[pos_2]
    input_list[pos_2] = prov

def partition(input_list, start, end, pivot_position):
    i = start - 1
    swap (pivot_position, end, input_list)
    for j in range(start, end):
        if input_list[j] < input_list[end]:
            i += 1
            swap(i, j, input_list)
    new_pivot_position = i + 1
    input_list.insert(new_pivot_position, input_list[end])
    del input_list[end + 1]
    return new_pivot_position

def quicksort(input_list, start, end):
    if start >= end:
        return input_list
    else:
        pivot = partition(input_list, start, end, (start + end) // 2)
        quicksort(input_list, start, pivot - 1)
        quicksort(input_list, pivot + 1, end)
        return input_list

print(test_quicksort(["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens", "American Gods"], 0, 4, ["American Gods", "Coraline", "Good Omens", "Neverwhere", "The Graveyard Book"]))
print(test_quicksort(["I soliti ignoti"], 0, 0, ["I soliti ignoti"]))
print(test_quicksort(["Inglourious Basterds", "Jackie Brown", "The Hateful Eight", "Reservoir Dogs", "Once Upon a Time in Hollywood", "Kill: Bill Vol. 2", "Kill Bill: Vol. 1", "Pulp Fiction"], 0, 7, ["Inglourious Basterds", "Jackie Brown", "Kill Bill: Vol. 1", "Kill: Bill Vol. 2", "Once Upon a Time in Hollywood", "Pulp Fiction", "Reservoir Dogs", "The Hateful Eight"]))
print(test_quicksort([4, 10, 3, 7, 8, 9, 1], 0, 6, [1, 3, 4, 7, 8, 9, 10]))
print(test_quicksort([10, 5, 7, 4, 2, 9], 0, 5, [2, 4, 5, 7, 9, 10]))