Popular Posts
-
Metrika adalah kumpulan bilangan berbentuk persegi panjang yang disusun menurut baris dan kolom. Bilangan-bilangan yang terdapat di suatu ...
-
Merge Sort (Metode Penggabungan) Metode penggabungan biasanya digunakan pada pengurutan berkas. Prinsip dari metode penggabun...
-
Quick Sort (Metode Quick) Metode Quick sering disebut juga metode partisi (partition exchange sort). Metode ini diperkenalkan pertam...
-
Entity Relationship Diagram (ERD) Entity Relationship Diagram merupakan jaringan yang menggunakan susunan data yang disimpan dari s... -
Key adalah satu gabungan dari beberapa atribut yang dapat membedakan semua basis data (row) dalam tabel secara unik. 1. Super ...
-
Dalam matematika, himpunan adalah segala koleksi benda-benda tertentu yang dianggap sebagai satu kesatuan. Walaupun hal ini merupakan id...
-
Selection Sort (Metode Seleksi) Metode seleksi melakukan pengurutan dengan cara mencari data yang terkecil kemudian menukarkannya dengan...
-
Insertion Sort (Metode Penyisipan) ---( Straight Insertion Sort (Metode Penyisipan langsung) Proses pengurutan dengan metode peny...
-
Sorting merupakan suatu proses untuk menyusun kembali humpunan obyek menggunakan aturan tertentu. Sorting disebut juga s ebagai suatu alg...
-
Shell Sort (Metode Shell) Metode ini disebut juga dengan metode pertambahan menurun (diminishing increment). Metode ini dikembangka...
Sabtu, 16 Februari 2013
Insertion Sort (Metode Penyisipan)
---( Straight Insertion Sort (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.
Animation of the insertion sort sorting a 30element array.
Algoritma penyisipan langsung dapat dituliskan sebagai berikut :
1. i = 1
2. selama (i < N) kerjakan baris 3 sampai dengan 9
3. x = Data[i]
4. j = i – 1
5. selama (x < Data[j]) kerjakan baris 6 dan 7
6. Data[j + 1] = Data[j]
7. j = j – 1
8. Data[j+1] = x
9. i = i + 1
Di bawah ini merupakan prosedur yang menggunakan metode penyisipan langsung: 2. selama (i < N) kerjakan baris 3 sampai dengan 9
3. x = Data[i]
4. j = i – 1
5. selama (x < Data[j]) kerjakan baris 6 dan 7
6. Data[j + 1] = Data[j]
7. j = j – 1
8. Data[j+1] = x
9. i = i + 1
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;
} }
---( Binary Insertion Sort (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.
Algoritma penyisipan biner dapat dituliskan sebagai berikut :
1. i = 1
2. selama (i < N) kerjakan baris 3 sampai dengan 14
3. x = Data[i]
4. l = 0
5. r = i – 1
6. selama (l<=r) kerjakan baris 7 dan 8
7. m = (l + r) / 2
8. jika (x < Data[m]) maka r = m – 1, jika tidak l = m + 1
9. j = i – 1
10. selama ( j >=l) kerjakan baris 11 dan 12
11. Data[j+1] = Data[j]
12. j = j – 1
13. Data[l] = x
14. 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;
}
}
Langganan:
Posting Komentar (Atom)
0 komentar:
Posting Komentar