Lecture "Divide and conquer algorithm", exercise 2

[essepuntato]

Develop the divide and conquer algorithm def quicksort(input_list, start, end)​ that takes a list and the positions of the first and last elements in the list to consider as inputs, and that calls partition(input_list, start, end, start) (defined in the previous exercise) to partition the input list into two slices, and then applies itself recursively on the two partitions (neither of which includes the pivot value since it has been already correctly positioned by means of the execution of partition). In addition, define appropriately the base case of the algorithm so as to stop if needed before to run the partition algorithm.

Accompany the implementation of the function with the appropriate test cases.

[hizclick]

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):
    start = partition(input_list, start, end, start)
    if start != len(input_list):
        start +=1
    if(start<len(input_list)):
        partition(input_list, start, end, start)
        return input_list
    else: 
        return input_list

partition function

def partition(input_list, start, end, pivot_position):    
    pivot_value = input_list[pivot_position]
    for position, item in enumerate(input_list):
        if start <= position <= end:
            if item in input_list[start:pivot_position+1]:
                if item > pivot_value:
                    new_value = item
                    input_list.pop(position)
                    input_list.insert(end,new_value)
                    pivot_position = position
            elif item in input_list[pivot_position+1:end+1]:
                if item < pivot_value:
                    new_value = item
                    input_list.pop(position)
                    input_list.insert(start,new_value)
                    pivot_position = position

    for position, item in enumerate(input_list):
        if start <= position <= end:
            if item in input_list[start:pivot_position+1]:
                if item > pivot_value:
                    for position, item in enumerate(input_list):
                        if item == pivot_value:
                            pivot_position = position
                    partition(input_list, start, end, pivot_position)
            elif  item in input_list[pivot_position+1:end+1]:
                if item < pivot_value:
                    for position, item in enumerate(input_list):
                        if item == pivot_value:
                            pivot_position = position
                    partition(input_list, start, end, pivot_position)
    for position, item in enumerate(input_list):
        if item == pivot_value:
            return position

 #Since lists are mutable, we have used different names for each list while running the test.

my_list = list(["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens","American Gods"])
my_list2 = list(["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens","American Gods"])

my_list = list(["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens","American Gods"])
my_list2 = list(["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens","American Gods"])
my_list3 = list(["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens","American Gods"])

print(test_quicksort(my_list, 1, 4,["The Graveyard Book", "American Gods","Coraline", "Good Omens","Neverwhere"]))     #True
print(test_quicksort(my_list2, 2, 4,["The Graveyard Book", "Coraline", "American Gods","Good Omens","Neverwhere",])) #True
print(test_quicksort(my_list2, 3, 4,["The Graveyard Book", "Coraline", "American Gods" , "Good Omens","Neverwhere"])) #True

[SeverinJB]

This recursive quicksort algorithm should work with any kind of input.

Note: Against what I wrote in the other thread, I have not yet optimised the partition algorithm. However, the following partition algorithm was adjusted to work with quicksort. If I have time, I would still like to eliminate the unnecessary "excerpt_list workaround" in the partition algorithm.

+++ Quicksort. +++

def quicksort(input_list, start, end):
    if 0 <= start <= end <= len(input_list):

        if len(input_list[start:end]) <= 1:
            if input_list[start] > input_list[end]:
                input_list[end], input_list[start] = input_list[start], input_list[end]
            return input_list
        else:
            pivot_position = partition(input_list, start, end, start)
            quicksort(input_list, pivot_position + 1, end)
            quicksort(input_list, start, pivot_position)
            return input_list

    else:
        print("Input values without effect.")
        return input_list

+++ Quicksort, Partition, and Testing Sets. +++

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

def partition(input_list, start, end, pivot_position):
    pivot_object = input_list[pivot_position]
    excerpt_list = input_list[start:end + 1]
    excerpt_list.remove(pivot_object)
    ordered_list = [pivot_object]

    def conductor(input):
        input_len = len(input)

        if input_len == 1:
            return assistant(input)
        else:
            mid = input_len // 2
            conductor(input[0:mid])
            conductor(input[mid:input_len])

    def assistant(value):
        if value[0] > pivot_object:
            ordered_list.insert(len(ordered_list), value[0])
        else:
            ordered_list.insert(0, value[0])

    conductor(excerpt_list)
    input_list[start:end + 1] = ordered_list
    print(input_list.index(pivot_object))
    return input_list.index(pivot_object)

def quicksort(input_list, start, end):
    if 0 <= start <= end <= len(input_list):

        if len(input_list[start:end]) <= 1:
            if input_list[start] > input_list[end]:
                input_list[end], input_list[start] = input_list[start], input_list[end]
            return input_list
        else:
            pivot_position = partition(input_list, start, end, start)
            quicksort(input_list, pivot_position + 1, end)
            quicksort(input_list, start, pivot_position)
            return input_list

    else:
        print("Input values without effect.")
        return input_list

print(test_quicksort([3, 1, 6, 4, 7, 9, 2, 5, 8, 0], 0, 9, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]))
print(test_quicksort(["Rory", "Lorelai", "Luke", "Lane"], 1, 3, ["Rory", "Lane", "Lorelai", "Luke"]))
print(test_quicksort(["Tristan", "Logan", "Jess", "Dean"], 5, 3, ["Tristan", "Logan", "Jess", "Dean"]))

[delfimpandiani]

I haven't yet correctly separated the code between quicksort() and partition(), but this quicksort() that contains my partition() code does the job. Will continue trying to separate tomorrow.

def test_quicksort(input_list, s, e, pp, expected):
    result = quicksort(input_list, s, e, pp)
    if result == expected:
        return True
    else:
        return False

def quicksort(input_list, s, e, pp):
    len_input_list = len(input_list)
    if len_input_list <= 2: # base case: list with only 2 items
        input_list = sorted(input_list) # make sure the two items are in order
        return input_list

    else: # recursive step
        pv = input_list[pp] #pivot value is the item at pivot position in input lsit
        for item in input_list[s:(e +1)]:
            if item == pv:
                pass
            elif item < pv:
                input_list.remove(item)
                input_list.insert(s, item)
            elif item > pv:
                input_list.remove(item)
                input_list.insert(e, item)
        new_pp = input_list.index(pv)
        left = input_list[s:new_pp]
        right = input_list[(new_pp + 1): e + 1]
        left = quicksort(left, s, new_pp, pp)
        right = quicksort(right, new_pp, len(right), pp)
        input_list = input_list[0:s]
        input_list.extend(left)
        input_list.append(pv)
        input_list.extend(right)
        return input_list

my_list = list(["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens","American Gods"])

print(test_quicksort(my_list, 1, 4, 1, ["The Graveyard Book", "American Gods","Coraline", "Good Omens","Neverwhere"]))
print(test_quicksort(["Rory", "Lorelai", "Luke", "Lane"], 1, 3, 1, ["Rory", "Lane", "Lorelai", "Luke"]))

#True
#True

[delfimpandiani]

Version of partition() and quicksort() separated:

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

# partition algorithm
def partition(input_list, s, e, pp):
        pv = input_list[pp]
        for item in input_list[s:(e +1)]:
            if item == pv:
                pass
            elif item < pv:
                input_list.remove(item)
                input_list.insert(s, item)
            elif item > pv:
                input_list.remove(item)
                input_list.insert(e, item)
        new_pp = input_list.index(pv)
        return new_pp, input_list

# quicksort algorithm
def quicksort(input_list, s, e):
    left_behind = input_list[0:s]
    len_input_list = len(input_list)

    if len_input_list <= 2: # base case: list with only 2 items
        input_list = sorted(input_list) # make sure the two items are in order
        return input_list

    else: # recursive step
        pp = s
        pv = input_list[pp]
        new_pp = input_list.index(pv)
        partition_tuple = partition(input_list, s, e, pp)
        new_pp = partition_tuple[0]
        input_list = partition_tuple[1]
        left = input_list[s:new_pp]
        right = input_list[(new_pp + 1): e + 1]
        left = quicksort(left, s, new_pp)
        right = quicksort(right, new_pp, len(right))
        input_list = left_behind
        input_list.extend(left)
        input_list.append(pv)
        input_list.extend(right)
        return input_list

my_list = list(["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens","American Gods"])

print(test_quicksort(my_list, 1, 4, ["The Graveyard Book", "American Gods","Coraline", "Good Omens","Neverwhere"]))
print(test_quicksort(["Rory", "Lorelai", "Luke", "Lane"], 1, 3, ["Rory", "Lane", "Lorelai", "Luke"]))

#True
#True

[essepuntato]

Hi guys,

(As in the previous exercise)

That has been the most interesting discussion we had so far in the entire course. I really thank you for all you effort in solving it, providing an incredible number of different perspectives and angles to look at this problem. It has been great.

Here my solution to the problem - I hope you can find it clear but I'm happy to discuss it in the next lecture. The source code is available online as usual.

from partition import partition

# Test case for the algorithm
def test_quicksort(input_list, start, end, expected):
    result = quicksort(input_list, start, end)
    if expected == result:
        return True
    else:
        return False

# Code of the algorithm
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

# Run tests
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"]))