import numpy as np
Modul 4 Struktur Data: Array, Searching, Sorting
Kembali ke Struktur Data (dengan Python)
Pada pertemuan ini, kita akan membahas tentang operasi pada array, termasuk melihat beberapa algoritma-algoritma searching dan sorting pada array.
Operasi pada array
Sebagian besar pembahasan di praktikum kali ini bisa menggunakan list
biasa atau menggunakan array dari numpy
, terutama materi searching dan sorting. Namun, untuk materi operasi pada array, kita akan menggunakan array dari numpy
.
Traversal
Traversal pada array adalah “mengunjungi” elemen array satu per satu, dari awal sampai akhir. Tujuannya bisa untuk print saja, atau untuk menjumlahkan, atau yang lain. Apapun tujuannya, kalau itu melibatkan mengunjungi elemen array satu per satu, maka itu termasuk traversal.
Kita bisa mendeklarasikan suatu array dengan ukurannya saja, kemudian mengisi elemennya satu-per-satu.
= np.empty(5) A
print(A) # isinya masih garbage value
[0. 0.5 1. 1.5 2. ]
0] = 5
A[1] = 20
A[2] = -3
A[3] = 7
A[4] = -11 A[
print(A)
[ 5. 20. -3. 7. -11.]
Alternatifnya, kita bisa langsung saja menentukan elemen array sejak awal dibuat.
= np.array([5, 20, -3, 7, -11])
A print(A)
[ 5 20 -3 7 -11]
Berikut beberapa contoh traversal pada array.
for i in range(0, len(A)):
print(A[i])
5
20
-3
7
-11
sum = 0
for i in range(0, len(A)):
sum += A[i]
print(sum)
18
“Insertion”
Array memiliki ukuran yang tetap. Terkadang, ketika kita membuat array, belum tentu keseluruhan array itu langsung kita gunakan semua. Bisa jadi, di awal kita hanya menggunakan sebagian saja, namun nantinya akan kita gunakan seutuhnya. Sehingga, untuk mengelola data yang kita simpan di dalam array (sebagai struktur data), perlu ada mekanisme “memasukkan” dan “menghapus” data pada array.
(Pembahasan “insertion” dan “deletion” pada array mungkin agak aneh, tetapi sangat masuk akal untuk berbagai struktur data yang akan kita pelajari ke depannya, sehingga kita bahas terlebih dahulu untuk array.
Misalkan kita hanya mendeklarasikan suatu array. Belum ada data yang dimasukkan, sehingga kita bisa menyimpan variabel untuk “ukuran” array saat ini adalah nol.
= np.empty(5)
B = 0 B_size
Saat ini, array tersebut masih sepenuhnya berisi garbage value.
print(B)
[13. 20. 3. 7. 11.]
Kita bisa memasukkan elemen, misalnya 13, seperti berikut.
# insert 97
= 97
B[B_size]
# update data "ukuran" array,
# bertambah satu karena memasukkan satu elemen baru
+= 1 B_size
Dengan begitu, array menjadi seperti ini:
print(B)
[97. 20. 3. 7. 11.]
Perhatikan nilai variabel “ukuran” yang kita simpan:
print(B_size)
1
Saat ini, baru satu elemen yang kita masukkan ke dalam array. Sehingga, semua elemen lainnya itu tidak kita anggap, karena masih berupa garbage value (data sampah).
# insert -17
= -17
B[B_size] += 1 B_size
print(B)
[ 97. -17. 3. 7. 11.]
print(B_size)
2
# insert 43
= 43
B[B_size] += 1 B_size
print(B)
[ 97. -17. 43. 7. 11.]
print(B_size)
3
“Deletion”
Selain memasukkan data, kita juga bisa menghapus data. Kalau kita hanya ingin menghapus elemen “terakhir” (di data kita yaitu 43), maka kita tinggal “melupakan” elemen tersebut (sehingga statusnya menjadi garbage value) dengan mengurangi variabel “ukuran”:
# delete elemen "terakhir" (dari yang sudah kita isi)
= B_size - 1 B_size
print(B)
[ 97. -17. 43. 7. 11.]
print(B_size)
2
Memang array nya tidak berubah sama sekali, tapi ini masalah mindset (hehe). Tadinya, kita mengakui bahwa array berisi tiga buah data yang kita simpan, tetapi sekarang kita menganggap hanya berisi dua buah data. Sehingga, data ketiga yang tadi kita anggap data, itu sekarang menjadi garbage value yang bukan tanggung jawab kita.
Mari kita coba insert beberapa elemen lagi.
# insert 53, -98, 71
= 53
B[B_size] += 1
B_size
= -98
B[B_size] += 1
B_size
= 71
B[B_size] += 1 B_size
print(B)
[ 97. -17. 53. -98. 71.]
print(B_size)
5
Sekarang array sudah penuh. Bagaimana kalau misalnya kita ingin menghapus elemen pada indeks 2 (yaitu 53)? Kita perlu menggeser elemen indeks 3 menjadi indeks 2, kemudian indeks 4 menjadi indeks 3, sehingga “ukuran” array menjadi berkurang satu (elemen terakhir menjadi garbage value).
# delete elemen pada indeks 2
for i in range(2, len(B)-1):
= B[i+1]
B[i] = B_size - 1 B_size
print(B)
[ 97. -17. -98. 71. 71.]
print(B_size)
4
Jangan lupa, sekarang “ukuran” data kita hanya empat buah data, sehingga elemen terakhir di situ (yang kebetulan juga 71) adalah garbage value yang tidak kita anggap.
Searching
Algoritma searching, seperti namanya, adalah algoritma yang digunakan untuk mencari sesuatu dalam suatu list. Umumnya, algoritma semacam ini memiliki 2 input, yaitu suatu “key” atau elemen yang ingin dicari, dan suatu array atau list tempat pencarian key tersebut.
Terdapat 2 algoritma umum untuk searching, yaitu:
- Linear Search
- Binary Search
Linear Search
Linear search adalah algoritma searching di mana setiap elemen pada list dibandingkan satu per satu dengan key. Pada algoritma ini, kita akan mencoba untuk mencari keberadaan key pada list, serta index dari key tersebut (jika ada). Kalau key tidak ditemukan, kita bisa return -1 (memang sudah tradisi untuk menandakan ketiadaan elemen pada array, lagipula mustahil ada indeks -1 pada array).
def linear_search(arr, key):
for i in range(0, len(arr)):
if arr[i] == key:
return i
# sampai sini, berarti elemen tidak ditemukan
return -1
= [1, 5, 2, 3, 4, 8, 7, 6, 10, 9]
A 8) linear_search(A,
5
Binary Search
Binary search adalah algoritma searching dimana suatu list dicek apakah nilai tengahnya adalah key. Jika tidak, list dipecah dua dan searching dilanjut tergantung posisi key relatif dari nilai tengah tersebut (apakah lebih kecil atau lebih besar).
def binary_search(arr, key):
= 0
left_idx = len(A)
right_idx = False
found while (not found) and (left_idx <= right_idx):
= int( (left_idx + right_idx) / 2 )
center_idx if arr[center_idx] == key:
return center_idx
elif arr[center_idx] > key:
= center_idx - 1
right_idx else:
= center_idx + 1
left_idx # keluar loop berarti tidak ditemukan
return -1
= [2, 4, 6, 8, 10, 12, 14, 16, 18, 20]
A 14) binary_search(A,
6
Sorting
Terdapat 5 algoritma umum dalam sorting yang akan dijelaskan, yaitu:
- Bubble Sort
- Insertion Sort
- Selection Sort
- Quick Sort
- Merge Sort
Bubble Sort
Bubble sort adalah algoritma sorting yang cara kerjanya adalah dengan membandingkan elemen yang bersebelahan secara berurutan, lalu ditukar jika urutannya salah. Bubble sort melibatkan beberapa kali “pass”, yaitu beberapa kali melihat array dari awal sampai akhir.
Tentunya, bubble sort akan berhenti ketika array sudah terurut. Namun, bagaimana cara mengetahui apakah array sudah terurut? Salah satu caranya, di tiap pass, kita bisa menganggap array sudah terurut (ditandai dengan variabel boolean), lalu melakukan bubble sort, dan apabila ada elemen yang masih belum terurut, maka ketika ditukar, kita menandai array tersebut belum terurut. Sedangkan, apabila semua elemen sudah terurut (tidak terjadi pertukaran), variabel boolean tetap bernilai True
, sehingga array sudah terurut dan bubble sort sudah selesai. Untuk itu, digunakan while loop.
def bubble_sort_while(A):
= len(A)
n # di awal, array belum terurut
= False
selesai while (not selesai):
# di awal pass, asumsi array sudah terurut
= True
selesai for i in range(0, n-1):
# jika ada elemen yang belum terurut (perlu ditukar),
if A[i] > A[i+1]:
# tandai array belum terurut
= False
selesai # lalu tukar
+1] = A[i+1], A[i]
A[i], A[i# pass selesai
= [1, 5, 2, 3, 4, 8, 7, 6, 10, 9]
A
bubble_sort_while(A)print(A)
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Sebenarnya, banyaknya pass tidak akan melebihi \((n-1)\). Sehingga, daripada menggunakan while loop dan menandai array, kita bisa menggunakan for loop saja, untuk pass ke-i.
def bubble_sort_for(A):
= len(A)
n # Lakukan pass sebanyak (n-1) kali, yaitu pass ke-i, i=0, 1, ..., (n-2)
for i in range(n-1):
# Iterasi untuk tiap elemen ke-j, j=0, 1, ..., (n-2)
for j in range(n-1):
# Apabila elemen ke-j ternyata lebih besar daripada yang setelahnya,
if A[j] > A[j+1]:
# Maka tukar kedua elemen agar urutannya benar
+1] = A[j+1], A[j] A[j], A[j
= [1, 5, 2, 3, 4, 8, 7, 6, 10, 9]
A
bubble_sort_for(A)print(A)
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Insertion Sort
Cara kerja dari insertion sort adalah dengan membandingkan elemen baru dengan elemen sebelumnya dan ditempatkan di tempat yang sesuai. Insertion sort mulai dari indeks ke-1, yang mana elemen pada indeks tersebut dibandingkan dengan indeks sebelumnya. Jika posisinya tidak sesuai, maka elemen ditukar, dan seterusnya hingga posisinya sesuai. Lalu iterasi dilanjutkan dengan elemen indeks ke-2, hingga elemen telah diiterasi semua.
def insertion_sort(A):
= len(A)
n # Untuk tiap elemen di array... (kecuali elemen paling pertama, indeks 0)
for i in range(1, n):
= i
j # Selama elemen itu lebih kecil daripada elemen di sebelah kirinya,
# tukar (geser elemen itu ke sebelah kirinya) agar menjadi terurut
while A[j] < A[j-1]:
-1] = A[j-1], A[j]
A[j], A[j-= 1 # j berkurang karena bergeser ke kiri
j # Kalau elemen sudah di ujung kiri array,
# udah ga ada elemen di sebelah kirinya lagi, jadi keluar aja
if j == 0:
break
= [1, 5, 2, 3, 4, 8, 7, 6, 10, 9]
A insertion_sort(A)
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Selection Sort
Selection sort melakukan sorting dengan memasukkan nilai minimum dari suatu list. Jika diberikan suatu list \(A[0..(n-1)]\), maka algoritma mencari nilai minimum dari \(A[0..(n-1)]\), lalu ditukar dengan elemen \(A[0]\). Selanjutnya algoritma mencari nilai minimum dari \(A[1..(n-1)]\), lalu ditukar dengan elemen \(A[1]\), dan seterusnya.
def selection_sort(A):
= len(A)
n # Untuk tiap elemen ke-i, akan ditukarkan dengan elemen minimum yang
# ada di sebelah kanannya
for i in range(n-1):
# Asumsi awal: elemen yang sedang dilihat (elemen ke-i) adalah minimum
= i
min_idx = A[min_idx]
min_val
# Periksa masing-masing elemen selanjutnya...
for j in range(i+1, n):
# Kalau ternyata ketemu elemen yang lebih kecil lagi...
if A[j] < min_val:
# ... maka itu menjadi minimum yang terbaru
= A[j]
min_val = j
min_idx # Ketika keluar for loop, sudah diperoleh elemen minimum sesungguhnya
# Tukar elemen minimum dengan elemen ke-i
= A[min_idx], A[i] A[i], A[min_idx]
= [1, 5, 2, 3, 4, 8, 7, 6, 10, 9]
A selection_sort(A)
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Merge Sort
Merge sort melakukan sort dengan memecah list menjadi dua secara rekursif. Lalu sorting dilakukan dengan melakukan merge pada hasil pecahan list. Merge adalah proses pada dua list yang menyatukan dua list terurut menjadi satu list terurut. Merge dilakukan hingga list utuh kembali.
def merge_sort(A):
= len(A)
n # Seandainya hanya berisi satu elemen, tidak perlu dilakukan apa-apa
if len(A) > 1:
# indeks middle (elemen tengah)
= int(n/2)
m # Array A dipisah menjadi A1 (sebelah kiri) dan A2 (sebelah kanan)
= A[:m]
A1 = A[m:]
A2 # Lakukan merge sort pada keduanya
merge_sort(A1)
merge_sort(A2)
# Di bawah ini adalah proses penggabungan dari A1 dan A2 yang
# masing-masing sudah terurut
= 0 # indeks untuk A1
i = 0 # indeks untuk A2
j = 0 # indeks untuk array/list baru yang nantinya sudah terurut
k
# Loop selama kedua array masih punya elemen yang
# belum dimasukkan ke array/list baru
while i < len(A1) and j < len(A2):
# Kalau ternyata elemen pada A1 yang lebih kecil...
if A1[i] <= A2[j]:
# ... maka itulah yang dimasukkan ke array/list baru
= A1[i]
A[k] += 1 # lanjut ke elemen berikutnya untuk A1
i # Selain itu, berarti elemen pada A2 yang lebih kecil...
else:
# ... maka itulah yang dimasukkan
= A2[j]
A[k] += 1 # lanjut ke elemen berikutnya untuk A2
j # Ukuran array baru sudah bertambah satu
+= 1
k # Keluar loop, berarti salah satu array sudah habis
# Ada dua kemungkinan, yaitu A1 yang belum habis, atau A2 yang belum.
# Sehingga keduanya perlu "dihabiskan"
# Menghabiskan A1 kalau belum habis
while i < len(A1):
= A1[i]
A[k] += 1
i += 1
k
# Menghabiskan A2 kalau belum habis
while j < len(A2):
= A2[j]
A[k] += 1
j += 1 k
= [1, 5, 2, 3, 4, 8, 7, 6, 10, 9]
A
merge_sort(A)print(A)
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Quicksort
Secara keseluruhan, algoritma quicksort (yang bersifat rekursif) terdiri dari langkah berikut:
Apabila array kosong atau terdiri dari satu elemen, sorting selesai. Selain itu, lanjut ke langkah berikut.
Pilih salah satu elemen di array sebagai “pivot” (Bebas, yang penting konsisten. Biasanya elemen pertama. Kemungkinan lain: elemen tengah, elemen terakhir, dsb)
Lakukan “partisi”, yaitu proses yang membuat kondisi array menjadi seperti berikut:
-----------------------------------------------------------
| semua elemen yang | pivot | semua elemen yang |
| lebih kecil dari pivot | | lebih besar dari pivot |
-----------------------------------------------------------
- Lakukan quicksort pada sebelah kiri pivot dan pada sebelah kanan pivot.
Untuk proses “partisi”, ada dua cara utama untuk melakukannya (algoritma partisi), yaitu algoritma partisi Hoare dan algoritma partisi Lomuto.
Quicksort dengan partisi Hoare
def partition_hoare(A, left_idx, right_idx):
# Buat "pointer" low dan high (simpan indeksnya saja)
= left_idx
low_idx = right_idx
high_idx
# Diasumsikan array sudah terpartisi dengan baik (padahal belom hehe),
# - tugas low adalah memeriksa dari kiri (apakah benar sudah dipartisi),
# - tugas high adalah memeriksa dari kanan.
# Sudah terpartisi artinya:
# - sebelah kiri pivot adalah yang lebih kecil dari pivot
# - sebelah kanan pivot adalah yang lebih besar dari pivot
# Pilih indeks pivot, bebas, misal elemen paling pertama (paling kiri)
= left_idx
pivot_idx = A[pivot_idx]
pivot_val
# Loop selama low belum melewati high
# (syarat ini sangat penting, hingga diperiksa berkali-kali)
while low_idx <= high_idx:
# low lanjut ke kanan hingga menemukan elemen yang posisinya salah,
# yaitu elemen yang nilainya lebih besar dari pivot
while (low_idx <= high_idx) and not (A[low_idx] > pivot_val):
+= 1
low_idx
# high lanjut ke kiri hingga menemukan elemen yang posisinya salah,
# yaitu elemen yang nilainya lebih kecil dari pivot
while (low_idx <= high_idx) and not (A[high_idx] < pivot_val):
-= 1
high_idx
# low dan high sama-sama menunjuk pada elemen yang posisinya salah,
# keduanya akan menjadi benar kalau posisinya ditukar
if low_idx <= high_idx:
= A[high_idx], A[low_idx]
A[low_idx], A[high_idx]
# Apabila elemen pivot ternyata ikut ditukar,
# pastikan data posisinya (pivot_idx) di-update.
if pivot_idx == low_idx: # Apabila tadinya pivot di low,
= high_idx # maka sekarang pivot di high.
pivot_idx elif pivot_idx == high_idx: # Namun apabila tadinya pivot di high,
= low_idx # maka sekarang pivot di low.
pivot_idx
# Kalau sudah keluar loop, berarti low sudah melewati high;
# Sudah ketemu garis baginya, yaitu antara low dan high.
# Saat ini, sebelah kiri garis bagi sudah lebih kecil dari pivot,
# dan sebelah kanan garis bagi sudah lebih besar dari pivot.
# Sekarang kita tinggal menempatkan pivot pada garis bagi tersebut
# Tukar pivot dengan high kalau pivot di sebelah kiri high,
if pivot_idx <= high_idx:
= A[high_idx], A[pivot_idx]
A[pivot_idx], A[high_idx] = high_idx
pivot_idx
# atau tukar pivot dengan low kalau pivot di sebelah kanan low
else:
= A[low_idx], A[pivot_idx]
A[pivot_idx], A[low_idx] = low_idx
pivot_idx
# Partisi sudah selesai, return posisi pivot
# supaya jadi tahu di mana garis baginya
return pivot_idx
def quicksort_hoare(A, left_idx=None, right_idx=None):
# Kalau left_idx dan right_idx tidak diinput, otomatis menjadi None
# dan kalau begitu, berarti sebenarnya quicksort mau dilakukan pada
# keseluruhan array, sehingga ujung kiri adalah indeks 0 dan
# ujung kanan adalah indeks terakhir (n-1 di mana n adalah panjang array)
if left_idx == None:
= 0
left_idx if right_idx == None:
= len(A) - 1
right_idx
# Ada if statement untuk memastikan ujung kiri dan ujung kanan masih wajar.
if left_idx < right_idx:
= partition_hoare(A, left_idx, right_idx)
pivot_idx -1)
quicksort_hoare(A, left_idx, pivot_idx+1, right_idx)
quicksort_hoare(A, pivot_idx# Kalau sewaktu-waktu menjadi tidak wajar, berarti array kosong, berarti
# quicksort sudah selesai dan tidak perlu dilakukan apa-apa lagi
= [1, 5, 2, 3, 4, 8, 7, 6, 10, 9]
A
quicksort_hoare(A)print(A)
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Quicksort dengan partisi Lomuto
def partition_lomuto(A, left_idx, right_idx):
# Pilih elemen pivot, sepertinya untuk Lomuto harus elemen terakhir
= right_idx
pivot_idx = A[pivot_idx]
pivot_val
# Asumsi awal: semua elemen lebih besar dari nilai pivot,
# sehingga "separator" atau "garis pemisah" ada di ujung kiri,
# bahkan di sebelah kiri elemen pertama
= left_idx - 1
sep
# Periksa tiap elemen...
for j in range(left_idx, right_idx):
# Kalau ternyata ada elemen yang tidak lebih besar dari pivot...
if A[j] <= pivot_val:
# Majukan garis pemisah...
= sep + 1
sep # Lalu tukar elemen itu (yang seharusnya di sebelah kiri pivot),
# agar menjadi di (sebelah kiri) garis pemisah
= A[j], A[sep]
A[sep], A[j] # Nantinya, pivot akan diletakkan di posisi indeks sep+1.
# Data indeks "sep" menunjuk pada indeks terakhir yang
# elemennya lebih kecil dari pivot.
# Keluar for loop, sekarang semua elemen sudah diperiksa,
# indeks sep menunjuk pada elemen terakhir yang lebih kecil dari pivot.
# Maka, pivot bisa diletakkan di posisi sep+1.
# Tukar elemen pivot dengan elemen apapun yang sedang di sep+1.
+1], A[pivot_idx] = A[pivot_idx], A[sep+1]
A[sep# Sekarang, pivot ada di sep+1
= sep+1
pivot_idx
# Partisi sudah selesai, return posisi pivot
# supaya jadi tahu di mana garis baginya
return pivot_idx
def quicksort_lomuto(A, left_idx=None, right_idx=None):
if left_idx == None:
= 0
left_idx if right_idx == None:
= len(A) - 1
right_idx
if left_idx < right_idx:
= partition_lomuto(A, left_idx, right_idx)
pivot_idx - 1)
quicksort_lomuto(A, left_idx, pivot_idx + 1, right_idx) quicksort_lomuto(A, pivot_idx
= [1, 5, 2, 3, 4, 8, 7, 6, 10, 9]
A
quicksort_lomuto(A)print(A)
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Perhatikan bahwa, meskipun algoritma partisi Hoare dan partisi Lomuto sangat berbeda, ketika di fungsi quicksort
(quicksort_hoare
dan quicksort_lomuto
), kodenya sama, hanya berbeda di fungsi partisi yang digunakan.