22.50
Ariana
Salah satu algoritma sorting yang paling sederhana adalah insertion sort. Ide dari algoritma ini dapat dianalogikan seperti mengurutkan kartu. Mirip dengan cara orang mengurutkan kartu, selembar demi selembar kartu diambil dan disisipkan (insert) ke tempat yang seharusnya.
Algoritma insertion sort pada dasarnya memilah data yang akan diurutkan menjadi dua bagian, yang belum diurutkan (meja pertama) dan yang sudah diurutkan (meja kedua). Elemen pertama diambil dari bagian array yang belum diurutkan dan kemudian diletakkan sesuai posisinya pada bagian lain dari array yang telah diurutkan. Langkah ini dilakukan secara berulang hingga tidak ada lagi elemen yang tersisa pada bagian array yang belum diurutkan.
Prinsip dasar teknik insertion sort ini adalah secara beulang-ulang memasukkan nilai ke dalam posisinya atau tempatnya yang benar. Cara ini biasanya digunakan oleh pemain kartu pada saat mereka sedang menyusun kartu yang mereka pegang, yaitu dengan mengambil sebuah kartu yang belum pada tempatnya untuk kemudian disisipkan di tengah-tengah kartu lain yang merupakan tempat atau posisi yang benar kartu tersebut.
Penjelasan berikut ini menerangkan bagaimana algoritma insertion sort bekerja dalam pengurutan kartu. Mengurutkan satu set kartu dari kartu yang bernilai paling kecil hingga yang paling besar. Seluruh kartu diletakkan pada meja, sebutlah meja ini sebagai meja pertama, disusun dari kiri ke kanan dan atas ke bawah. Kemudian kita mempunyai meja yang lain, meja kedua, dimana kartu yang diurutkan akan diletakkan. Ambil kartu pertama yang terletak pada pojok kiri atas meja pertama dan letakkan pada meja kedua. Ambil kartu kedua dari meja pertama, bandingkan dengan kartu yang berada pada meja kedua, kemudian letakkan pada urutan yang sesuai setelah perbandingan. Proses tersebut akan berlangsung hingga seluruh kartu pada meja pertama telah diletakkan berurutan pada meja kedua.
Pengurutan dimulai dari data ke-2 sampai dengan data terakhir, jika ditemukan data yang lebih kecil, maka akan ditempatkan (diinsert) diposisi yang seharusnya.
Pada penyisipan elemen, maka elemen-elemen lain akan bergeser ke belakang.
Prinsip pengurutannya yaitu
1). Dimulai dari elemen 1 sampai elemen akhir
2). Jika elemen saat ini < elemen berikutnya, maka tidak dipindah
3). Jika elemen saat ini > elemen berikutnya
Contoh penjelasannya adalah sebagai berikut.
Diinputkan 5 buah data secara acak yaitu:
1 2 3 4 5
25 | 15 | 20 | 1 | 7 |
Proses:
1 2 3 4 5
25 | 15 | 20 | 1 | 7 |
Bandingkan A[1] dan A[2]
A[1] > A[2] maka tukar posisi A[1] dengan A[2]
1 2 3 4 5
15 | 25 | 20 | 1 | 7 |
Bandingkan A[1] dengan A[3]
A[1] < A[3] maka tidak terjadi tukar posisi
1 2 3 4 5
15 | 25 | 20 | 1 | 7 |
Bandingkan A[1] dengan A[4]
A[1] > A[4] maka tukar posisi A[1] dengan A[4]
1 2 3 4 5
1 | 25 | 20 | 15 | 7 |
Bandingkan A[1] dengan A[5]
A[1] < A[5] maka tidak terjadi tukar posisi
1 2 3 4 5
1 | 25 | 20 | 15 | 7 |
Bandingkan A[2] dengan A[3]
A[2] > A[3] maka tukar posisi A[2] dengan A[3]
1 2 3 4 5
1 | 20 | 25 | 15 | 7 |
Bandingkan A[2] dengan A[4]
A[2] > A[4] maka tukar posisi A[2] dengan A[4]
1 2 3 4 5
1 | 15 | 25 | 20 | 7 |
Bandingkan A[2] dengan A[5]
A[2] > A[5] maka tukar posisi A[2] dengan A[5]
1 2 3 4 5
1 | 7 | 25 | 20 | 15 |
Bandingkan A[3] dengan A[4]
A[3] > A[4] maka tukar posisi A[3] dengan A[4]
1 2 3 4 5
1 | 7 | 20 | 25 | 15 |
Bandingkan A[3] dengan A[5]
A[3] > A[5] maka tukar posisi A[3] dengan A[5]
1 2 3 4 5
1 | 7 | 15 | 25 | 20 |
Bandingkan A[4] dengan A[5]
A[4] > A[5] maka tukar posisi A[4] dengan A[5]
1 2 3 4 5
1 | 7 | 15 | 20 | 25 |
Pengurutan selesai
Ini dia sintaks / listing / Script Program Pengurutan Bilangan dengan metode Insertion Sort
Ini dia sintaks / listing / Script Program Pengurutan Bilangan dengan metode Insertion Sort
0 comments:
Posting Komentar