when I try to open the Partition.pdf file from Amir's recitation , it says the file doesn't exist anymore.
Where can i see the code for the partition?
In the exam, can I do the partition like that:
lst1=[x for x in lst in x<pivot]
lst2=[x for x in lst in if x>pivot]
It runs over the list twice but the complexity stays the same:O(n)
Date: 30 Jan 2013 23:10
Number of posts: 2
RSS: New posts
fixed (inplace_partition file now exists).
Your solution will not work correctly if pivot appears more than once in the original list (but that's easy to fix). it is indeed O(n) as you mentioned.
Also, pay attention that your solution is not inplace, as it creates copies for all the elements.