Perbandingan
Penukaran
Partisi

  • Bagian yang dipartisi
  • Pivot
  • Dibandingkan
  • Ditukar
  • Di tempatnya

Info lebih lanjut tentang quicksort

Quicksort

Quicksort memilih pivot, memindahkan setiap nilai yang lebih kecil ke depannya dan nilai lainnya ke belakangnya, lalu mengurutkan kedua sisi dengan cara yang sama. Setelah setiap partisi, pivot berada di tempat akhirnya. Pilih cara memilih pivot, putar pengurutan dengan kecepatan berapa pun atau maju satu perbandingan setiap kali, dan lihat mengapa pivot yang buruk pada daftar terurut membuat quicksort lambat. Tekan Putar untuk melihat pengurutan, atau Langkah dan Mundur untuk maju satu perbandingan setiap kali. Geser penggeser langkah untuk melompat ke mana saja. Kotak-kotak menghitung perbandingan, penukaran, dan partisi. Pilih jumlah batang, urutan awalnya, atau ketik angka sendiri, serta cara memilih pivot. Saat papan dipilih, tombol panah melangkah, spasi memutar dan menjeda, serta Home dan End melompat ke awal dan akhir.

Cara kerjanya

  1. Pilih jumlah batang dan urutan awalnya: acak, hampir terurut, terbalik, atau dengan sedikit nilai unik. Atau ketik angka sendiri.
  2. Tekan Putar, atau gunakan Langkah dan Mundur untuk maju satu perbandingan setiap kali. Geser penggeser langkah untuk melompat ke mana saja.
  3. Pilih aturan pivot: nilai terakhir, nilai tengah, nilai acak, atau median dari tiga. Coba masing-masing pada daftar terurut.

Cara kerja quicksort

Pilih satu nilai dari bagian yang akan diurutkan sebagai pivot dan pindahkan ke ujung. Periksa nilai lainnya dari kiri ke kanan; setiap nilai yang lebih kecil dari pivot ditukar ke bagian kiri yang tumbuh dari awal. Lalu tukar pivot ke posisi tepat setelah bagian kiri. Semua nilai sebelumnya kini lebih kecil dan tidak ada yang lebih kecil setelahnya, jadi pivot sudah di tempat akhirnya. Urutkan bagian sebelum dan sesudahnya dengan cara yang sama, sampai setiap bagian hanya berisi satu nilai.

Mengapa pivot penting

Saat pivot jatuh di dekat tengah, setiap partisi membagi dua masalahnya, dan jumlah perbandingan tumbuh seperti n log n: untuk 40 nilai acak, sekitar 190. Saat pivot adalah nilai terkecil atau terbesar, satu sisi kosong dan sisi lain berisi semua nilai lainnya. Dengan nilai terakhir sebagai pivot, hal itu terjadi di setiap langkah pada daftar terurut atau terbalik, dan pengurutan butuh n(n − 1)/2 perbandingan, 780 untuk 40 nilai. Pivot acak atau median dari nilai pertama, tengah, dan terakhir menghindari hal itu dalam praktik.

Pertanyaan yang sering diajukan

Bagaimana cara kerja quicksort?

Quicksort memilih pivot, mempartisi daftar sehingga nilai yang lebih kecil berada sebelum pivot dan sisanya setelahnya, lalu mengurutkan kedua sisi dengan quicksort. Setelah setiap partisi, pivot sudah di tempat akhirnya.

Mengapa quicksort lambat pada daftar terurut?

Dengan nilai pertama atau terakhir sebagai pivot, daftar terurut selalu memberi nilai terkecil atau terbesar sebagai pivot. Satu sisi partisi pun kosong, sehingga setiap partisi hanya menyingkirkan satu nilai, dan pengurutan butuh n(n − 1)/2 perbandingan. Pivot acak atau median dari tiga mengatasinya dalam praktik.

Apakah quicksort lebih cepat dari merge sort?

Sering kali, dalam praktik: quicksort mengurutkan di tempat, tidak butuh buffer, dan loop dalamnya sangat sederhana. Rata-rata, perbandingannya sedikit lebih banyak dari merge sort, dan kasus terburuknya n², sedangkan merge sort selalu n log n. Pengurutan pustaka seperti introsort dimulai dengan quicksort dan beralih ke heap sort jika pembagiannya terlalu tidak seimbang.

Apakah quicksort stabil?

Tidak. Partisi menukar nilai dalam jarak jauh, sehingga nilai yang sama bisa berubah urutan.

Apakah angka saya dikirim ke mana pun?

Tidak. Pengurutan berjalan di browser Anda, dan pengaturan terakhir Anda tersimpan di penyimpanan lokal browser ini.

Siap mencobanya?

Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.

Ke Editor