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.

[delete4ever]

Currently it only works when the element used as pivot is unique in the list...

# Test case for the algorithm
def test_quicksort(input_list, start, end, expected):
    quicksort(input_list, start, end)
    result = input_list
    if result == expected:
        return True
    else:
        return False
# Code for partition algorithm in 2nd exercise
def partition(input_list, start, end, pivot_position):
    left_list= list()
    right_list= list()
    wanted_list= input_list[start:(end+1)]
    if pivot_position >= start:
            for i in wanted_list:
                if i < input_list[pivot_position]:
                    left_list.append(i)
                if i > input_list[pivot_position]:
                    right_list.append(i)
            input_list[:] = list(input_list[0:start] + left_list + [input_list[pivot_position]] + right_list + input_list[end+1:len(input_list)])
            return len(input_list[0:start]) + len(left_list)    
# Code for quicksort algorithm
def quicksort(input_list, start, end):
    if start <= end:
        new_pivot= partition(input_list, start, end, start)
        quicksort(input_list, start, new_pivot-1)
        quicksort(input_list, new_pivot+1, end)
# Three test runs
print(test_quicksort([5, 4, 3, 2, 1], 0, 4, [1, 2, 3, 4, 5])) #True
print(test_quicksort([5, 4, 3, 2, 1], 1, 3, [5, 2, 3, 4, 1])) #True
print(test_quicksort([1], 0, 0, [1])) #True

[leonardozilli]

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

def quicksort_partition(input_list, start, end, pivot_position):
    pivot_item = input_list[pivot_position]
    i = start - 1

    if pivot_position >= start and pivot_position <= end:
        for item in input_list[start:end + 1]:
            if item < input_list[pivot_position]:
                i += 1
                if pivot_position == i:
                    pivot_position = input_list.index(item)
                input_list[input_list.index(item)], input_list[i] = input_list[i], input_list[input_list.index(item)]
        input_list.insert(i + 1, input_list[pivot_position])
        input_list.pop(pivot_position + 1)

        pivot_new_position = input_list.index(pivot_item)
        return pivot_new_position
    else:
        return None
        
def quicksort(input_list, start, end):
    if end > start:
        pivot_position = quicksort_partition(input_list, start, end, start)
        quicksort(input_list, start, pivot_position - 1)
        quicksort(input_list, pivot_position + 1, end)
    return input_list

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

[ranacoskun]

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


def partition(input_list, start, end, pivot_position):
    i = start - 1

    for position in range(start, end + 1):
        if input_list[position] < input_list[pivot_position]:
            i = i + 1
            if i == pivot_position:
                pivot_position = position
            temp = input_list[position]
            input_list[position] = input_list[i]
            input_list[i] = temp

    temp = input_list[pivot_position]
    input_list[pivot_position] = input_list[i + 1]
    input_list[i + 1] = temp

    return i + 1


def quicksort(input_list, start, end):
    if start < end:
        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


print(test_quicksort(["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens", "American Gods"], 1, 4, ['The Graveyard Book', 'American Gods', 'Coraline', 'Good Omens', 'Neverwhere']))  # True
print(test_quicksort(["d", "e", "a", "c"], 0, 3, ['a', 'c', 'd', 'e']))  # True
print(test_quicksort([7, 6, 3, 9, 12, 1], 0, 5, [1, 3, 6, 7, 9, 12]))  # True
print(test_quicksort([7, 6, 3, 9, 12, 1], 2, 4, [7, 6, 3, 9, 12, 1]))  # True

[n1kg0r]

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


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


def quicksort(input_list, start, end):
    if end > start:
        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


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

[lucia1299]

def test_quicksort(input_list, start, end, expected):
    result = quicksort(input_list, start, end)
    return result == expected 
  
def partition(input_list, start, end, pivot_position):
    i = start-1
    for j in range(start, end+1):
        if input_list[j] < input_list[pivot_position]:
            i += 1
            input_list[j], input_list[i] = input_list[i], input_list[j]
    input_list[i+1], input_list[end] = input_list[end], input_list[i+1]    
    return i+1
   
def quicksort(input_list, start, end):
    if start < end:
        pivot_new = partition(input_list, start, end, end)
        quicksort(input_list, start, pivot_new-1)
        quicksort(input_list, pivot_new+1, end)
    return input_list
    
print(test_quicksort([0, 3, 5, 6, 2, 9, 10], 0, 6, [0, 2, 3, 5, 6, 9, 10])) #True
print(test_quicksort(['Bologna', 'Milano', 'Napoli', 'Palermo', 'Firenze', 'Venezia'], 0, 5, ['Bologna', 'Firenze', 'Milano', 'Napoli', 'Palermo', 'Venezia'])) #True
print(test_quicksort([56, 34, 901, 2, 3, 6, 345], 0, 6, [2, 3, 6, 34, 56, 345, 901])) #True

[alka2696]

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

def partition(my_list, start, end, pivot_position):
    pivot_value = my_list[pivot_position]
    store_index = start
    for i in range(start, end+1):
        if my_list[i] < pivot_value:
            my_list[store_index], my_list[i] = my_list[i], my_list[store_index]
            store_index += 1
    my_list[store_index], my_list[pivot_position] = my_list[pivot_position], my_list[store_index]
    return store_index

def quicksort(my_list, start, end):
    if start >= end:
        return my_list
    pivot_position = end
    store_index = partition(my_list, start, end, pivot_position)
    quicksort(my_list, start, store_index-1)
    quicksort(my_list, store_index+1, end)
    return my_list




print(test_quicksort([5, 4, 3, 2, 1], 0, 4,[1, 2, 3, 4, 5])) #True
print(test_quicksort([1, 2, 3, 4, 5, 6, 7], 0, 6, [1, 2, 3, 4, 5, 6, 7])) #True