Algoritma seleksi: Perbedaan antara revisi

Jelajahi riwayat secara interaktif

← Revisi sebelumnya

Konten dihapus Konten ditambahkan

VisualTeks wiki

Revisi per 20 Juli 2017 13.59 sunting HsfBot (bicara \| kontrib) Bot 1.172.010 suntingan k Bot: penggantian teks otomatis (-algoritma, +algoritme) ← Revisi sebelumnya		Revisi terkini sejak 11 Januari 2022 04.53 sunting balikkan Hysocc (bicara \| kontrib) Pengguna terkonfirmasi, Peninjau 63.595 suntingan k Hysocc memindahkan halaman Algoritme seleksi ke Algoritma seleksi dengan menimpa pengalihan lama
(4 revisi perantara oleh 3 pengguna tidak ditampilkan)
Baris 2: == Seleksi dengan algoritme pengurutan == Satu algoritme seleksi yang sederhana dan digunakan secara luas adalah memanfaatkan [[algoritme pengurutan]] pada list, kemudian mengekstrak elemen ke-''k''. Ini adalah contoh [[reduksi (kompleksitas)\|reduksi]] satu permasalahan ke dalam permasalahan lain. Hal ini bermanfaat ketika kita ingin melakukan banyak seleksi terhadap sebuah list tunggal, ~~dimana~~di mana kasus ini membutuhkan hanya satu operasi pengurutan di awal yang membutuhkan waktu yang lama (''expensive''), yang diikuti oleh banyak operasi ekstraksi yang sebentar (''[http://www.top-cheap.com Cheap] {{Webarchive\|url=https://web.archive.org/web/20200923084727/https://www.top-cheap.com/ \|date=2020-09-23 }}''). Ketika kita hanya ingin melakukan satu seleksi, atau ketika kita ingin selalu mengubah list di antara tiap seleksi, metode ini dapat jadi lebih lama (''costly''), biasanya membutuhkan paling sedikit O(''n'' log ''n'') waktu, ~~dimana~~di mana ''n'' adalah panjang dari list. == Algoritme minimum/maksimum linear == Baris 8: '''function''' minimum(a[1..n]) minIndex := 1 minValue := a[1] '''for''' i '''from''' 2 '''to''' n '''if''' a[i] < minValue minIndex := i minValue := a[i] '''return''' minValue '''function''' maximum(a[1..n]) maxIndex := 1 maxValue := a[1] '''for''' i '''from''' 2 '''to''' n '''if''' a[i] > maxValue maxIndex := i maxValue := a[i] '''return''' maxValue Baris 45: Keuntungan lain dari metode ini adalah: * Setelah mengetahui lokasi elemen terkecil ke-''j'', waktu yang dibutuhkan hanya O(''j'' + (''k''-''j'')<sup>2</sup>) untuk menemukan elemen terkecil ke-''k'', atau hanya O(''k'') untuk ''k'' ≤ ''j''. * Metode ini dapat dilakukan dengan struktur data [[list berkait]], ~~dimana~~di mana list terbut berbasis partisi yang membutuhkan [[pengaksesan acak]]. {{algoritme-stub}}