from random import *
from time import *
import sys
def quicksort(mylist, pivot, end):
# pivot will always be the first element in the list/sub-list
if (len(mylist) == end) and (pivot == 0): # shuffle the list before we start (only happens on the first call)
shuffle(mylist)
if (pivot == end) or (pivot == end-1):
return mylist
sr = pivot + 1 # start from element after pivot
sl = end - 1 # start from end of list
smaller = None
bigger = None
smallest_index = 0
while sr <= sl:
if mylist[sr] > mylist[pivot]:
bigger = mylist[sr]
else:
sr += 1
if mylist[sl] < mylist[pivot]:
smaller = mylist[sl]
else:
sl -= 1
if (sr < sl) and (smaller is not None) and (bigger is not None):
mylist[sr] = smaller
mylist[sl] = bigger
smallest_index = sr
sr += 1
sl -= 1
smaller = None
bigger = None
if (sr-1 == sl) and ((smaller is not None) or (mylist[sl] <= mylist[pivot])):
smaller = mylist[sl]
smallest_index = sl
mylist[smallest_index], mylist[pivot] = mylist[pivot], mylist[smallest_index]
quicksort(mylist, pivot, smallest_index)
quicksort(mylist, smallest_index+1, end)
return mylist
I also used sys.setrecursionlimit(1000000) because it was originally breaking the limit with larger lists, but I end up getting exit code 0xC00000FD
I've been working at this for hours and just can't seem to crack it. I can't tell if I just need a better implementation or if I went wrong somewhere. This was the only implementation I could come up with unfortunately.
Help please?
User contributions licensed under CC BY-SA 3.0