QUICKSORT
Definisi
Quick
sort adalah
algoritma sorting yang berdasarkan pembandingan dengan metoda divide-and-conqueror.
Disebut Quick Sort, karena
Algoritma quick sort mengurutkan
dengan sangat cepat. Algoritma quick
sort mengurutkan dengan
sangat cepat,Pengurutan Quick sort di tentukan oleh pivot dan pivot tersebut
bisa di depan , belakang dan tengah. namun algoritma ini sangat komplex dan
diproses secara rekursif. Tetapi langkah pengerjaanya rumit.
Ilustrasi
Algoritma
done = False
while not done:
while z <= n and listangka[z] <=
posisi:
z = z + 1
while listangka[n] >= posisi and n
>= z:
n = n -1
if n < z:
done = True
else:
temp = listangka[z]
listangka[z] = listangka[n]
listangka[n] = temp
Kode Program
def
quickSorttengah(alist):
quickSortHelper(alist,0,len(alist)-1)
def
quickSortHelper(alist,first,last):
if first<last:
splitpoint =
partition(alist,first,last)
quickSortHelper(alist,first,splitpoint-1)
quickSortHelper(alist,splitpoint+1,last)
def partition(alist,first,last):
tengah = (first+last)//2
pivotvalue = alist.pop(tengah)
leftmark = first
rightmark = last-1
done = False
while not done:
while leftmark <= rightmark and
alist[leftmark] <= pivotvalue:
leftmark = leftmark + 1
while alist[rightmark] >= pivotvalue
and rightmark >= leftmark:
rightmark = rightmark -1
if rightmark < leftmark:
done = True
else:
temp = alist[leftmark]
alist[leftmark] = alist[rightmark]
alist[rightmark] = temp
alist.insert(leftmark,pivotvalue)
print(alist,pivotvalue)
return leftmark
alist =
[5,1,4,2,8,10,3]
quickSorttengah(alist)
print(alist)
