Penjelasan Algoritma Quick Sort dan Contohnya

Quick Sort merupakan salah satu algoritma sorting yang populer yang menggunakan perbandingan nlogn untuk mengurutkan array n elemen dalam situasi tipikal.

Quick Sort bekerja dengan memilih elemen pivot dari array dan mempartisi elemen lain menjadi dua sub-array. Proses ini deterapkan secara rekursif ke sub-array hingga seluruh array diurutkan.

Berikut ini langkah-langkah cara kerja algoritma Quick Sort:

• Pilih elemen pivot dari array. Pivot dapat berupa elemen apa pun di dalam array, tetapi untuk lebih mudahnya anggap kita memilih elemen paling kanan sebagai pivot.
• Atur ulang elemen array sehingga semua elemen yang lebih kecil dari pivot dipindahkan ke kiri pivot, dan semua elemen yang lebih besar dari pivot dipindahkan ke kanan pivot. Pivot kemudian akan berada di posisi terutu terakhirnya.
• Terapkan dua langkah di atas secara rekursif ke sub-array yang dibuat di sisi kiri dan kanan pivot. Proses ini terus berlanjut sampai sub-array berisi satu elemen yang sudah diurutkan.
• Saat rekursif berhenti, makan sub-array yang sudah diurutkan akan digabungkan sehingga menghasilkan array yang terurut sepenuhnya.

Cara Kerja Quick Sort

Mari kita pahami bagaimana cara kerja dari algoritma Quick Sort. Sebagai contoh kita mempunyai array dengan value berikut.

array : [2,7,4,9,5]

Karena elemen 2, 4 kurang dari 5 (Pivot), mereka berada di sisi kiri pivot. Satu-satunya persyaratan adalah semua elemen harus lebih kecil dari pivot. Demikian pula, di sisi semua komponen harus lebih besar dari pivot.

Sehingga posisi pivot menjadi seperti berikut ini, terletak di antara elemen lebih kecil dan lebih besar dari pivot.

Selanjutnya terapkan langkah-langkah di atas secara rekursif ke sub-array kiri dan kanan

Sehingga didapat urutan dari array sebagai berikut ini.

Contoh Kode Implementasi Algoritma Quick Sort

Berikut ini merupakan kode yang dibuat dengan bahasa pemrograman python untuk implementasi algortima Qucik Sort.

def partition(array, left, right):
 
    # Pilih elemen paling kanan sebagai Pivot
    pivot = array[right]
 
    # Pointer for greater element
    i = left - 1

    # melakuakan perbandingan setiap elemen dengan pivot
    for j in range(left, right):
        if array[j] <= pivot:
 
            # jika element lebih kecil dari pivot
            # tukar dengan elemen yang lebih besar yang ditunjukkan oleh i
            i = i + 1

            (array[i], array[j]) = (array[j], array[i])
 
    # Tukar elemen dengan pivot
    # elemen yang lebih besar yang ditentukan oleh i
    (array[i + 1], array[right]) = (array[right], array[i + 1])
 
    return i + 1
 
 
# quicksort
def quicksort(array, left, right):
    if left < right:
 
        # Partisi array
        pivotIndex = partition(array, left, right)
 
        # Urutan untuk array kiri pivot
        quicksort(array, left, pivotIndex - 1)
 
        # Urutan untuk array kanan pivot
        quicksort(array, pivotIndex + 1, right)
 
 

if __name__ == '__main__':
    array = [2,7,4,9,5]
 
    # Memanggil Fungsi quicksort
    quicksort(array, 0, len(array) - 1)
    print('Hasil:')
    for i in array:
        print(i, end=" ")

Kesimpulan

Dari artikel diatas kita sudah mempelajari bagaimana alur dari algoritma Qucik Sort.

Perlu anda ketahui dalam pemilihan pivot dapat mempengaruhi efisiensi algoritma. Impelementasi di atas menggunakan elemen paling kanan sebagai pivot, namun ada strategi lain, seperti memilih pivot secara acak atau memilih median dari tiga elemen.

Semua tergantung keperluan sehingga dapat meningkatkan performa dalam suatu kasus tertentu.

Sekian untuk artikel ini semoga bermanfaat dan jika ada pertanyaan kalian dapat komentar di bawah ini.