Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Python code for the Quick Sort Algorithm
def quicksort(x):
if len(x) == 1 or len(x) == 0:
return x
else:
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:])
first_part.append(x[i])
return first_part + second_part
alist = [54,26,93,17,77,31,44,55,20]
quicksort(alist)
print(alist)
@CSElliyas

This comment has been minimized.

Copy link

@CSElliyas CSElliyas commented Aug 26, 2017

Some bugs.
Replace quickSort with quicksort in 18 line.

@rationality6

This comment has been minimized.

Copy link

@rationality6 rationality6 commented Oct 1, 2017

And this is Lomuto way :)

@motiur

This comment has been minimized.

Copy link

@motiur motiur commented Nov 4, 2017

Doesn't work.

@jackmandude72

This comment has been minimized.

Copy link

@jackmandude72 jackmandude72 commented Dec 6, 2017

I fixed it.

def quicksort(x):
    if len(x) == 1 or len(x) == 0:
        return x
    else:
        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:])
        first_part.append(x[i])
        return first_part + second_part

alist = [54,26,93,17,77,31,44,55,20]
print(quicksort(alist))
@gopherunner

This comment has been minimized.

Copy link

@gopherunner gopherunner commented Dec 19, 2017

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

def quicksort(x):
      if len(x) < 2:
          return x
      else:
          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)
@malhi3

This comment has been minimized.

Copy link

@malhi3 malhi3 commented Dec 22, 2017

How can I change this to a reverse quicksort?

@rgedagit

This comment has been minimized.

Copy link

@rgedagit rgedagit commented Jan 18, 2018

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

This comment has been minimized.

Copy link

@BENALI31 BENALI31 commented Feb 14, 2018

def reverse_quicksort(x):
if len(x) < 2:
return x
else:
pivot = x[-1] # last one on the list is the pivot
less = [i for i in x if i <= pivot] # i in all the table
greater = [i for i in x[:-1] if i > pivot] #our last element
return reverse_quicksort(greater) + [pivot] + reverse_quicksort(less)

@kumohen

This comment has been minimized.

Copy link

@kumohen kumohen commented Mar 7, 2018

doesn,t work .code has some error.

@imsharvanj

This comment has been minimized.

Copy link

@imsharvanj imsharvanj commented May 31, 2018

how to convert this to randomized quickSort

@pete312

This comment has been minimized.

Copy link

@pete312 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

@ajitkshirsagar

This comment has been minimized.

Copy link

@ajitkshirsagar ajitkshirsagar commented Mar 13, 2019

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

def quicksort(x):
      if len(x) < 2:
          return x
      else:
          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.

@conectcell

This comment has been minimized.

Copy link

@conectcell conectcell commented Jun 29, 2019

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

@CcGaviria

This comment has been minimized.

Copy link

@CcGaviria 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
else:
piv = int(num[0])
less = [x for x in num[1:] if int(x) < piv]
print("less",less)
higher = [x for x in num[1:] if int(x) > piv]
print(higher)
return sort(higher) + [piv] + sort(less)
for y in range(0, input()):
list = raw_input()
alist = list.split()
listOrg = sort(alist)
print(listOrg)

@anandchinna98

This comment has been minimized.

Copy link

@anandchinna98 anandchinna98 commented Jan 24, 2020

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]:
a[i],a[j]=a[j],a[i]
print("The sorted list is ",a)

@RaviPabari

This comment has been minimized.

Copy link

@RaviPabari RaviPabari commented Aug 19, 2020

@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
You can’t perform that action at this time.