Sorting [Struktur Data]
Assalamualaikum Wr.Wb.
Selamat pagi teman – teman,
masih harus semangat yaa untuk terus belajar. Nahh disini kita lanjut ke materi
selanjutnya yaitu sorting atau pengurutan. Seperti biasa sebelumnya kita
harus tau apaasih definisinya?
Sorting terdapat 3 macam yaitu :
1.
Bubble Sort
2.
Selection Sort
3.
Insertion Sort
Kita akan bahas satu persatu
ya teman-teman, untuk yang pertama kita bahas bubble sort terlebih dahulu.
1. Bubble Sort
Bubble Sort adalah salah satu algoritma untuk sorting data atau kata lainnya mengurutkan data dari yang terkecil ke yang terbesar atau sebaliknya.
Kita bisa menyelesaikannya
dengan dua cara yaitu :
1. membandigkan sebuah nilai disebelahnya.
2. Swap : membandingkan dengan cara menukar, jika nilai lebih kecil.
Contoh :
Kita dapat mengurutkan data
tersebut dengan cara membandingkan nilai disebelahnya, apabila nilai di
sebelahnya lebih kecil maka kita melakukan swap (menukar). Kita dapat melakukan
looping sebanyak n-1 , dimana n adalah elemen.
Ø Fase 1
Pada loop 1 kita membandingkan indeks 0 dan angka disebelahnya, apakah 4 < 11? Jika iya maka kita akan menukar datanya (swap). Dan setelah ditukar terlihat hasilnya seperti disampingnya.
Selanjutnya kita lanjut ke loop 2, membandingkan indeks 1 dengan angka disebelahnya. Dan terlihat 70 > 13, maka tidak terjadi swap.
Lanjut pada loop 3 kita membandingkan indeks 2 dengan angka disebelahnya. Terlihat 20<70, maka terjadi swap, dan hasilnya terlihat pada tabel disampingnya.
Ø Fase 2
Pada fase 2 ini kita tetap melakukan loop, meskipun tidak ada data yang tertukar. Tujuannya hanya untuk mengecek kembali hingga tidak ada pertukaran lagi.
Soal Latihan!
Selesaikanlah
data berikut menggunakan cara Bubble Sort agar terurut!
Ø Fase 1
-
Pada loop1 kita
membandingkan indeks 0 dan indeks 1, terlhat 20<100, maka terjadi swap
-
Pada loop 2 kita
membandingkan indkes 1 dan indeks 2, terlihat 7<100, maka terjadi swap.
-
Pada loop 3 kita
membandingkan indkes 2 dan indeks 3, terlihat 50<100, maka terjadi swap.
-
Pada loop 4 kita
membandingkan indkes 3 dan indeks 4, terlihat 2<100, maka terjadi swap.
-
Pada loop 5 kita
membandingkan indkes 4 dan indeks 5, terlihat 33<100, maka terjadi swap.
-
Pada tabel
terakhir yaitu hasil.
Ø Fase 2
-
Pada loop1 kita
membandingkan indeks 0 dan indeks 1, terlhat 7<20, maka terjadi swap
-
Pada loop 2 kita
membandingkan indkes 1 dan indeks 2, terlihat 50>20, maka tidak terjadi swap.
-
Pada loop 3 kita
membandingkan indkes 2 dan indeks 3, terlihat 2<50, maka terjadi swap.
-
Pada loop 4 kita
membandingkan indkes 3 dan indeks 4, terlihat 33<50, maka terjadi swap.
-
Pada loop 5 kita
membandingkan indkes 4 dan indeks 5, terlihat 100>50, maka tidak terjadi swap.
-
Pada tabel
terakhir yaitu hasil.
Ø Fase 3
-
Pada loop1 kita
membandingkan indeks 0 dan indeks 1, terlhat 20>7, maka tidak terjadi swap
-
Pada loop 2 kita
membandingkan indkes 1 dan indeks 2, terlihat 2<20, maka terjadi swap.
-
Pada loop 3 kita
membandingkan indkes 2 dan indeks 3, terlihat 33>20, maka tidak terjadi swap.
-
Pada loop 4 kita
membandingkan indkes 3 dan indeks 4, terlihat 50>33, maka tidak terjadi swap.
-
Pada loop 5 kita
membandingkan indkes 4 dan indeks 5, terlihat 100>50, maka tidak
terjadi swap.
-
Pada tabel
terakhir yaitu hasil.
Ø Fase 4
-
Pada loop1 kita
membandingkan indeks 0 dan indeks 1, terlhat 2<7, maka terjadi swap
-
Pada loop 2 kita
membandingkan indkes 1 dan indeks 2, terlihat 20>7, maka tidak
terjadi swap.
-
Pada loop 3 kita
membandingkan indkes 2 dan indeks 3, terlihat 33>20, maka tidak terjadi swap.
-
Pada loop 4 kita
membandingkan indkes 3 dan indeks 4, terlihat 50>33, maka tidak terjadi swap.
-
Pada loop 5 kita
membandingkan indkes 4 dan indeks 5, terlihat 100>50, maka tidak terjadi swap.
-
Pada tabel
terakhir yaitu hasil.
Ø Fase 5
-
Pada loop 1 kita
membandingkan indeks 0 dan indeks 1, terlhat 7>2, maka tidak terjadi swap
-
Pada loop 2 kita
membandingkan indkes 1 dan indeks 2, terlihat 20>7, maka tidak
terjadi swap.
-
Pada loop 3 kita
membandingkan indkes 2 dan indeks 3, terlihat 33>20, maka tidak terjadi swap.
-
Pada loop 4 kita
membandingkan indkes 3 dan indeks 4, terlihat 50>33, maka tidak terjadi swap.
-
Pada loop 5 kita
membandingkan indkes 4 dan indeks 5, terlihat 100>50, maka tidak terjadi swap.
-
Pada tabel
terakhir yaitu hasil.
Kesimpulannya
Bubble sort termasuk algoritma yang paling mudah dipahami, namun pada bubble
sort ini meskipun pada fase pertama sudah urut tetap ada fase selanjutnya yaitu
fase dua yang bertujuan hanya untuk mengecek kembali hingga tidak ada
pertukaran lagi.
Kelebihan
Bubble Sort :
-
merupakan
pengurutan yang paling simpel.
-
Bubble Sort algoritmanya
sangat mudah untuk dimengerti.
-
Akan sangat
cocok untuk pengurutan sebuah data dengan bilangan yang di mulai dari yang
terkecil.
Kelemahan/Kekurangan
Bubble Sort :
-
Walaupun
sederhana Metode Bubble Sort ini Merupakan salah satu Metode pengurutan yang
tidak efisien.
-
Jumlah
perulangan akan tetap saja sama totalnya meskipun data yang asli telah
urut. Ini dikarenakan satu data akan
dibandingkan dengan data-data yang lain guna untuk menentukan posisi yang
tepat.
Selanjutnya
kita akan membahas materi sorting yang kedua yaitu Selection Sort.
1. Selection
Sort
Selection merupakan
salah satu algoritma pengurutan yang sederhana. Ide dasarnya adalah melakukan
beberapa kali pass untuk melakukan penyeleksian elemen struktur data.
Algoritma ini bekerja sebagai berikut:
1. Mencari nilai minimum atau maksimum
dalam sebuah list
2. Menukarkan nilai ini dengan elemen
pertama list
3. Mengulangi langkah di atas untuk
sisa list dengan dimulai pada posisi kedua.
4. Selection sort merupakan perbaikan dari metode bubble sort dengan
mengurangi jumlah perbandingan.
5. Selection sort merupakan metode pengurutan dengan mencari nilai data
terkecil dan nilai data terbesar dimulai dari data diposisi 0 hingga diposisi N-1.
Contoh :
·
Langkah pertama
kita mengambl angka 10 untuk dijadikan kunci, lalu kita membandingkan data
disebelahnya, terlihat angka 4 < 10
maka terjadi swap dan diletakkan pada posisi pertama.
Maka terlihat seperti ini :
·
Selanjutnya pada langkah kedua
kita
membandingkan dengan angka selanjutnya , dan terlihat 70>10 maka tidak
terjadi swap.
Maka data tetap dan tidak berubah seperti ini :
·
Dan langkah
terakhir kita membandingkan dengan angka terakhir yaitu 20, dan terlihat
20<20 dan terjadi swap.
Maka terlihat seperti ini :
Kesimpulannya, menyelesaikan
dengan menggunakan Selection Sort ini pemahamannya memang lebih mudah bubble
sort tetapi tidak memakan waktu. Dan tidak perlu mengecek kembali seperti
bubble sort. Untuk mempermudah selection sort ini mengambil satu angka terlebih
dahulu ijadikan kunci untuk membandingkan dengan angka disebelahnya.
Yang terahir kita bahas
tentang Insertion Sort.
1. Insertion
Sort
Insertion Sort adalah sebuah algoritma pengurutan
yang membandingkan dua elemen data pertama, mengurutkannya, kemudian mengecek
elemen data berikutnya satu persatu dan membandingkannya dengan elemen data
yang telah diurutkan. Karena algoritma ini bekerja dengan membandingkan
elemen-elemen data yang akan diurutkan,Agar lebih mudah dalam
memahaminya silahkan perhatikan contoh dibawah ini.
Contoh :
Kita dapat menyelesaikan soal
diatas dengan mengecek terlebih dahulu lalu menggeser angkanya.
Ø Proses 1
Kita mengambil angka 20 pada
indeks ke-1
-
lalu mengecek
apakah 20 lebih kecil dari 100? Jika iya maka kita akan meggeser data indeks
ke-0 ke posisi 1.
Maka sekarang angka 20 tergeser paada posisi indeks
ke-0 seperti ini :
Ø Proses 2
Lanjut kita mengambil angka 7
pada indeks ke-2.
-
Pertama kita
membandingkan apakah 7 kurang dari 100? Jika iya maka kita menggeser data ke-1
ke posisi 2.
-
Kedua kita
membandingkan angka 7 dengan indeks 0. Apakah 7 kurang dari 20? Jika iya kita
akan menggeser data ke-0 ke posisi 1.
Maka sekarang angka 7 tergeser paada posisi indeks
ke-0 Seperti ini :
Ø Proses 4
Lanjut kita mengambil angka 2
pada indeks ke-4 .
-
Pertama kita
membandingkan apakah 2 kurang dari 100? Jika iya maka kita menggeser data ke-3
ke posisi 4.
-
Kedua kita
membandingkan angka 2 dengan indeks 2. Apakah 2 lebih kecil dari 50? Jika iya
kita akan menggeser data ke-2 ke posisi 3.
-
Ketiga kita
membandingkan angka 2 dengan indeks 1. Apakah 2 lebih kecil dari 20? Jika iya
kita akan menggeser data ke-1 ke posisi 2.
-
Keempat kita
membandingkan angka 2 dengan indeks 0. Apakah 2 lebih kecil dari 7? Jika iya
kita akan menggeser data ke-0 ke posisi 1.
Maka sekarang angka 2 tergeser pada posisi indeks ke-0.
Dapat dilihat seperti ini :
Ø Proses 5
Lanjut kita mengambil angka
33 pada indeks ke-5 .
-
Pertama kita
membandingkan apakah 33 kurang dari 100? Jika iya maka kita menggeser data ke-4
ke posisi 5.
-
Kedua kita
membandingkan angka 33 dengan indeks 3. Apakah 33 lebih kecil dari 50? Jika iya
kita akan menggeser data ke-3 ke posisi 4.
-
Ketiga kita
membandingkan angka 33 dengan indeks 2. Apakah 33 lebih besar dari 20? Jika iya
kita tidak menggeser data karena data yang kita bandingkan lebih besar.
-
Keempat kita
membandingkan angka 33 dengan indeks 1. Apakah 33 lebih besar dari 7? Jika iya
kita tidak menggeser data karena data yang kita bandingkan lebih besar.
-
Kelima kita
membandingkan angka 33 dengan indeks 0. Apakah 33 lebih besar dari 2? Jika iya
kita tidak menggeser data karena data yang kita bandingkan lebih besar.
Maka sekarang angka 33 tergeser pada posisi indeks
ke-3.
Seperti ini :
Kesimpulan : menggunakan cara
Insertion Sort sederhana dalam penerapannya, jika data sudah terurut,maka cara ini lebih cepat dibanding bubble sort dan selection sort.. tetapi adapun kekurangannya yaitu banyaknya operasi yang diperlukan dalam mencari posisi juga membutuhkan waktu yang banyak jika data belum terurut.
Disini saya
mempunyai contoh program sort yang menggunakan metode Quick Sort. banyak data
yang digunakan adalah data random sebanyak 20 data.
Menurut saya merupakan algoritma pengurutan
data yang sangat cepat,sehingga cocok untuk mengurutkan data dalam jumlah
besar.
PENGURUTAN DATA
Data yang belum urut : 11,15,22,100,66,46,33,99,3,-2,-44,67,82,105,4,7,31,77,-45,1
Terimakasih sudah
menyimak,semoga dapat dipahami dan semoga bermanfaat untuk teman-teman yang
mengunjungi blog ini.
Wassalamualaikum Wr.Wb.
Komentar
Posting Komentar