Skip to content

Instantly share code, notes, and snippets.

Last active February 3, 2021 20:01
  • Star 9 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save anirudhjayaraman/897ca0d97a249180a48b50d62c87f239 to your computer and use it in GitHub Desktop.
Python code for the Quick Sort Algorithm
def quicksort(x):
if len(x) == 1 or len(x) == 0:
return x
pivot = x[0]
i = 0
for j in range(len(x)-1):
if x[j+1] < pivot:
x[j+1],x[i+1] = x[i+1], x[j+1]
i += 1
x[0],x[i] = x[i],x[0]
first_part = quicksort(x[:i])
second_part = quicksort(x[i+1:])
return first_part + second_part
alist = [54,26,93,17,77,31,44,55,20]
Copy link

how to convert this to randomized quickSort

Copy link

pete312 commented Aug 22, 2018

data = [ int(random.random() * 1000) for i in range(1000000)]
quicksort( data )

This code will break down with larger ranges like above.

but it is quick however merge sort is quicker

quick sort of 100000 numbers is 0.981563091278 seconds
merge sort of 100000 numbers is 0.594537973404 seconds

and will not break down
merge sort of 1000000 numbers is 7.16332697868 seconds
merge sort of 10000000 numbers is 88.5104949474 seconds

for comparison here is bubble sort; and I got tired of waiting on it so range is lower.
bubble sort of 20000 numbers is 30.7648730278 seconds
quick sort of 20000 numbers is 0.104420900345 seconds
merge sort of 20000 numbers is 0.103673934937 seconds

Copy link

I think that you could re-write to something like this also:

def quicksort(x):
      if len(x) < 2:
          return x
          pivot = x[0]
          less = [i for i in x[1:] if i <= pivot]
          greater = [i for i in x[1:] if i > pivot]
          return quicksort(less) + [pivot] + quicksort(greater)

I think you are 2 times traversing the list.

Copy link

ykemer commented Jun 29, 2019

quicksort([8, 3, 1, 7, 0, 10, 2]) and it doesn't work

Copy link

CcGaviria commented Jun 30, 2019

Bueno pues la razón de que no funcione es que no estamos teniendo en cuenta el tipo de dato que comparamos:
The data type is not integer...

def sort(num):
if len(num) < 2:
return num
piv = int(num[0])
less = [x for x in num[1:] if int(x) < piv]
higher = [x for x in num[1:] if int(x) > piv]
return sort(higher) + [piv] + sort(less)
for y in range(0, input()):
list = raw_input()
alist = list.split()
listOrg = sort(alist)

Copy link

simple method

a= [4,7,1,2,3,9,7,0,4,56,3]
for i in range(len(a)):
for j in range(len(a)):
if a[i]<a[j]:
print("The sorted list is ",a)

Copy link

@pete312 use pypy3 instead of python to see some BIG RUNNING TIME DIFFRENCE

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment