Comments (17)
diegochillo
commented on August 27, 2024
The partition function has to return the new pivot position and reorganize the content of input_list, so I check both objects in the test_partition function.
I watched Ang's video after doing the exercise. That's why I get the result in a more naive way.
def test_partition(input_list,start,end,pivot_position,expected,expected_list):
result=partition(input_list,start,end,pivot_position)
return result==expected and input_list==expected_list
def partition(input_list,start,end,pivot_position):
outbefore = list()
outafter = list()
before = list()
after = list()
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)
#print("DEBUG newindex="+str(newindex))
return newindex
print(test_partition (["Rick","Morty","Beth","Summer","Mr. Poopybutthole","Jerry"],1,5,3,5,["Rick","Morty","Beth","Mr. Poopybutthole","Jerry","Summer"]))
print (test_partition (["Birdperson","Mr. Meeseeks","Evil Morty","Squanchy","Gazorpazorpfield","Pickle Rick"],0,3,2,1,["Birdperson","Evil Morty","Mr. Meeseeks","Squanchy","Gazorpazorpfield","Pickle Rick"]))
print(test_partition([4,9,22,3,7,8,43,12,100,65],2,7,7,5,[4,9,3,7,8,12,22,43,100,65]))
from 2020-2021.
fcagnola
commented on August 27, 2024
EDIT: after reviewing the code, my original solution had two problems. Following Bruno's advice I first changed the return statement to return what the exercise actually requested: the index of the pivot (and not the list). Also, I noticed that while modifying the list in place the pivot position was changing, and I was actually comparing a static pivot position, ultimately resulting in weird outputs. I solved these problems and what follows should work:
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
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]
list_d = ["g", "a", "d", "e", "f", "b", "c", "h"]
print(partition(list_a, 0, 7, 6)) # returns True
print(partition(list_b, 0, 10, 7)) # returns True
print(partition(list_c, 0, 12, 8)) # returns True
print(partition(list_d, 0, 8, 3)) # returns True
from 2020-2021.
giorgiasampo
commented on August 27, 2024
def test_partition(input_list, start, end, pivot_position, expected):
result = partition(input_list, start, end, pivot_position)
return result == expected
def partition(input_list, start, end, pivot_position):
work_list = input_list[start:end+1]
pivot_value = input_list[pivot_position]
left_list = list()
right_list = list()
right_list.append(pivot_value)
result = input_list[:start]
for item in work_list:
if item < pivot_value:
left_list.append(item)
elif item != pivot_value:
right_list.append(item)
result.extend(left_list)
result.extend(right_list)
result.extend(input_list[end+1:])
return result, result.index(pivot_value)
print(test_partition([0,1,2,3,4,5,6,7,8,9], 2, 5, 3,([0, 1, 2, 3, 4, 5, 6, 7, 8, 9], 3)))
print(test_partition(['b','c','e','a','z','f','o','n'], 2, 7, 6,(['b', 'c', 'e', 'a', 'f', 'o', 'n', 'z'], 5)))
from 2020-2021.
SarahTew
commented on August 27, 2024
In working on this problem I ran into some weird questions for @essepuntato.
-
Why doesn't my numbers example (taken directly from the KC Ang video) end up in the same exact order as the video? Even thought it is correct it is not what I expected.
-
In my code with my alphabet example, if I leave off the 'or equal to' sign in my code, it doesn't work for the last letter in my list, "b". It doesn't go in the right place. When I have the 'or equal to" sign in the code, it works fine, but there are no repeat values in the list anyway so I don't understand why it is relevant and messing with the result in this particular case.
def partition(input_list, start, end, pivot_position):
pivot_item = input_list[pivot_position]
i = start - 1
j = start
for element in range(len(input_list[start:end+1])):
if input_list[j] >= input_list[pivot_position]:
j = j + 1
#if you remove the "=" from the above if statement, it doesn't work. Why not? Switch it out for the if statement below to see what happens. (See example with list "alphabet")
#if input_list[j] > input_list[pivot_position]:
elif input_list[j] < input_list[pivot_position]:
i += 1
input_list [i], input_list[j] = input_list[j], input_list[i]
j += 1
input_list[i+1], input_list[pivot_position] = input_list[pivot_position], input_list[i+1]
print(input_list)
return input_list.index(pivot_item)
numbers=[7, 2, 1, 8, 6, 3, 5, 4]
alphabet=["e","a","g", "c", "d", "f", "b"]
print(partition(numbers, 0, 7, 7))
print (partition(alphabet, 0, 6, 4))
For numbers it prints: [2, 1, 3, 4, 6, 7, 5, 8]
For alphabet it prints: ['a', 'c', 'b', 'd', 'e', 'f', 'g']
For alphabet without the 'or equal to' in the code it prints ['a', 'c', 'd', 'e', 'g', 'f', 'b']
from 2020-2021.
gabrielefiorenza
commented on August 27, 2024
def test_partition(input_list, start, end, pivot_position,expected):
result = partition(input_list, start, end, pivot_position)
return expected==result
def partition(input_list,start,end,pivot_position):
i=start-1
j=start
pivot= input_list[pivot_position]
input_list.pop(pivot_position)
for e in range(len(input_list[start:end+1])):
if input_list[j]>=pivot:
j+=1
elif input_list[j]<pivot:
i+=1
input_list[j], input_list[i]=input_list[i],input_list[j]
j+=1
input_list.insert(i + 1,pivot)
return(i+1)
my_list = list(["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens", "American Gods"])
print(test_partition(my_list, 1, 4, 1,2))
from 2020-2021.
SarahTew
commented on August 27, 2024
I tried make a new partition function that worked by actually dividing the list and I came up with one that sort of works.
Instead of returning all the elements in a single list, it returns them in a series of sublists. I kind of like it better because it's easier to see what was included within the start and end range and what was outside of the range.
BUT since it is done this way, you can't get the index of the pivot since it's not actually a list of elements
The other weird thing is that even though I've put the pivot element in it's own list, it doesn't become a sublist in the final list. I don't know why this one gets added as a element to the previous list and not its own sublist. (The reason I made the pivot element into a list in the first place is because I kept getting an error about mixing lists and elements when trying to add them my final list.)
To be honest, I don't really understand why it's adding them as sublists. I have tried concatenation, .extend, .append and I can't get it just be a normal list (unless the range is the entire list to begin with) What is happening here?
def partition(input_list, start, end, pivot_position):
smaller = []
larger = []
left_of_start = [input_list[:start]]
right_of_end = [input_list[end + 1:]]
pivot_element_list = [input_list[pivot_position]]
pivot_element=input_list[pivot_position]
final_list = []
j = start
for element in range(len(input_list[start:end+1])):
if input_list[j] > input_list[pivot_position]:
larger.append(input_list[j])
j += 1
elif input_list[j]< input_list[pivot_position]:
smaller.append(input_list[j])
j += 1
if start != 0:
final_list.extend(left_of_start)
final_list.extend(smaller)
final_list.extend(pivot_element_list)
final_list.extend(larger)
if end+1 != len(input_list):
final_list.extend(right_of_end)
index = final_list.index(pivot_element)
return final_list
numbers=[7, 2, 1, 8, 6, 3, 5, 4]
print(partition(numbers, 1, 4, 3))
print(partition(numbers, 0, 7, 7))
1st print (with narrow range) will print [[7], 2, 1, 8, [3, 5, 4]]
2nd print (range includes all items in list) will print: [2, 1, 3, 4, 7, 8, 6, 5]
from 2020-2021.
vanessabonanno
commented on August 27, 2024
items_list = [10, 11, 13, 14, 16, 18, 19, 15, 17]
my_pivot_position = 4
my_start = 0
my_end = 8
def test_partition(input_list, start, end, pivot_position, expected):
result = partition(input_list, start, end, pivot_position)
if result == expected:
return True
else:
return False
def partition(input_list, start, end, pivot_position):
# check if it is a valid list:
if start > end:
return "Wrong input list!"
i = start - 1
j = start
pivot = input_list.pop(pivot_position)
for element in items_list:
if element > pivot:
j += 1
elif element < pivot:
i += 1
input_list[i], input_list[j] = input_list[j], input_list[i]
j += 1
items_list.insert(i+1, pivot)
return items_list
print(partition(items_list, 3, 1, my_pivot_position)) # Wrong input list!
print(partition(items_list, my_start, my_end, my_pivot_position)) # [10, 11, 13, 14, 15, 16, 19, 18, 17]
# Tests:
print(test_partition(items_list, my_start, my_end, my_pivot_position, [10, 11, 13, 1, 15, 16, 19, 18, 17])) # False
print(test_partition(items_list, my_start, my_end, my_pivot_position, [10, 11, 13, 14, 15, 16, 19, 18, 17]))# True
print(test_partition(items_list, 5, 1, my_pivot_position, "Wrong input list!")) # True
print(test_partition(items_list, my_start, my_end, my_pivot_position, 1.5)) # False
from 2020-2021.
SofiBar
commented on August 27, 2024
def test_partition(input_list, start, end, pivot_position, expected):
if partition(input_list, start, end, pivot_position) == expected:
return True
def partition(input_list, start, end, pivot_position):
my_list = input_list[start:end]
p = input_list[pivot_position]
result_list = [p]
new_pp = 0
for item in my_list:
if item > p:
result_list.insert(new_pp + 1, item)
if item < p:
result_list.insert(new_pp, item)
new_pp += 1
del input_list[start:end]
for item in reversed(result_list):
input_list.insert(start, item)
new_pp += start
print(new_pp)
return input_list
my_num_list = [8, 7, 3, 5, 2, 1, 9, 20, ]
b_list = list(["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens", "American Gods"])
print(test_partition(my_num_list, 1, 5, 3, [8, 3, 2, 5, 7, 1, 9, 20]))
print(test_partition(b_list, 1, 5, 2, ["The Graveyard Book", "Coraline", "Good Omens", "American Gods", "Neverwhere"]))
from 2020-2021.
dbrembilla
commented on August 27, 2024
def partition(input_list, start, end, pivot_position):
before_pivot=[]
after_pivot=[]
before=[]
after=[]
pivot = input_list[pivot_position]
for i in input_list:
idx=input_list.index(i)
if idx < start:
before_pivot.append(i)
elif idx > end:
after_pivot.append(i)
else:
if i < pivot:
before.append(i)
elif i > pivot:
after.append(i)
result = before_pivot+ before + [pivot] + after + after_pivot
return result.index(pivot)
from 2020-2021.
AlessandraFa
commented on August 27, 2024
def test_partition(input_list, start, end, pivot_position, expected):
result = partition(input_list, start, end, pivot_position)
return result == expected
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
print(test_partition([1,5,8,7,3,9,2,11], 0, 7, 3, ([1, 5, 3, 2, 7, 8, 9, 11], 4)))
print(test_partition(["f","n","e","d","a","m"], 0, 5, 3, (['a', 'd', 'f', 'n', 'e', 'm'], 1)))
from 2020-2021.
AlessandroBertozzi
commented on August 27, 2024
def test_partition(input_list, start, end, pivot_position, expected):
result = partition(input_list, start, end, pivot_position)
return result == expected
def partition(input_list, start, end, pivot_position):
my_list = input_list[start:end + 1]
if len(input_list) == 1:
return pivot_position
left_list = []
right_list = []
for element in my_list:
if element > my_list[pivot_position]:
right_list.append(element)
elif element < my_list[pivot_position]:
left_list.append(element)
elif element == my_list[pivot_position]:
pass
position_pivot = len(left_list)
left_list.append(my_list[pivot_position])
my_list = left_list.extend(right_list)
return position_pivot + start
print(test_partition(["The Graveyard Book", "American Gods", "Coraline",
"Neverwhere", "Good Omens"], 1, 4, 1, 2))
print(test_partition([1], 0, 1, 0, 0))
from 2020-2021.
LuisAmmi
commented on August 27, 2024
def partition(input_list, start, end, pivot_position):
pivot_item = input_list[pivot_position]
current_list = input_list[start:end+1]
before_start = input_list[:start]
after_end = input_list[end+1:]
result = list()
result.append(pivot_item)
for i in current_list:
if i != pivot_item:
if i < pivot_item:
result.insert(result.index(pivot_item), i)
if i > pivot_item:
result.insert(result.index(pivot_item) + 1, i)
update_list = before_start + result + after_end
return update_list.index(pivot_item)
my_list = list(["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens", "American Gods"])
my_list2 = list(["Hola", "Ciao", "Amigo", "Salut", "Hello", "Hi"])
print(partition(my_list, 1, 4, 1))
print(partition(my_list2, 2, 6, 3))
from 2020-2021.
GiuliaMenna
commented on August 27, 2024
def test_partition(input_list, start, end, pivot_position, expected):
result = partition(input_list, start, end, pivot_position)
if expected == result:
return True
else:
return False
def partition(input_list, start, end, pivot_position):
part_list = input_list[start:end + 1]
pivot_value = input_list[pivot_position]
left = []
right = []
if len(input_list) == 1:
return pivot_position
for item in part_list:
if item < input_list[pivot_position]:
left.append(item)
if item == part_list[pivot_position]:
pass
if item > part_list[pivot_position]:
right.append(item)
position_pivot = len(left)
left.append(part_list[pivot_position])
input_list = left.extend(right)
return position_pivot + start
list_ = ["sole", "luna", "abete", "alberi", "canzoni"]
print(test_partition(list_, 1, 4, 3, 2))
list_numbers = [7, 3, 1, 5, 24]
print(test_partition(list_numbers, 0, 4, 1, 1))
list__=[24]
print(test_partition(list__, 0, 1, 0, 0))
family_list= ["dario","gemma","emanuela","stefania","giulia"]
print(test_partition(family_list,0,4,1,2))
from 2020-2021.
yunglong28
commented on August 27, 2024
def test_partition (input_list, start, end, pivot_position, expected):
result = partition(input_list, start, end, pivot_position)
if result == expected:
return True
else:
return False
def partition(input_list, start, end, pivot_position):
if start > end or end >= len(input_list) or pivot_position >= len(input_list):
return None # to be safe
outbefore = list() #elements before start
outafter = list() #elements after end
before = list() #elements before the pivot
after = list() #elements after the pivot
pivot_e = input_list[pivot_position]
pivoter = 1 # count the elements equal to the pivot
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])
else:
pivoter += 1 #if there's an element = to the pivot
input_list.clear()
input_list.extend(outbefore)
input_list.extend(before)
# append as many elements to the center as the ones equal to the pivot element
while pivoter > 0:
input_list.append(pivot_e)
pivoter -= 1
input_list.extend(after)
input_list.extend(outafter)
newindex = len(outbefore) + len(before)
return newindex
print(test_partition(['Mario', 'Luigi', 'Peach', 'Donkey Kong', 'Bowser Jr.'], 0, 4, 3, 1)) #True
print(test_partition([18,22,19,21,24,4], 0, 5, 0, 1)) #True
print(test_partition(['a', 'cc', 'bbb', 'ahahah', 'f'], 0, 4, 0, 0)) #True
from 2020-2021.
edoardodalborgo
commented on August 27, 2024
def test_partition(input_list, start, end, pivot, expected):
return partition(input_list, start, end, pivot) == 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])
print(test_partition(["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens", "Coraline", "Good Omens", "American Gods"], 0, 5, 3, 2))
print(test_partition(["The Graveyard Book", "Coraline", "Good Omens", "Neverwhere", "The Graveyard Book", "Neverwhere", "American Gods"], 0, 6, 5, 3))
from 2020-2021.
essepuntato
commented on August 27, 2024
About @SarahTew, @LuisAmmi and @dbrembilla's code:
input_list.index(pivot_item) # or similar
You should not use the index method to find the index of your pivot, but you should already know which is the index according to all the swaps you have done.
@SarahTew, about the other comments, did you try to run your code using Python Tutor? I think that you seeing the behaviour of the execution of your algorithm visually can help you in correcting it.
For all: as introduced during a lecture, it would be better to modify the input list "in place" (as Ang does: without creating a new list). Please remind that you must return only the new index of the pivot. However, the execution of partition will also modify the input list by swapping its elements. This is entirely possible if you consider that lists in Python are mutable objects.
from 2020-2021.
IlaRoss
commented on August 27, 2024
I took seriously the "please take your time, think about it" advice @essepuntato!
I am posting the last 5 exercises just now, sorry for that.
One question regarding partition (and, consequently, quicksort): should these work also when an element occurs more than once in the input_list? If this is the case I will correct my algorithm as it doesn't seem to work.
Thank You
# test
def test_partition(input_list, start, end, pivot_position, expected):
result = partition(input_list, start, end, pivot_position)
if result == expected:
return True
else:
return False
# algo
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
alist = ['g', 'c', 'e', 'd', 'a', 'f', 'b']
blist = [3, 7, 5, 4, 1, 6, 2]
mlist = ['Monteverdi C.', 'Gesualdo C.', 'Marenzio L.', 'Schein J.H.', 'Dowland J.', 'Willaert A.', 'Verdelot, P.',
'Palestrina G.P.']
# test runs
print(test_partition(alist, 0, 5, 3, 2))
print(test_partition(blist, 1, 5, 4, 1))
print(test_partition(mlist, 2, 7, 7, 4))
print(test_partition(alist, 4, 2, 5, 'start cannot be greater than end'))
print(test_partition(blist, 3, 8, 5, 'start or end outta range'))
print(test_partition(blist, -3, 6, 3, 'start or end outta range'))
print(test_partition(mlist, 1, 4, 6, 'pivot must be included between start and end'))
from 2020-2021.
Related Issues (20)
- Lecture "Brute-force algorithms", exercise 5 HOT 15
- Lecture "Organising information: unordered structures", exercise 1 HOT 21
- Lecture "Organising information: unordered structures", exercise 2 HOT 19
- Lecture "Organising information: unordered structures", exercise 3 HOT 20
- Lecture "Recursion", exercise 1 HOT 19
- Lecture "Recursion", exercise 2 HOT 20
- Lecture "Divide and conquer algorithms", exercise 1 HOT 19
- Lecture "Divide and conquer algorithms", exercise 3 HOT 5
- Lecture "Dynamic programming algorithms", exercise 1 HOT 21
- Lecture "Dynamic programming algorithms", exercise 2 HOT 19
- Lecture "Organising information: trees", exercise 1 HOT 9
- Lecture "Organising information: trees", exercise 2 HOT 7
- Bonus exercise (AtariGo) HOT 2
- Lecture "Backtracking algorithms", exercise 1 HOT 6
- Lecture "Backtracking algorithms", exercise 2 HOT 5
- Lecture "Organising information: graphs", exercise 1 HOT 15
- Lecture "Organising information: graphs", exercise 2 HOT 14
- Lecture "Greedy algorithms", exercise 1 HOT 5
- Lecture "Greedy algorithms", exercise 2 HOT 1
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from 2020-2021.