| 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) |
And this is Lomuto way :)
Doesn't work.
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))
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)
How can I change this to a reverse quicksort?
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)
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)
doesn,t work .code has some error.
how to convert this to randomized quickSort
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
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.
quicksort([8, 3, 1, 7, 0, 10, 2]) and it doesn't work
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)
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)
@pete312 use pypy3 instead of python to see some BIG RUNNING TIME DIFFRENCE
Some bugs.
Replace quickSort with quicksort in 18 line.