Quick Sort merupakan suatu algoritma pengurutan data yang menggunakan teknik pemecahan data menjadi partisi-partisi, sehingga metode ini disebut juga dengan nama partition exchange sort. Untuk memulai irterasi pengurutan, pertama-tama sebuah elemen dipilih dari data, kemudian elemen-elemen data akan diurutkan diatur sedemikian rupa
Metode Quick sering disebut juga metode partisi (partition exchange sort). Metode ini mempunyai efektifitas yang tinggi dengan teknik menukarkan dua elemen dengan jarak yang cukup besar. Metode pengurutan quick sort dapat diimplementasikan dalam bentuk non rekursif dan rekursif.
Quick Sort merupakan salah satu algoritma pengurutan data yang menggunakan teknik membagi data menjadi partisi-partisi. Metode Quick Sort disebut juga dengan nama partition exchange sort.
Untuk memulai proses pengurutan, pertama-tama sebuah data dipilih dari kelompok data sebagai data pivot. Posisi data pivot dapat dicari dengan menggunakan rumus :
i = (indeks awal + indeks akhir) div 2
Kemudian elemen-elemen data akan diatur, sehingga nilai data pivot yang terletak di posisi ke I memenuhi kondisi sebagai berikut :
1. Semua data di posisi ke 1 sampai dengan ke I-1 lebih kecil atau sama dengan pivot atau data[i]<=pivot.
2. Semua data di posisi ke I+1 sampai dengan ke N lebih besar atau sama dengan pivot atau data[i]>=pivot.
Contoh Quick Sort mengunakan python :
def partition(arr,low,high):
i = ( low-1 )
pivot = arr[high]
for j in range(low , high):
if arr[j] <= pivot:
i = i+1
arr[i],arr[j] = arr[j],arr[i]
arr[i+1],arr[high] = arr[high],arr[i+1]
return ( i+1 )
def quickSort(arr,low,high):
if low < high:
pi = partition(arr,low,high)
quickSort(arr, low, pi-1)
quickSort(arr, pi+1, high)
arr = [10, 7, 8, 9, 1, 5]
n = len(arr)
quickSort(arr,0,n-1)
print ("Sorted array is:")
for i in range(n):
print ("%d" %arr[i]),
i = ( low-1 )
pivot = arr[high]
for j in range(low , high):
if arr[j] <= pivot:
i = i+1
arr[i],arr[j] = arr[j],arr[i]
arr[i+1],arr[high] = arr[high],arr[i+1]
return ( i+1 )
def quickSort(arr,low,high):
if low < high:
pi = partition(arr,low,high)
quickSort(arr, low, pi-1)
quickSort(arr, pi+1, high)
arr = [10, 7, 8, 9, 1, 5]
n = len(arr)
quickSort(arr,0,n-1)
print ("Sorted array is:")
for i in range(n):
print ("%d" %arr[i]),
EmoticonEmoticon