insertion sort
DESCRIPTION
Salah satu metode pengurutan data. Oleh-oleh kuliah Perancangan dan Analisis Algoritma.TRANSCRIPT
Insertion Sort(Salah Satu Metode Pengurutan
Data)
Aku_dan_Hidupku
Metode Insertion sort
• Metode penyisipan (Insertion sort) bertujuan untuk mengurutkan elemen-elemen dalam array.
• Metode ini mengurutkan bilangan-bilangan yang sedang dibaca dan membandingkannya secara berulang dengan bilangan di sisi kirinya yang belum terbaca hingga terurut.
Aku_dan_Hidupku
Contoh PenggunaanTerdapat setumpuk kartu bernomor 2 hingga 8
Kartu-kartu ini akan diacak, dan kemudian diurutkan kembali dengan metode “insertion sort”Berikut adalah penjelasan mengenai metode “insertion sort”
Aku_dan_Hidupku
Algoritma Insertion Sort
InsertionSort (A, n) {
for j = 2 to n {
key = A[j]i = j-1while(i > 0) dan (A[i] > key){
A[i+1]= A[i]i = i -1
}A[i+1] = key
}}
Aku_dan_Hidupku
Pseudocode (inti kode)
InsertionSort (A, n) {
for j = 2 to n {
key = A[j]i = j-1while(i > 0) dan (A[i] >
key){A[i+1]= A[i]i = i -1
}A[i+1] = key
}}
Aku_dan_Hidupku
Algoritma Insertion Sort
Tempat menyimpan data = tiap kartu
Banyak data = banyak kartu
InsertionSort (A, n) {
for j = 2 to n {
key = A[j]i = j-1while(i > 0) dan (A[i] >
key){A[i+1]= A[i]i = i -1
}A[i+1] = key
}}
Aku_dan_Hidupku
Algoritma Insertion Sort
j 1 2 3 4 5 6 7
j adalah indeks array A
Kita akan mengurutkan kartu dari yang paling kiri
j = 1 sudah urut terhadap dirinya, jadi kita mulai dari j = 2
Key adalah variabel penyimpan sementara untuk kartu yang sedang akan diurutkan.
Key
InsertionSort (A, n) {
for j = 2 to n {
key = A[j]i = j-1while(i > 0) dan (A[i] >
key){A[i+1]= A[i]i = i -1
}A[i+1] = key
}}
Aku_dan_Hidupku
Algoritma Insertion Sort
j 1 2 3 4 5 6 7
Key
i adalah variabel penjelajah. i bermula dari nilai j-1.
InsertionSort (A, n) {
for j = 2 to n {
key = A[j]i = j-1while(i > 0) dan (A[i] >
key){A[i+1]= A[i]i = i -1
}A[i+1] = key
}}
Aku_dan_Hidupku
Algoritma Insertion Sort
j 1 2 3 4 5 6 7
i
Key
i menjelajah mulai dari j-1 hingga sebelum indeks ke 0.i akan tetap menjelajah bila A[i] lebih besar dari nilai key.
InsertionSort (A, n) {
for j = 2 to n {
key = A[j]i = j-1
while(i > 0) dan (A[i] > key){A[i+1]= A[i]i = i -1
}A[i+1] = key
}}
Aku_dan_Hidupku
Algoritma Insertion Sort
j 1 2 3 4 5 6 7
i
Key
Nilai A[i+1] diganti dengan nilai A[i]
InsertionSort (A, n) {
for j = 2 to n {
key = A[j]i = j-1while(i > 0) dan (A[i] >
key){A[i+1]= A[i]i = i -1
}A[i+1] = key
}}
Aku_dan_Hidupku
Algoritma Insertion Sort
j 1 2 3 4 5 6 7
i
A[i+1]
Key
i bergerak ke indeks sebelumnya
InsertionSort (A, n) {
for j = 2 to n {
key = A[j]i = j-1while(i > 0) dan (A[i] >
key){A[i+1]= A[i]i = i -1
}A[i+1] = key
}}
Aku_dan_Hidupku
Algoritma Insertion Sort
j 1 2 3 4 5 6 7
i
Key
Kembali ke ‘while’. Karena i bernilai 0, maka perulangan berhenti.
InsertionSort (A, n) {
for j = 2 to n {
key = A[j]i = j-1
while(i > 0) dan (A[i] > key){A[i+1]= A[i]i = i -1
}A[i+1] = key
}}
Aku_dan_Hidupku
Algoritma Insertion Sort
j 1 2 3 4 5 6 7
i
Key
Nilai A[i+1] diisi dengan nilai pada key.
InsertionSort (A, n) {
for j = 2 to n {
key = A[j]i = j-1while(i > 0) dan (A[i] >
key){A[i+1]= A[i]i = i -1
}A[i+1] = key
}}
Aku_dan_Hidupku
Algoritma Insertion Sort
j 1 2 3 4 5 6 7
i
InsertionSort (A, n) {
for j = 2 to n {
key = A[j]i = j-1while(i > 0) dan (A[i] >
key){A[i+1]= A[i]i = i -1
}A[i+1] = key
}}
Aku_dan_Hidupku
Algoritma Insertion Sort
j 1 2 3 4 5 6 7
A[1] dan A[2] sudah urut, kita lanjut ke j = 3
Key
Key adalah variabel penyimpan sementara untuk kartu yang sedang akan diurutkan.
InsertionSort (A, n) {
for j = 2 to n {
key = A[j]i = j-1while(i > 0) dan (A[i] >
key){A[i+1]= A[i]i = i -1
}A[i+1] = key
}}
Aku_dan_Hidupku
Algoritma Insertion Sort
j 1 2 3 4 5 6 7
Key
nilai awal i adalah j-1.
InsertionSort (A, n) {
for j = 2 to n {
key = A[j]i = j-1while(i > 0) dan (A[i] >
key){A[i+1]= A[i]i = i -1
}A[i+1] = key
}}
Aku_dan_Hidupku
Algoritma Insertion Sort
ij 1 2 3 4 5 6 7
Key
i menjelajah mulai dari j-1 hingga sebelum indeks ke 0.i akan tetap menjelajah bila A[i] lebih besar dari nilai key.
InsertionSort (A, n) {
for j = 2 to n {
key = A[j]i = j-1
while(i > 0) dan (A[i] > key){A[i+1]= A[i]i = i -1
}A[i+1] = key
}}
Aku_dan_Hidupku
Algoritma Insertion Sort
ij 1 2 3 4 5 6 7
Key
Nilai A[i+1] diganti dengan nilai A[i]
InsertionSort (A, n) {
for j = 2 to n {
key = A[j]i = j-1while(i > 0) dan (A[i] >
key){A[i+1]= A[i]i = i -1
}A[i+1] = key
}}
Aku_dan_Hidupku
Algoritma Insertion Sort
i
A[i+1]
j 1 2 3 4 5 6 7
i bergerak ke indeks sebelumnya
InsertionSort (A, n) {
for j = 2 to n {
key = A[j]i = j-1while(i > 0) dan (A[i] >
key){A[i+1]= A[i]i = i -1
}A[i+1] = key
}}
Aku_dan_Hidupku
Algoritma Insertion Sort
ij 1 2 3 4 5 6 7
Key
Kembali ke ‘while’. Nilai i sekarang adalah 1.
InsertionSort (A, n) {
for j = 2 to n {
key = A[j]i = j-1
while(i > 0) dan (A[i] > key){A[i+1]= A[i]i = i -1
}A[i+1] = key
}}
Aku_dan_Hidupku
Algoritma Insertion Sort
ij 1 2 3 4 5 6 7
Key
Ternyata A[i] < key. ‘while’ pun berhenti.
Nilai A[i+1] diisi dengan nilai pada key.
InsertionSort (A, n) {
for j = 2 to n {
key = A[j]i = j-1while(i > 0) dan (A[i] >
key){A[i+1]= A[i]i = i -1
}A[i+1] = key
}}
Aku_dan_Hidupku
Algoritma Insertion Sort
ij 1 2 3 4 5 6 7
Key
InsertionSort (A, n) {
for j = 2 to n {
key = A[j]i = j-1while(i > 0) dan (A[i] >
key){A[i+1]= A[i]i = i -1
}A[i+1] = key
}}
Aku_dan_Hidupku
Algoritma Insertion Sort
j 1 2 3 4 5 6 7
A[1] hingga A[3] sudah urut, kita lanjut ke j = 4
j 1 2 3 4 5 6 7
Key
Key adalah variabel penyimpan sementara untuk kartu yang sedang akan diurutkan.
InsertionSort (A, n) {
for j = 2 to n {
key = A[j]i = j-1while(i > 0) dan (A[i] >
key){A[i+1]= A[i]i = i -1
}A[i+1] = key
}}
Aku_dan_Hidupku
Algoritma Insertion Sort
j 1 2 3 4 5 6 7
Key
nilai awal i adalah j-1.
InsertionSort (A, n) {
for j = 2 to n {
key = A[j]i = j-1while(i > 0) dan (A[i] >
key){A[i+1]= A[i]i = i -1
}A[i+1] = key
}}
Aku_dan_Hidupku
Algoritma Insertion Sort
i
j 1 2 3 4 5 6 7
Key
i
i menjelajah mulai dari j-1 hingga sebelum indeks ke 0.i akan tetap menjelajah bila A[i] lebih besar dari nilai key.
InsertionSort (A, n) {
for j = 2 to n {
key = A[j]i = j-1
while(i > 0) dan (A[i] > key){A[i+1]= A[i]i = i -1
}A[i+1] = key
}}
Aku_dan_Hidupku
Algoritma Insertion Sort
j 1 2 3 4 5 6 7
Key
i
Nilai A[i+1] diganti dengan nilai A[i]
InsertionSort (A, n) {
for j = 2 to n {
key = A[j]i = j-1while(i > 0) dan (A[i] >
key){A[i+1]= A[i]i = i -1
}A[i+1] = key
}}
Aku_dan_Hidupku
Algoritma Insertion SortA[i+1]
i bergerak ke indeks sebelumnya
InsertionSort (A, n) {
for j = 2 to n {
key = A[j]i = j-1while(i > 0) dan (A[i] >
key){A[i+1]= A[i]i = i -1
}A[i+1] = key
}}
Aku_dan_Hidupku
Algoritma Insertion Sort
j 1 2 3 4 5 6 7
Key
i
Kembali ke ‘while’. Nilai i sekarang adalah 2.
InsertionSort (A, n) {
for j = 2 to n {
key = A[j]i = j-1
while(i > 0) dan (A[i] > key){A[i+1]= A[i]i = i -1
}A[i+1] = key
}}
Aku_dan_Hidupku
Algoritma Insertion Sort
Ternyata A[i] < key. ‘while’ pun berhenti.
j 1 2 3 4 5 6 7
Key
i
Nilai A[i+1] diisi dengan nilai pada key.
InsertionSort (A, n) {
for j = 2 to n {
key = A[j]i = j-1
while(i > 0) dan (A[i] > key){A[i+1]= A[i]i = i -1
}A[i+1] = key
}}
Aku_dan_Hidupku
Algoritma Insertion Sort
j 1 2 3 4 5 6 7
Key
i
InsertionSort (A, n) {
for j = 2 to n {
key = A[j]i = j-1while(i > 0) dan (A[i] >
key){A[i+1]= A[i]i = i -1
}A[i+1] = key
}}
Aku_dan_Hidupku
Algoritma Insertion Sort
j 1 2 3 4 5 6 7
A[1] hingga A[4] sudah urut, kita lanjut ke j = 5
j 1 2 3 4 5 6 7
Key
Key adalah variabel penyimpan sementara untuk kartu yang sedang akan diurutkan.
InsertionSort (A, n) {
for j = 2 to n {
key = A[j]i = j-1while(i > 0) dan (A[i] >
key){A[i+1]= A[i]i = i -1
}A[i+1] = key
}}
Aku_dan_Hidupku
Algoritma Insertion Sort
Key
nilai awal i adalah j-1.
InsertionSort (A, n) {
for j = 2 to n {
key = A[j]i = j-1while(i > 0) dan (A[i] >
key){A[i+1]= A[i]i = i -1
}A[i+1] = key
}}
Aku_dan_Hidupku
j 1 2 3 4 5 6 7
Algoritma Insertion Sort
i
Key
i menjelajah mulai dari j-1 hingga sebelum indeks ke 0.i akan tetap menjelajah bila A[i] lebih besar dari nilai key.
InsertionSort (A, n) {
for j = 2 to n {
key = A[j]i = j-1
while(i > 0) dan (A[i] > key){A[i+1]= A[i]i = i -1
}A[i+1] = key
}}
Aku_dan_Hidupku
Algoritma Insertion Sort
j 1 2 3 4 5 6 7
i
Key
Nilai A[i+1] diganti dengan nilai A[i]
InsertionSort (A, n) {
for j = 2 to n {
key = A[j]i = j-1while(i > 0) dan (A[i] >
key){A[i+1]= A[i]i = i -1
}A[i+1] = key
}}
Aku_dan_Hidupku
Algoritma Insertion Sort
j 1 2 3 4 5 6 7
i
Key
Nilai A[i+1] diganti dengan nilai A[i]
InsertionSort (A, n) {
for j = 2 to n {
key = A[j]i = j-1while(i > 0) dan (A[i] >
key){A[i+1]= A[i]i = i -1
}A[i+1] = key
}}
Aku_dan_Hidupku
Algoritma Insertion Sort
j 1 2 3 4 5 6 7
i
i bergerak ke indeks sebelumnya
InsertionSort (A, n) {
for j = 2 to n {
key = A[j]i = j-1while(i > 0) dan (A[i] >
key){A[i+1]= A[i]i = i -1
}A[i+1] = key
}}
Aku_dan_Hidupku
Algoritma Insertion Sort
i
Key
j 1 2 3 4 5 6 7
i bergerak ke indeks sebelumnya
InsertionSort (A, n) {
for j = 2 to n {
key = A[j]i = j-1while(i > 0) dan (A[i] >
key){A[i+1]= A[i]i = i -1
}A[i+1] = key
}}
Aku_dan_Hidupku
Algoritma Insertion Sort
i
Key
j 1 2 3 4 5 6 7
i bergerak ke indeks sebelumnya
InsertionSort (A, n) {
for j = 2 to n {
key = A[j]i = j-1while(i > 0) dan (A[i] >
key){A[i+1]= A[i]i = i -1
}A[i+1] = key
}}
Aku_dan_Hidupku
Algoritma Insertion Sort
i
Key
j 1 2 3 4 5 6 7
Lakukan hal yang sama untuk “7” dan “6”
InsertionSort (A, n) {
for j = 2 to n {
key = A[j]i = j-1
while(i > 0) dan (A[i] > key){A[i+1]= A[i]i = i -1
}A[i+1] = key
}}
Aku_dan_Hidupku
Algoritma Insertion Sort
Lakukan hal yang sama untuk “7” dan “6”
InsertionSort (A, n) {
for j = 2 to n {
key = A[j]i = j-1
while(i > 0) dan (A[i] > key){A[i+1]= A[i]i = i -1
}A[i+1] = key
}}
Aku_dan_Hidupku
Algoritma Insertion Sort
Nah, sudah terurut kan
Aku_dan_Hidupku
Algoritma Insertion Sort
Terima kasih sudah menyimak.