Lecture "Divide and conquer algorithms", exercise 3

[essepuntato]

Implement in Python the divide and conquer quicksort algorithm – i.e. the recursive def quicksort(input_list, start, end)​. It takes a list and the positions of the first and last elements in the list 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 of which includes the pivot value since it has been already correctly positioned through the execution of partition). In addition, define the base case of the algorithm appropriately to stop if needed before to run 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 which is useful to understand the rationale of the binary search steps.

[diegochillo]

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

def partition(input_list,start,end,pivot_position):

    outbefore = []
    outafter = []
    before = []
    after = []
    newindex = 0

    pivot_e=input_list[pivot_position]
    i=0

    for i in range(len(input_list)):

        if i<start:
           outbefore.append(input_list[i])
        elif i>end:
           outafter.append(input_list[i])
        else:
            if input_list[i]<pivot_e:
               before.append(input_list[i])
            elif input_list[i]>pivot_e:
               after.append(input_list[i])

    input_list.clear()

    input_list.extend(outbefore)
    input_list.extend(before)
    input_list.append(pivot_e)
    input_list.extend(after)
    input_list.extend(outafter)

    newindex=len(outbefore)+len(before)
    return newindex

def quicksort(input_list, start, end):
    # print("DEBUG start:" + str(start))
    # print("DEBUG end:" + str(end))

    diff = end - start

    if diff <= 0:
        # print("DEBUG list " + str(input_list))
        return 1
    else:
        position = partition(input_list, start, end, start)
        # print("DEBUG arranged " + str(input_list[position]))
        return quicksort(input_list, start, position-1) + quicksort(input_list, position + 1, end)

# Test cases
print (test_quicksort([7,2,4,1,8,6,3,5,9],0,8,[1, 2, 3, 4, 5, 6, 7, 8, 9]))
print (test_quicksort(["y","m","t","r","o"],0,4,["m", "o", "r", "t", "y"]))
print (test_quicksort([],0,0,[]))
# Test case with working range shorter than the whole list:
print (test_quicksort([7,3,5,23,11,13,2,29,17,19],3,8,[7,3,5,2,11,13,17,23,29,19]))

[AlessandraFa]

def partition(input_list, start, end, pivot_position):
    list_temp = []
    pivot = input_list[pivot_position]
    position = 0
    for item in input_list[start:end]:
        if item < pivot:
            list_temp.insert(position, item)
            position += 1
        elif item > pivot:
            list_temp.append(item)
    list_temp.insert(position, pivot)
    input_list[start:end] = list_temp
    return input_list, position + start

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

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

print(test_quicksort([1,5,8,7,3,9,2,11], 0, 8, [1, 2, 3, 5, 7, 8, 9, 11]))
print(test_quicksort(["f","n","e","d","a","m"], 1, 5, ["f","a","d","e","n","m"]))

[fcagnola]

Nuntio vobis magno gaudio, I got to a working quicksort algorithm. I kept getting problems but I finally (took me several days) squashed all bugs and what follows works like a charm

def swap(list, old_idx, new_idx):
    tmp = list[old_idx]
    list[old_idx] = list[new_idx]
    list[new_idx] = tmp

def partition(input_list, first_elem, last_elem, pivot_position):

    idx = first_elem - 1  # counter for elements smaller than pivot
    compare = first_elem  # selects element to be compared and, in case, swapped with idx

    pivot = input_list.pop(pivot_position)
    # remove the pivot from the list, in order for it not to be moved while re-arranging the list in place

    for i in range(first_elem, last_elem):  # loops through list from start to end, but
        # the list is actually shorter since the pivot was removed through the pop() operation

        if input_list[compare] >= pivot:  # if element is >= pivot, do nothing and compare the next

            compare += 1

        elif input_list[compare] < pivot:  # if element <pivot switch places to idx and compare

            idx += 1

            swap(input_list, compare, idx)

            compare += 1

    input_list.insert(idx+1, pivot)
    # the last step before returning the index of the pivot actually re-inserting the pivot at its correct index
    # print("debug: input list {}".format(input_list))
    return idx+1

def quicksort(input_list, start, end):
    length = len(input_list[start:end+1]) # compute list length in order to check base case

    if length <= 1:  # base case, if the list passed as input is len<=1 return the list itself
        return input_list

    else:
        pvt = (start+end) // 2

        pivot_pos = partition(input_list, start, end, pvt)  # pivot_pos stores the right position of the pivot value

        quicksort(input_list, start, pivot_pos-1)

        quicksort(input_list, pivot_pos+1, end)

    return input_list

list_a = [7, 2, 1, 8, 6, 3, 5, 4]
list_b = [3, 6, 7, 9, 12, 8, 23, 15, 83, 24, 16]
list_c = [0, 17, 34, 51, 68, 0, 21, 42, 63, 84, 105, 126]

print(quicksort(list_a, 0, 7))  # returns [1, 2, 3, 4, 5, 6, 7, 8]
print(quicksort(list_b, 0, 10))  # returns [3, 6, 7, 8, 9, 12, 15, 16, 23, 24, 83]
print(quicksort(list_c, 0, 11))  # returns [0, 0, 17, 21, 34, 42, 51, 63, 68, 84, 105, 126]

[edoardodalborgo]

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

def substitution(i, j, input_list):
    i += 1
    input_list.insert(i, input_list[j])
    del input_list[j + 1]
    j += 1
    return input_list, i, j

def partition(input_list, start, end, pivot):
    j, f, i = start, end, start - 1
    pivot_value = input_list[pivot]
    while j <= f:
        if j < pivot:
            if input_list[j] < pivot_value:
                input_list, i, j = substitution(i, j, input_list)
            else:
                j += 1
        else:  
            if input_list[j] >= pivot_value:
                j += 1
            else:
                input_list, i, j = substitution(i, j, input_list)
    return input_list.index(input_list[i + 1])

def quicksort(input_list, start, end):
    if len(input_list[start:end+1]) > 1:
        pivot_index = partition(input_list, start, end, start)
        quicksort(input_list, start, pivot_index-1)
        quicksort(input_list, pivot_index+1, end)
        return input_list
    else:
        return input_list

print(test_quicksort([1, 4, 2, 65, 99, 32, 13, 14], 0, 7, [1, 2, 4, 13, 14, 32, 65, 99]))
print(test_quicksort(["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens", "Coraline", "Good Omens", "American Gods"], 1, 6, ['The Graveyard Book', 'American Gods', 'Coraline', 'Coraline', 'Good Omens', 'Good Omens', 'Neverwhere']))
print(test_quicksort(["The Graveyard Book", "Coraline", "Good Omens", "Neverwhere", "The Graveyard Book", "Neverwhere", "American Gods"], 0, 6, ['American Gods', 'Coraline', 'Good Omens', 'Neverwhere', 'Neverwhere', 'The Graveyard Book', 'The Graveyard Book']))

[IlaRoss]

# from partition import  partition (copied the function here instead)

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

# algorithm
def partition(input_list, start, end, pivot_value):
    if start < 0 or start > len(input_list) - 1 or end > len(input_list) - 1:
        return 'start or end outta range'
    if start > end:
        return 'start cannot be greater than end'
    if pivot_value < start or pivot_value > end:
        return 'pivot must be included between start and end'
    else:
        pivot_el = input_list[pivot_value]
        i = start - 1
        k = start
        while (k >= start) and (k <= end):
            if input_list[k] >= pivot_el:
                k += 1
            elif input_list[k] < pivot_el:
                i += 1
                local_variable = input_list[i]
                input_list[i] = input_list[k]
                input_list[k] = local_variable
                k += 1
        copy_pivot = pivot_el
        input_list.remove(pivot_el)
        input_list.insert(i + 1, copy_pivot)
        newpivot = input_list.index(copy_pivot)
        return newpivot

def quicksort(input_list, start, end):
    if start < 0 or start > len(input_list) - 1 or end > len(input_list) - 1:
        return 'start or end outta range'
    if start > end:
        return 'start cannot be greater than end'

    else:
        newpiv = partition(input_list, start, end, start)

        # base case
        if (len(input_list[start:newpiv]) == 1) and (len(input_list[newpiv+1:end]) == 1):
            return input_list
        else:
            quicksort(input_list, start, newpiv-1)
            quicksort(input_list, newpiv+1, end)
            return input_list

# some test runs
provalist = ['z', 'c', 'g', 'b', 'f', 'm', 'e', 'a']
print(test_quicksort(provalist, 1, 6, ['z', 'b', 'c', 'e', 'f', 'g', 'm', 'a']))
unalist = [6, 3, 8, 1, 7, 9, 5]
print(test_quicksort(unalist, 2, 6, [6, 3, 1, 5, 7, 8, 9]))
alist = ['g', 'c', 'e', 'd', 'a', 'f', 'b']
print(test_quicksort(alist, 5, 3, 'start cannot be greater than end'))
blist = [3, 7, 5, 4, 1, 6, 2]
print(test_quicksort(blist, 2, 7, 'start or end outta range'))