[go: up one dir, main page]
Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Lecture "Divide and conquer algorithm", exercise 2 #26

Open
essepuntato opened this issue Dec 2, 2018 · 5 comments
Open

Lecture "Divide and conquer algorithm", exercise 2 #26

essepuntato opened this issue Dec 2, 2018 · 5 comments
Labels
Exercise The exercises that are introduced in the lectures.

Comments

@essepuntato
Copy link
Contributor

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.
@essepuntato essepuntato added the Exercise The exercises that are introduced in the lectures. label Dec 2, 2018
@hizclick
Copy link
hizclick commented Dec 5, 2018 •
edited
Loading 
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
Copy link
SeverinJB commented Dec 5, 2018 •
edited
Loading

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
Copy link

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
Copy link

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
Copy link
Contributor Author

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"]))

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
Exercise The exercises that are introduced in the lectures.
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
4 participants
@essepuntato @SeverinJB @hizclick @delfimpandiani