Quick Sort: Pengertian, Cara Kerja, dan Implementasinya

Pengurutan data secara efisien adalah tahapan krusial dalam pemrograman dan pengolahan data. Quick sort adalah salah satu metode yang sering kali digunakan untuk mengurutkan data.

Selain itu, quick sort adalah algoritma yang sering kali digunakan oleh para developer dan ahli IT. Ini karena quick sort cepat dan efisien. Untuk lebih lengkapnya, baca artikel ini sampai habis ya!

Lebih detailnya, quick sort bekerja dengan memilih sebuah elemen dari array sebagai pivot. Setelah itu, quick sort mengatur ulang elemen-elemen lain dalam array. Dengan begitu, semua elemen dengan nilai lebih kecil dari pivot berada sebelumnya, sebaliknya juga sama.

Setelah pemisahan tersebut, pivot berada pada posisi akhirnya. Kemudian, proses ini akan diulangi secara rekursif untuk sub-array di kiri dan kanan pivot. Ini dilakukan sampai seluruh array menjadi terurut.

Lalu, elemen dengan nilai lebih besar berada di sebelah kanannya. Langkah tersebut menghasilkan dua sub-array yang belum terurut di kedua sisi pivot. Pivot sendiri berada di posisi akhir yang benar sesuai urutan. 

Proses partisi ini dilakukan dengan menggunakan dua pointer atau indeks yang bergerak melintasi array dari kedua ujungnya. Ini dilakukan secara bertahap untuk menukar elemen guna memastikan pemisahan yang benar relatif terhadap pivot.

Baca Juga:  Contoh Program Array C++ Seperti Apa?

Rekursi ini berlanjut sampai sub-array yang ditangani hanya berisi satu elemen atau tidak ada elemen sama sekali. Artinya, sub-array tersebut sudah terurut dan tidak memerlukan pemisahan lebih lanjut.

Hal tersebut adalah esensi dari pendekatan divide and conquer. Rekursi berhenti ketika sampai pada kasus dasar. Ini adalah saat ketika sub-array yang ditangani tidak dapat dibagi lagi karena hanya berisi satu elemen atau kosong.

• Efisiensi Tinggi: Untuk data set besar, quick sort menunjukkan performa yang sangat baik dengan kompleksitas waktu rata-rata lebih cepat.

• Pengurutan In-Place: Quick sort melakukan pengurutan langsung pada array input tanpa memerlukan ruang tambahan yang signifikan. Ini membuatnya sangat efisien dari segi penggunaan memori.

• Cache-Friendly: Quick sort mengurutkan data in-place dan bekerja pada sub-array yang lebih kecil. Oleh sebab itu, metode ini cenderung memiliki performa yang baik dengan cache modern.

• Mudah Diimplementasikan: Quick sort relatif mudah untuk diimplementasikan dan dapat diadaptasi untuk berbagai jenis data dan fungsi perbandingan.

• Scalable: Quick sort dapat menangani data set besar dengan efisien. Ini membuatnya cocok untuk aplikasi yang memproses jumlah data besar.

• Tidak Stabil: Quick sort bukan algoritma pengurutan yang stabil. Artinya, urutan relatif dari elemen-elemen yang sama dapat berubah setelah pengurutan. Ini mungkin menjadi masalah dalam beberapa kasus penggunaan khusus di mana kestabilan diperlukan.

• Sensitif terhadap Pemilihan Pivot: Efisiensi quick sort sangat bergantung pada cara pemilihan pivot. Pemilihan pivot yang tidak optimal dapat mengurangi efisiensi pengurutan.

• Overhead Rekursi: Meskipun rekursi memungkinkan struktur kode yang bersih dan elegan, ini juga menimbulkan overhead tambahan. Dalam kasus ekstrim dengan data set sangat besar dan kedalaman rekursi tinggi, ini dapat menyebabkan stack overflow.

Baca Juga: 10 Fungsi yang Mungkin Diperlukan dalam Proyek Typescript Kamu

def quick_sort(arr):

    # Basis rekursi: array dengan 0 atau 1 elemen sudah terurut

    if len(arr) <= 1:

        return arr

    else:

        # Memilih pivot, di sini kita memilih elemen terakhir sebagai pivot

        pivot = arr[-1]

        left = []  # Elemen lebih kecil dari pivot

        right = [] # Elemen lebih besar dari pivot

        for i in range(len(arr) - 1): # Mengabaikan elemen pivot saat ini

            if arr[i] < pivot:

                left.append(arr[i])

            else:

                right.append(arr[i])

        # Menggabungkan hasil rekursif dari sub-array kiri, pivot, dan sub-array kanan

        return quick_sort(left) + [pivot] + quick_sort(right)

# Contoh penggunaan

arr = [10, 7, 8, 9, 1, 5]

sorted_arr = quick_sort(arr)

print("Array terurut:", sorted_arr)

Lalu, output dari kode tersebut adalah:

[1, 5, 7, 8, 9, 10]

Demikian penjelasan lengkap mengenai quick sort mulai dari pengertian hingga implementasinya. Penjelasan tersebut menunjukkan bahwa quick sort adalah salah satu algoritma pengurutan yang cukup efisien untuk digunakan dalam data set besar.

Terkait dengan data, MinDi ada rekomendasi program buat kamu yang tertarik mendalaminya. Program rekomendasi MinDi adalah Bootcamp Data Science Dibimbing.id. 

Program ini cocok buat kamu yang mau belajar segala hal terkait data science mulai dari nol hingga mahir. Pembelajarannya lengkap dan didasari oleh silabus beginner-friendly. 

Kamu bisa belajar teori, konsep dasar, aplikasi data, tools, hingga praktik dengan real-case project. Intinya, kamu bakal dibimbing sampai jadi! Tertarik? Yuk, segera daftar dan mulai karirmu di data science bareng Dibimbing.id!