Panduan Algoritma Python Quicksort

Jelajahi algoritma quicksort dengan Python. Pelajari pemilihan pivot, partisi, dan rekursi dalam contoh pengkodean interaktif ini.

Coba di Editor

Ikhtisar

Quicksort adalah algoritma pengurutan yang sangat cepat dan banyak digunakan. Seperti penggabungan, ini menggunakan pendekatan bagi-dan-taklukkan. Namun, quicksort mengurutkan elemen 'di tempat', menjadikannya hemat memori.

Algoritma ini bekerja dengan memilih elemen 'pivot' dari daftar. Kemudian elemen lainnya dipartisi menjadi dua sub-array: sub-array yang lebih kecil dari pivot dan sub-array yang lebih besar dari pivot. Proses ini diterapkan secara rekursif pada sub-array.

Meskipun Quicksort memiliki kompleksitas kasus terburuk sebesar O(n²), waktu proses rata-ratanya adalah O(n log n), dan biasanya kinerjanya mengungguli pengurutan gabungan dalam praktiknya karena lebih sedikit cache yang hilang dan tidak ada overhead dalam pembuatan array sementara.

Kode & Output Eksekusi

Skrip Penyortiran Cepat rekursif yang ringkas menggunakan pemahaman daftar agar mudah dibaca.

quicksort.py

Coba di Editor

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[len(arr) // 2]
        left = [x for x in arr if x < pivot]
        middle = [x for x in arr if x == pivot]
        right = [x for x in arr if x > pivot]
        return quicksort(left) + middle + quicksort(right)

# Test list
data = [12, 4, 5, 6, 7, 3, 1, 15]
print("Original List:", data)
sorted_data = quicksort(data)
print("Sorted List:  ", sorted_data)

Keluaran Terminal

Original List: [12, 4, 5, 6, 7, 3, 1, 15]
Sorted List:   [1, 3, 4, 5, 6, 7, 12, 15]

Implementasi Langkah demi Langkah

Rutinitas penyortiran sistem di mana jejak memori harus dijaga seminimal mungkin
Penyortiran tujuan umum dalam kerangka perpustakaan bahasa standar
Pengajaran akademis mekanika partisi dan pembagian dan penaklukan rekursif

Pertanyaan yang Sering Diajukan

Bagaimana kita dapat menghindari kompleksitas kasus terburuk O(n²) di Quicksort?

Kasus terburuk terjadi ketika pivot yang dipilih berulang kali merupakan elemen terkecil atau terbesar. Untuk mengurangi hal ini, pengembang menggunakan strategi seperti memilih pivot acak atau nilai "median dari tiga".

Apakah Quicksort stabil?

Tidak, Quicksort standar tidak stabil. Selama pemartisian, elemen ditukar dalam rentang yang panjang, yang dapat mengubah urutan relatif elemen duplikat.

Topik Terkait

Tutorial Algoritma Pengurutan Penggabungan Python

Pelajari cara mengimplementasikan Pengurutan Gabung dengan Python. Contoh interaktif langkah demi langkah dari strategi pengurutan Divide and Conquer.

Algoritma Penyortiran Python

Jelajahi algoritma pengurutan python. Visualisasikan pengurutan gelembung dan pengurutan gabungan secara asli dalam konteks IDE browser.

Algoritma Pencarian Biner Python

Cari daftar yang diurutkan dalam waktu logaritmik O(log n). Jalankan dan pahami pencarian biner dengan Python, termasuk logika langkah demi langkah, kasus edge, dan pengoptimalan.