Metode Penyisipan Langsung
Proses pengurutan dengan metode penyisipan
langsung dapat dijelaskan sebagai berikut :
Data dicek satu per satu mulai dari
yang kedua sampai dengan yang terakhir.Apabila ditemukan data yang lebih kecil
daripada data sebelumnya, maka data tersebut disisipkan pada posisi yang
sesuai.Akan lebih mudah apabila membayangkan pengurutan kartu.Pertama-tama anda
meletakkan kartu-kartu tersebut di atas meja, kemudian melihatnya dari kiri ke
kanan.Apabila kartu di sebelah kanan lebih kecil daripada kartu di sebelah
kiri, maka ambil kartu tersebut dan sisipkan di tempat yang sesuai.
Algoritma
penyisipan langsung dapat dituliskan sebagai berikut :
i←1 selama (i < N) kerjakan baris 3
sampai dengan 9
x←Data[i]
j←i – 1 selama (x < Data[j]) kerjakan
baris 6 dan 7
Data[j
+ 1] ←Data[j]
j←j – 1
Data[j+1]
←x
i←i + 1
Untuk
lebih memperjelas langkah-langkah algoritma penyisipan langsung dapat
dilihat
pada tabel. Proses pengurutan pada tabel dapat dijelaskan sebagai berikut:
·
Pada saat i=1,
x sama dengan Data[1] = 35 dan j=0. Karena Data[0] = 12 dan 35 > 12 maka
proses dilanjutkan untuk i=2.
·
Pada saat i=2,
x = Data[2] = 9 dan j=1. Karena Data[1] = 35 dan 9 < 35, maka dilakukan
pergeseran sampai ditemukan data yang lebih kecil dari 9. Hasil pergeseran ini,
Data[1] = 12 dan Data[2] = 35 sedangkan Data[0] = x = 9.
·
Pada saat i=3,
x = Data[3] = 11 dan j=3. Karena Data[2] = 35 dan 11 < 35, maka dilakukan
pergeseran sampai ditemukan data yang lebih kecil dari 11. Hasil pergeseran
ini, Data[2] = 12 dan Data[3] = 35 sedangkan Data[1] = x = 11.
·
Dan
seterusnya.
Iterasi
|
Data[0]
|
Data[1]
|
Data[2]
|
Data[3]
|
Data[4]
|
Data[5]
|
Data[6]
|
Data[7]
|
Data[8]
|
Data[9]
|
Awal
|
12
|
35
|
9
|
11
|
3
|
17
|
23
|
15
|
31
|
20
|
I=1
|
12
|
35
|
9
|
11
|
3
|
17
|
23
|
15
|
31
|
20
|
I=2
|
12
|
35
|
9
|
11
|
3
|
17
|
23
|
15
|
31
|
20
|
I=3
|
9
|
12
|
35
|
11
|
3
|
17
|
23
|
15
|
31
|
20
|
I=4
|
9
|
11
|
12
|
35
|
3
|
17
|
23
|
15
|
31
|
20
|
I=5
|
3
|
9
|
11
|
12
|
35
|
17
|
23
|
15
|
31
|
20
|
I=6
|
3
|
9
|
11
|
12
|
17
|
35
|
23
|
15
|
31
|
20
|
I=7
|
3
|
9
|
11
|
12
|
17
|
23
|
35
|
15
|
31
|
20
|
I=8
|
3
|
9
|
11
|
12
|
15
|
17
|
23
|
35
|
31
|
20
|
I=9
|
3
|
9
|
11
|
12
|
15
|
17
|
23
|
31
|
35
|
20
|
Akhir
|
3
|
9
|
11
|
12
|
15
|
17
|
20
|
23
|
31
|
35
|
Di bawah ini merupakan prosedur yang menggunakan
metode penyisipan langsung.
void StraighInsertSort()
{
int i, j,
x;
for(i=1;
i<Max; i++){
x =
Data[i];
j = i - 1;
while (x
< Data[j]){
Data[j+1] =
Data[j];
j--;
}
Data[j+1] =
x;
}
}
Dari algoritma
dan prosedur diatas, jumlah perbandingan (=C) minimum, rata-rata
dan maksimum
pada metode penyisipan langsung adalah
Cmin = N –
1
Crata-rata = (N2
+ N + 2) / 4
Cmax = (N2
+ N – 2) / 2
Jumlah
perbandingan minimum terjadi jika data sudah dalam keadaan urut, sebaliknya
jumlah perbandingan maksimum terjadi jika data dalam keadaan urut terbalik.
Cara menghitung Cmin
adalah dengan melihat kalang paling luar yaitu i, pengulangan ini dimulai
dari 1 sampai dengan N-1 atau sama dengan N-1 Cara menghitung Cmax dengan
menganggap selalu terjadi pergeseran. Kalang dalam (while) diatas akan
melakukan pengulangan dari 0 sampai dengan i. Apabila hal ini dilakukan
sebanyak N-1 kali, maka Cmax adalah jumlah dari deret aritmetik 2, 3, 4,
..., N atau (N – 1) / 2 . (2 + N)
Cara menghitung Crata-rata
adalah dengan menjumlahkan Cmin dan Cmax dan dibagi dengan 2.
Jumlah
penggeseran (=M) minimum, rata-rata dan maksimum untuk metode penyisipan
langsung adalah :
Mmin = 2(N
– 1)
Mrata-rata = (N2
+ 7N - 8) / 4
Mmax = (N2
+ 3N – 4) / 2
Metode Penyisipan Biner
Metode ini merupakan pengembangan
dari metode penyisipan langsung. Dengan cara penyisipan langsung, perbandingan
selalu dimulai dari elemen pertama (data ke-0), sehingga untuk menyisipkan
elemen ke i kita harus melakukan perbandingan sebanyak i-1 kali. Ide dari
metode ini didasarkan pada kenyataan bahwa pada saat menggeser data ke-i, data
ke 0 s/d i-1 sebenarnya sudah dalam keadaan terurut.Sebagai
contoh pada tabel diatas, pada saat i=4, data ke 0 s/d 3 sudah dalam keadaan
urut : 3, 9, 12, 35. Dengan demikian posisi dari data ke-i sebenarnya dapat
ditentukan dengan pencarianbiner.
Misalnya pada saat i = 7, data
yang akan dipindah adalah 15 sedangkan data di sebelah kiri 15 adalah sebagai
berikut :
3
|
9
|
11
|
12
|
17
|
23
|
35
|
15
|
Pertama-tama dicari data pada
posisi paling tengah diantara data diatas.Data yang terletak di tengah adalah
data ke-3, yaitu 12. Karena 12 < 15, berarti 15 harus disisipkan di sebelah
kanan 12. Oleh karena itu, proses pencarian dlanjutkan lagi untuk data berikut
17
|
23
|
35
|
Dari hasil ini, didapat data
tengahnya adalah data 23. Karena 15 < 23, berarti 15 harus
disisipkan di sebelah kiri 23.
Proses dilanjutkan kembali untuk data
17
|
Karena 17 > 15, berarti 15
harus disisipkan di sebelah kiri 17
Algoritma penyisipan biner dapat
dituliskan sebagai berikut :
i←1
selama (i < N) kerjakan baris 3
sampai dengan 14
x←Data[i]
l←0
r←i
– 1
selama (l<=r) kerjakan baris 7 dan 8
m←(l
+ r) / 2
jika (x < Data[m]) maka r ←m – 1, jika tidak l ←m + 1
j←i
– 1
selama ( j >=l) kerjakan baris 11
dan 12
Data[j+1] ←Data[j]
j←j
– 1
Data[l] ←x
I
←i + 1
Di bawah ini merupakan prosedur
yang menggunakan metode penyisipan biner.
void
BinaryInsertSort()
{
int i, j, l,
r, m, x;
for (i=1;
i<Max; i++){
x = Data[i];
l = 0;
r = i - 1;
while(l <=
r){
m = (l + r) /
2;
if(x <
Data[m])
r = m - 1;
else
l = m + 1;
}
for(j=i-1;
j>=l; j--)
Data[j+1] =
Data[j];
Data[l]=x;
}
}
Dari algoritma
dan prosedur diatas, jumlah perbandingan (=C) untuk metode penyisipan
biner adalah :
C = Σ [2log(i)]
Sedangkan jumlah
penggeseran (=M) untuk metode penyisipan biner sama dengan metode
penyisipan langsung.
Metode Seleksi
Metode seleksi melakukan pengurutan dengan cara mencari data
yang terkecil kemudian menukarkannya dengan data yang digunakan sebagai acuan
atau sering dinamakan pivot.
Proses pengurutan dengan metode
seleksi dapat dijelaskan sebagai berikut : langkah pertama dicari data terkecil
dari data pertama sampai data terakhir. Kemudian data terkecil ditukar dengan
data pertama. Dengan demikian, data pertama sekarang mempunyai nilai paling
kecil dibanding data yang lain. Langkah kedua, data terkecil kita cari mulai
dari data kedua sampai terakhir.Data terkecil yang kita peroleh ditukar dengan
data kedua dan demikian seterusnya sampai semua elemen dalam keadaan
terurutkan.
Algoritma
seleksi dapat dituliskan sebagai berikut :
i←0
selama (i < N-1) kerjakan baris 3
sampai dengan 9
k←i
j←i
+ 1
Selama (j < N) kerjakan baris 6 dan
7
Jika (Data[k] > Data[j]) maka k ←j
j←j
+ 1
Tukar Data[i] dengan Data[k]
i←i
+ 1
Untuk
lebih memperjelas langkah-langkah algoritma seleksi dapat dilihat pada table.
Proses pengurutan pada tabel 6.2 dapat dijelaskan sebagai berikut:
·
Pada
saat i=0, data terkecil antara data ke-1 s/d ke-9 adalah data ke-4, yaitu 3,
maka data ke-0 yaitu 12 ditukar dengan data ke-4 yaitu 3.
·
Pada
saat i=1, data terkecil antara data ke-2 s/d ke-9 adalah data ke-2, yaitu 9,
maka data ke-1 yaitu 35 ditukar dengan data ke-2 yaitu 9.
·
Pada
saat i=2, data terkecil antara data ke-3 s/d ke-9 adalah data ke-3, yaitu 11,
maka data ke-2 yaitu 35 ditukar dengan data ke-3 yaitu 11.
·
Pada
saat i=3, data terkecil antara data ke-4 s/d ke-9 adalah data ke-4, yaitu 12,
maka data ke-3 yaitu 35 ditukar dengan data ke-4 yaitu 12.
·
Dan
seterusnya.
Iterasi
|
Data[0]
|
Data[1]
|
Data[2]
|
Data[3]
|
Data[4]
|
Data[5]
|
Data[6]
|
Data[7]
|
Data[8]
|
Data[9]
|
Awal
|
12
|
35
|
9
|
11
|
3
|
17
|
23
|
15
|
31
|
20
|
I=0
|
12
|
35
|
9
|
11
|
3
|
17
|
23
|
15
|
31
|
20
|
I=1
|
3
|
35
|
9
|
11
|
12
|
17
|
23
|
15
|
31
|
20
|
I=2
|
3
|
9
|
35
|
11
|
12
|
17
|
23
|
15
|
31
|
20
|
I=3
|
3
|
9
|
11
|
35
|
12
|
17
|
23
|
15
|
31
|
20
|
I=4
|
3
|
9
|
11
|
12
|
35
|
17
|
23
|
15
|
31
|
20
|
I=5
|
3
|
9
|
11
|
12
|
15
|
17
|
23
|
35
|
31
|
20
|
I=6
|
3
|
9
|
11
|
12
|
15
|
17
|
23
|
35
|
31
|
20
|
I=7
|
3
|
9
|
11
|
12
|
15
|
17
|
20
|
35
|
31
|
23
|
I=8
|
3
|
9
|
11
|
12
|
15
|
17
|
20
|
23
|
31
|
35
|
Akhir
|
3
|
9
|
11
|
12
|
15
|
17
|
20
|
23
|
31
|
35
|
Di bawah ini merupakan prosedur yang menggunakan
metode seleksi.
void SelectionSort()
{
int i, j,
k;
for(i=0;
i<Max-1;i++){
k = i;
for (j=i+1;
j<Max; j++)
if(Data[k]
> Data[j])
k = j;
Tukar(&Data[i],
&Data[k]);
}
}
Dari algoritma dan prosedur diatas, jumlah
perbandingan (=C) metode seleksi
adalah
C = N(N – 1) / 2
Jumlah penukaran (=M) pada metode seleksi
tergantung keadaan datanya. Penukaran minimum terjadi bila data sudah dalam keadaan
urut, sebaliknya jumlah penukaran maksimum terjadi bila data dalam keadaan urut
terbalik. Jumlah penukaran minimum dan maksimum dapat dirumuskan sebagai
berikut :
Mmin = 3(N – 1)
Mmax = [N2 / 4]+ 3(N – 1)
Tidak ada komentar:
Posting Komentar