BAB 11
SORTING I
Tujuan Instruksional Umum:
Mahasiswa memahami Jenis dari simple sorting dan algoritma serta implementasinya.
Tujuan Instruksional Khusus:
1. Mahasiswa memahami langkah – langkah dari Bubble Sort dan implementasinya dalam python
2. Mahasiswa memahami langkah – langkah dari Selection Sort dan implementasinya dalam python
3. Mahasiswa memahami langkah – langkah dari Insertion Sort dan implementasinya dalam python
Pokok Bahasan:
1. Algoritma & langkah – langkah Bubble Sort beserta programnya
2. Algoritma & langkah – langkah Selection Sort beserta programnya
3. Algoritma & langkah – langkah Insertion Sort beserta programnya
4. Latihan
11. 1 Sorting
Sorting / pengurutan adalah suatu proses untuk mengurutkan elemen-elemen berdasarkan key / kunci
tertentu. Tujuan dari sorting adalah agar mudah dan cepat dalam melakukan pencarian / searching.
Dalam kehidupan sehari-hari banyak sekali contoh yang dapat diberikan tentang sorting ini, misalnya
Absen Mahasiswa diurutkan / disort berdasarkan NIM , Daftar Dosen diurutkan berdasarkan Kode
Dosen. Urutan dalam sorting :
Bisa dilakukan secara menaik dari kecil ke besar ( Ascending ), yang berarti elemen dengan key
yang kecil akan berada diatas dari elemen dari key yang lebih besar atau
Bisa dilakukan secara menurun dari besar ke kecil ( Descending ), yang berarti elemen dengan
key besar akan berada di atas elemen dengan key yang lebih kecil.
Teknik melakukan sorting ini cukup banyak , yang dapat dikelompokkan dalam 3 (tiga) kelompok,
yaitu :
1. Simple Sort Techniques
Bubble Sort
Selection Sort
Insertion Sort
2. Advanced Sort Techniques
Heap Sort
Quick Sort
Merge Sort
11. 1.1 Bubble Sort
Bubble sort mungkin metode sorting paling populer yang digunakan dan sederhana. Proses
pengurutan dilakukan dengan membandingkan masing-masing nilai dalam suatu list secara
berpasangan, kemudian tukar nilai jika diperlukan, dan mengulanginya sampai akhir list secara
berurutan, sehingga tidak ada lagi nilai yang dapat ditukar.
Langkahnya seperti di bawah ini :
1. Bandingkan nilai pada data ke-1 dengan data ke-2.
2. Jika nilai data ke-1 lebih besar dari data ke-2 maka tukar posisinya.
3. Kemudian data yang lebih besar tersebut dibandingkan lagi dengan data ke-3.
4. Jika data ke-3 lebih kecil dari data ke-2 maka tukar posisinya, dan begitu seterusnya sampai
semua data yang ada jadi terurut.
Contoh : Apabila terdapat daftar angka 390, 205, 182, 45, 235, lakukan sorting dengan teknik Bubble
sort.
Hasil Putaran Pertama :
Hasil Putaran Kedua
Hasil Putaran Ketiga
Hasil Putaran Keempat
Fungsi untuk melakukan Exchange Sort adalah sebagai berikut :
def BubbleSort(val):
for angka in range(len(val)-1,0,-1):
for i in range(angka):
if val[i]>val[i+1]:
temp = val[i]
val[i] = val[i+1]
val[i+1] = temp
data = [23,7,32,99,4,15,11,20]
BubbleSort(data)
print(data)
12.1.2 Selection Sort
Konsep dasar dalam melakukan pengurutan dengan teknik selection sort adalah dengan memilih nilai
terkecil dari nilai-nilai yang akan diurutkan. Dibawah ini disajikan contoh secara bertahap mengenai
proses Selection Sort.
Contoh bila diketahui list angka 390, 205, 182, 45, 235 dilakukan sorting dengan teknik Selection
Sort.
Langkah-langkahnya adalah sebagai berikut :
1. Dari list angka ambil yang paling kecil, yaitu angka 45, tukar tempat antara 45 dengan elemen
yang berada pada tempat pertama, yaitu angka 390, berarti sudah ada 1 angka ( yaitu 45 ) yang
diurut, yang ditandai dengan garis bawahnya.
2. Dari list angka yang belum sort ( dari 205,182,,390,235 ) ambil angka yang paling kecil. Yaitu
angka 182. tukar tempat antara 182 dengan angka pada posisi kedua, yaitu 205. berarti sudah
ada 2 angka ( yaitu 45 dan 182 ) yang sudah urut.
3. dstnya
Fungsi untuk melakukan Selection Sort adalah sebagai berikut :
def SelectionSort(val):
for isi in range(len(val)-1,0,-1):
Max=0
for lokasi in range(1,isi+1):
if val[lokasi]>val[Max]:
Max = lokasi
temp = val[isi]
val[isi] = val[Max]
val[Max] = temp
data = [23,7,32,99,4,15,11,20]
SelectionSort(data)
print(data)
11.1.3 Insertion Sort
Insertion Sort dilakukan dengan menambahkan satu demi satu elemen ke dalam list elemen-elemen
yang telah terurut, sehingga data tepat sorted. Berikut diberikan ilustrasi secara bertahap dalam
melakukan Insertion Sort.
Contoh : untuk list angka yang sama seperti diatas, yaitu : 390, 205, 182, 45, 235 lakukan Sorting
dengan teknik Insertion Sort
Langkah pengerjaan Insertion Sort adalah sebagai berikut :
1. Ambil 2 angka yang paling bawah , yaitu 45 dan 235, lakukan pengurutan terhadap kedua
angka tersebut.
2. Tambahkan 1 angka lagi ke dalam list data yang sudah terurut, yang menjadi 182, 45, 235
lakukan pengurutan terhadap list data ini.
3. dstnya.
Fungsi untuk melakukan Insertion Sort adalah sebagai berikut :
def InsertionSort(val):
for index in range(1,len(val)):
nilaiaktif = val[index]
posisi = index
while posisi>0 and val[posisi-1]>nilaiaktif:
val[posisi]=val[posisi-1]
posisi = posisi-1
val[posisi]=nilaiaktif
Data = [23,7,32,99,4,15,11,20]
InsertionSort(Data)
print(Data)
Soal Latihan
1. untuk daftar angka berikut ini lakukanlah sorting (tunjukkan dan jelaskan langkah – langkahnya)
10, 90, 87, 5, 78, 3, 65, 45
a. insertion sort
b. selection sort
c. bubble sort
Latihan dirumah
1. untuk daftar angka berikut ini lakukanlah sorting (tunjukkan dan jelaskan langkah – langkahnya)
45, 21, 56, 77, 23, 90, 12, 73, 78
a. insertion sort
b. selection sort
c. bubble sort
Referensi
1. Daniel F Stubbs & Neil W. Webre (1985). Data Structures with Abstract Data Type and
Pascal. Brook/ Cole Publishing Company
2. Munir, Rinaldi & Lidya, Leoni (2003), Algoritma & Pemrograman Dalam Bahasa Pascal dan
C Buku 2, Penerbit Informatika Bandung.