() translation by (you can also view the original English article)
Jika kamu diberikan selembar kertas dengan daftar 1000 nama, dan kamu diminta untuk menemukan beberapa nama, namun daftar ini tidak dalam urutan apapun (misalnya urutan alfabetis), akan sangat membuat frustrasi bukan? Meletakkan daftar tersebut dalam urutan, walaupun memakan waktu, membuat menemukan nama jauh lebih mudah. Dengan demikian, memiliki sesuatu dalam urutan adalah keinginan alami kita sebagai manusia, dan mencari dalam daftar ini jelas sekali akan sedikit memakan usaha daripada mencari dalam daftar tidak berurutan.
Mari pindah ke dunia komputer, dimana daftar yang diperlukan dalam pencarian mungkin sangat besar, dan dimana kinerja mungkin terpengaruh bahkan dengan komputer yang cepat. Dalam kasus ini, memiliki algoritma pemilahan dan pencarian yang sesuai mungkin akan menjadi solusi untuk isu tersebut. Sementara pemilahan merupakan tentang meletakkan daftar nilai dalam urutan, pencarian adalah proses menemukan posisi sebuah nilai dalam daftar.
Untuk menjelaskan seberapa kritis isu ini, mari saya tunjukkan apa yang disebutkan oleh Donald Knuth, seorang ahli komputer Amerika, ahli matematika, professor emeritus di Stanford University dalam Seni Pemrograman Komputer, vol.3, Pemilahan dan Pencarian, halaman 3:
Perusahaan pembuat komputer di tahun 1960 memperkirakan bahwa lebih dari 25 persen waktu menjalankan komputer dihabiskan untuk pemilahan, ketika semua pelanggan mereka diperhitungkan. Nyatanya, ada banyak instalasi dimana tugas pemilahan bertanggungjawab untuk lebih dari separuh waktu computing. Dari statistik ini, kita mungkin menyimpulkan bahwa entah (i) ada banyak aplikasi pemilahan yang penting, atau (ii) banyak orang memilah ketika mereka seharusnya tidak perlu, atau (iii) algoritma pemilahan yang tidak efisien telah digunakan secara umum.
Dalam tutorial ini, saya akan secara khusus menjelaskan algoritma Pemilahan Seleksi (pemilahan) dan algoritma Pencarian Linier (pencarian).
Algoritma Pemilahan Seleksi
Algoritma Pemilahan Seleksi didasarkan pada seleksi suksesif nilai minima dan maksima. Bayangkan bahwa kita memiliki sebuah daftar yang ingin kita pilah dalam urutan meningkat (dari nilai terkecil ke terbesar). Elemen terkecil akan berada pada awal daftar, dan elemen terbesar akan berada pada akhir daftar.
Katakanlah daftar original tampak sebagai berikut:
| 7 | 5 | 3.5 | 4 | 3.1 |
Hal pertama yang kita lakukan adalah menemukan nilai minimum di dalam daftar, dimana dalam kasus ini adalah 3.1.
Setelah menemukan nilai minimum, tukar nilai minimum dengan elemen pertama dalam daftar. Yaitu, tukar 3.1 dengan 7. Sekarang daftar akan tampak sebagai berikut:
| 3.1 | 5 | 3.5 | 4 | 7 |
Sekarang setelah kita yakin bahwa elemen pertama berada dalam posisi yang benar pada daftar, kita mengulangi langkah di atas (menemukan nilai minimum) dimulai dari elemen kedua di dalam daftar. Kita dapat menemukan bahwa nilai minimum di dalam daftar (dimulai dari elemen kedua) adalah 3.5. Dengan demikian sekarang kita menukar 3.5 dengan 5. Daftar tersebut sekarang menjadi sebagai berikut:
| 3.1 | 3.5 | 5 | 4 | 7 |
Pada titik ini, kita yakin bahwa elemen pertama dan elemen kedua berada dalam posisi yang benar.
Sekarang, kita memeriksa nilai minimum dalam sisa daftar, yaitu dimulai dari elemen ketiga 5. Nilai minimum di dalam sisa daftar yaitu 4, dan kita sekarang menukarnya dengan 5. Sehingga daftar itu menjadi sebagai berikut:
| 3.1 | 3.5 | 4 | 5 | 7 |
Jadi sekarang kita yakin bahwa tiga elemen pertama berada dalam posisi yang benar, dan proses berlanjut dengan cara itu.
Mari lihat bagaimana algoritma Pemilahan Seleksi diterapkan dalam Python (berdasarkan Isai Damier):
1 |
def selectionSort(aList): |
2 |
for i in range(len(aList)): |
3 |
least = i |
4 |
for k in range(i+1, len(aList)): |
5 |
if aList[k] < aList[least]: |
6 |
least = k |
7 |
|
8 |
swap(aList, least, i) |
9 |
|
10 |
def swap(A, x, y): |
11 |
temp = A[x] |
12 |
A[x] = A[y] |
13 |
A[y] = temp |
Mari uji algoritma dengan menambahkan pernyataan di bawah pada akhir script di atas:
1 |
my_list = [5.76,4.7,25.3,4.6,32.4,55.3,52.3,7.6,7.3,86.7,43.5] |
2 |
selectionSort(my_list) |
3 |
print my_list |
Dalam kasus ini, kamu harusnya mendapatkan output di bawah:
[4.6, 4.7, 5.76, 7.3, 7.6, 25.3, 32.4, 43.5, 52.3, 55.3, 86.7]
Algoritma Pencarian Linier
Algoritma Pencarian Linier merupakan sebuah algoritma sederhana, dimana tiap item dalam daftar (dimulai dari item pertama) diinvestigasi hingga item yang diperlukan ditemukan, atau akhir daftar dicapai.
Algoritma Pencarian Linier diterapkan dalam Python sebagai berikut (berdasarkan pada Python School):
1 |
def linearSearch(item,my_list): |
2 |
found = False |
3 |
position = 0 |
4 |
while position < len(my_list) and not found: |
5 |
if my_list[position] == item: |
6 |
found = True |
7 |
position = position + 1 |
8 |
return found |
Mari uji codenya. Masukkan pernyataan di bawah pada akhir script Python di atas:
1 |
bag = ['book','pencil','pen','note book','sharpener','rubber'] |
2 |
item = input('What item do you want to check for in the bag?') |
3 |
itemFound = linearSearch(item,bag) |
4 |
if itemFound: |
5 |
print 'Yes, the item is in the bag' |
6 |
else: |
7 |
print 'Oops, your item seems not to be in the bag' |
Ketika kamu memasukkan input, pastikan itu berada di antara kutip tunggal atau ganda (yaitu 'pencil'). Jika kamu menginput 'pencil', misalnya, kamu harusnya mendapatkan output di bawah:
Yes, the item is in the bag
Dimana, jika kamu memasukkan 'ruler' sebagai input, kamu akan mendapatkan output di bawah:
Oops, your item seems not to be in the bag
Seperti yang dapat kita lihat, Python membuktikan dirinya lagi menjadi bahasa pemrograman yang membuatnya mudah untuk membuat konsep algoritmik program seperti yang kita lakukan di sini, yang berhubungan dengan algoritma pemilahan dan pencarian.
Penting untuk mencatat bahwa ada jenis lainnya dari algoritma pemilahan dan pencarian. Jika kamu ingin menggali lebih dalam tentang algoritma menggunakan Python, kamu dapat mengacu pada halaman ini.
