51
2.8 Teori Sorting
2.8.1 Bubble Sort
Algoritma
ini
diberi
nama
bubble
sort
karena
mengikuti
prinsip bubble
(gelembung
udara).
Karena
gelembung
udara lebih
ringan
daripada
air
maka
gelembung
udara
di
dalam
air
akan
naik ke
atas.
Ada
penulis
yang
menakan
algoritma
ini exchange sort
karena
pada
proses
pengurutan
selalu
dilakukan
pertukaran (exchange) dua data yang berdekatan.
Pengurutan
dalam algoritma
dibagi
dalam beberapa
putaran
(ronde,
round). Pada putaran pertama dicari data dengan nilai terkecil (jika
pengurutan secara ascending) dan
meletakkan data tersebut pada posisi
indeks
terkecil ([0]). Putaran kedua bertujuan mencari data nomor dua kecil dan
meletakannya pada [1] dan seterusnya. Banyaknya pengurutan adalah
sejumlah data dikurangi satu. Kompleksitas algoritma ini adalah O(n²).
2.8.2 Selection Sort
Algoritma ini membagi proses pengurutan menjadi putaran-putaran.
Pada
putaran
pertama
diseleksi
data dengan
nilai
terkecil
dan
data
ini
ditempatkan
pada
posisi
indeks
terkecil
(data[0]).
Pada
putaran
kedua
diseleksi
data
dengan
nilai
nomor
dua kecil untuk ditempatkan pada posisi
kedua
(data[1]).
Proses
seleksi
dlam satu
putaran
dilakukan
dengan
membandingkan
nilai
elemen
pada
dua indeks
pembanding.
Selama
proses
pembandingan
berlansung
perubahan hanya dilakukan terhadap indeks
pembanding. Pertukaran data secara fisik dilakukan pada akhir setiap putaran.
 |