Metode insertion sort
ini akan lebih mudah dipahami dengan secara langsung mempelajari setiap
tahapnya.
Tahap 1 :
Dimulai dari A[1]
Simpan nilai A[1]
pada sebuah variabel (misal x)
Geser masing-masing
satu langkah ke kanan semua nilai yang berada pada kiri A[1] satu per
satu jika nilai tersebut lebih besar dari x
Insert (sisipkan) x
di bekas tempat nilai yang terakhir digeser.
Tahap 2 :
Simpan nilai A[2]
pada variabel x.
Geser masing-masing
satu langkah ke kanan semua nilai yang berada pada kiri A[2] satu per
satu jika nilai tersebut lebih besar dari x
Insert (sisipkan) x
di bekas tempat nilai yang terakhir digeser.
Tahap berikutnya dan
seterusnya hingga terakhir tahap ke N-1 (untuk array dengan N elemen).
Instruksi pergeseran
ke kanan adalah A[i]=A[i - 1], sehingga nilai A[i] akan hilang (ditimpa oleh
nilai A[i-1] oleh karena itu pada awal tahap A[i] disimpan pada sebuah
variabel.
Sudah ada array satu dimensi sudah ada
isinya, diilustrasikan sebagai berikut :
|
0
|
1
|
2
|
3
|
4
|
5
|
|
|
A[6]
|
17
|
11
|
8
|
25
|
3
|
15
|
Akan dirurutkan ascending sehingga
dihasilkan urutan data seperti berikut:
|
0
|
1
|
2
|
3
|
4
|
5
|
|
|
A[6]
|
3
|
8
|
11
|
15
|
17
|
25
|
Maka proses pengurutan tahap demi tahap
dengan menggunakan metode insertion sort adalah sebagai berikut :
Tahap 1 (dimulai dari A[1])
|
17
|
11
|
8
|
25
|
3
|
15
|
x=A[1]= 11
|
|
17
|
17
|
8
|
25
|
3
|
15
|
Nilai di kiri A[1] adalah A[0],
A[0]>x, geser ke kanan
|
|
11
|
17
|
8
|
25
|
3
|
15
|
Tidak ada lagi nilai di kiri, jadi
insert x ke A[0], A[0]=x
|
Tahap 2 (dimulai dari
A[2])
|
11
|
17
|
8
|
25
|
3
|
15
|
x=A[2]= 8
|
|
11
|
17
|
17
|
25
|
3
|
15
|
Nilai di kiri A[2] adalah A[1],
A[1]>x, geser ke kanan
|
|
11
|
11
|
17
|
25
|
3
|
15
|
Nilai di kiri A[1] adalah A[0],
A[0]>x, geser ke kanan
|
|
8
|
17
|
8
|
25
|
3
|
15
|
Tidak ada lagi nilai di kiri, jadi
insert x ke A[0], A[0]=x
|
Tahap 3 (dimulai dari
A[3])
|
8
|
11
|
17
|
25
|
3
|
15
|
x=A[3]= 25
|
|
8
|
11
|
17
|
25
|
3
|
15
|
Nilai di kiri A[3] adalah A[2],
A[2]<x
|
A[2] tidak lebih besar dari x maka
tidak perlu melanjutkan ke nilai kirinya lebih lanjut karena sudah pasti tidak
lebih besar dari x juga.
Jadi proses insert x pada A[3], A[3]=x
Tahap 4 (dimulai dari
A[4])
|
8
|
11
|
17
|
25
|
3
|
15
|
x=A[4]= 3
|
|
8
|
11
|
17
|
25
|
25
|
15
|
Nilai di kiri A[4] adalah A[3],
A[3]>x, geser ke kanan
|
|
8
|
11
|
17
|
17
|
25
|
15
|
Nilai di kiri A[3] adalah A[2],
A[2]>x, geser ke kanan
|
|
8
|
11
|
11
|
17
|
25
|
15
|
Nilai di kiri A[2] adalah A[1],
A[1]>x, geser ke kanan
|
|
8
|
8
|
11
|
17
|
25
|
15
|
Nilai di kiri A[1] adalah A[0],
A[0]>x, geser ke kanan
|
|
3
|
8
|
11
|
17
|
25
|
15
|
Tidak ada lagi nilai di kiri, jadi
insert x ke A[0], A[0]=x
|
Tahap 5 (dimulai dari
A[5])
|
3
|
8
|
11
|
17
|
25
|
15
|
x=A[5]= 15
|
|
3
|
8
|
11
|
17
|
25
|
25
|
Nilai di kiri A[5] adalah A[4],
A[4]>x, geser ke kanan
|
|
3
|
8
|
11
|
17
|
17
|
25
|
Nilai di kiri A[4] adalah A[3],
A[3]>x, geser ke kanan
|
|
3
|
8
|
11
|
15
|
17
|
25
|
Nilai di kiri A[3] adalah A[2],
A[2]<x
|
A[2] tidak lebih besar dari x maka
tidak perlu melanjutkan ke nilai kirinya lebih lanjut karena sudah pasti tidak
lebih besar dari x juga.
Proses pergeseran terakhir pada A[3],
maka proses insert x pada A[3], A[3]=x
Flowchart Insertion
Tidak ada komentar:
Posting Komentar