Algoritma seleksi: Perbedaan antara revisi
Konten dihapus Konten ditambahkan
k +interwiki dan kategori |
k Hysocc memindahkan halaman Algoritme seleksi ke Algoritma seleksi dengan menimpa pengalihan lama |
||
| (18 revisi perantara oleh 13 pengguna tidak ditampilkan) | |||
Baris 1:
Dalam [[ilmu komputer]], sebuah '''
== Seleksi dengan algoritme pengurutan ==
[[Kategori:Algoritma]]▼
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, 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, di mana ''n'' adalah panjang dari list.
== Algoritme minimum/maksimum linear ==
Kasus terburuk algoritme linear untuk menemukan minimum atau maksimum adalah sangat jelas; kita menyimpan dua peubah, satu mengacu ke indeks dari elemen minimum/maksimum yang didapatkan sementara, dan satu lagi menyimpan nilainya. Bersamaan dengan kita memindai list tersebut, kita perbarui kedua peubah tersebut jika kita menemukan sebuah elemen yang sesuai:
'''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
Sebagai catatan, kemungkinan akan terdapat banyak elemen minimum atau maksimum. Oleh karena pembandingan di atas adalah kaku (''strict''), algoritme tersebut menemukan elemen minimum dengan indeks yang minimum. Dengan memanfaatkan pembandingan tak kaku (''non-strict'') (≤ and ≥), kita akan menemukan elemen minimum dengan indeks maksimum.
Jika kita ingin menemukan kedua elemen minimum dan maksimuam bersamaan, perbaikan kecil dapat dilakukan dengan sepasang pembandingan, yaitu membandingkan elemen ganjil dan genap pada setiap pasang dan membandingkannya dengan elemen maksimum dan minimum.
== Algoritme seleksi umum nonlinear ==
Dengan memakai ide yang sama yang digunakan dalam algoritme minimum/maksimum, kita dapat mengkonstruksi sebuah algoritme sederhana tapi tidak efisien untuk menemukan item terkecil ke-''k'' atau terbesar ke-''k'', yang membutuhkan waktu O(''kn''), yang efektif untuk ''k'' yang kecil. Untuk memperolehnya, kita cukup menemukan nilai paling ekstrem dan memindahnya ke bagian awal sampai kita mendapatkan indeks yang diinginkan. Hal ini dapat dilihat sebagai [[pengurutan seleksi]] yang tidak lengkap. Berikut ini adalah algoritme berbasis minimum:
'''function''' select(a[1..n], k)
'''for''' i '''from''' 1 '''to''' k
minIndex = i
minValue = a[i]
for j = i+1 to n
if a[j] < minValue
minIndex = j
minValue = a[j]
swap a[i] and a[minIndex]
'''return''' a[k]
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]], di mana list terbut berbasis partisi yang membutuhkan [[pengaksesan acak]].
{{algoritme-stub}}
[[Kategori:Algoritme Pencarian]]
| |||