Pemrograman Berorientasi objek (PBO) (Object Orientation Programming(OOP)) merupakan konsep pemrograman yang membagi program menjadi objek-objek yang nantinya dapat terhubung atau saling berinteraksi satu sama yang lainnya.
OOP memiliki 3 dasar dalam pemrogramannya, yaitu:
1. Inheritance (pewarisan) merupakan proses pewarisan data dan method dari kelas induk(Super Class) ke kelas anak(Sub Class). Dalam inheritance terdapat istilah overriding dan overload, apa itu? cari sendiri!! hehe. overriding itu kemampuan subClass untuk memodifikasi atau meredefinisi data atau method dari superClass. proses ini nantinya akan mengakibatkan kepada kedua kelas; subClass dan superClass. kalo overloding itu kemampuan dalam membuat dua atau lebih method dengan nama yang sama dalam satu kelas, namun memiliki jumlah parameter atau tipe argumentnya berbeda.
2. Encapsulation(Pembungkusan) merupakan cara "membungkus" data dan method yang menyusun suatu kelas sehingga kelas dapat dipandang sebagai suatu modul dan cara bagaiman menyembunyikannya dari luar (information hiding). Dalam OOP, enkapsulasi sangat penting untuk keamanan serta menghindari kesalaham permrograman,
3. Polymorphism, nah istilah satu ini dapat diartikan sebagai banyak bentuk. Penerapan polymorphism ini dilakukan dengan menggunakan nama yang sama, namun mempunyai tingkah laku (behavior) yang berbeda sehingga listing code implementasinyapun berbeda.
http://www.wilantara.com/pemrograman/22-pemrograman-berorientasi-objek.html
Minggu, 15 Mei 2011
Pemrograman Berorientasi objek
1. Apa itu PBO
Pemrograman berorientasi objek (Inggris: object-oriented programming disingkat OOP) merupakan paradigma pemrograman yang berorientasikan kepada objek. Semua data dan fungsi di dalam paradigma ini dibungkus dalam kelas-kelas atau objek-objek. Bandingkan dengan logika pemrograman terstruktur. Setiap objek dapat menerima pesan, memproses data, dan mengirim pesan ke objek lainnya.
Model data berorientasi objek dikatakan dapat memberi fleksibilitas yang lebih, kemudahan mengubah program, dan digunakan luas dalam teknik piranti lunak skala besar. Lebih jauh lagi, pendukung OOP mengklaim bahwa OOP lebih mudah dipelajari bagi pemula dibanding dengan pendekatan sebelumnya, dan pendekatan OOP lebih mudah dikembangkan dan dirawat.
2. Konstruktur dan Destruktur
*. Konstruktur adalah fungsi khusus anggota kelas yang otomatis dijalankan pada saat penciptaan objek (mendeklarasikan instancea). Konstruktur ditandai dengan namanya, yaitu sama dengan nama kelas. Konstruktur tidak mempunyai tipe hasil (return value). Biasanya konstruktur dipakai untuk inisialisai anggota data dan melakukan alokasi memori secara dinamis. Meskipun konstruktot tidak harus ada dalam kelas, tetappi jika diperlukan konstruktor dapat lebih dari satu.
Konstruktor adalah fungsi anggota yang mempunyai nama yang sam dengan nama kelas. Kegunaannya :
1. Mengalokasikan ruang bagi sebuah objek
2. Memberkan nilai awal terhadap anggota data suatu objek
3. Membentuk tugas-tugas lainnya
contoh:
*. Destruktur adalah pasangan konstruktur. Pada saat program membuat objek maka secara otomatis konstruktor akan dijalankan, yang biasanya dimaksudkan nuntuk memberi nilai awal variabel private. Sejalan dengan itu, C++ menyediakan fungsi destruktor (penghancur atau pelenyap) yang secara otomatis akan dijalankan pada saat berakhirnya objek. Setiap kelas mempunyai tepat satu destruktor. Jika kita mendeklarasian sebuah destruktor dalam sebuah kelas, maka destruktor akan deciptakan sendiri oleh compiler C++. Fungsi destruktor itu sendiri adalah untuk mendealokasikan memori dinamis yang diciptakan konstruktor. Destruktor adalah fungsi anggota yang mempunyai nama yang sama dengan nama kelas ditambah symbol tilde (~) didepannya.
contoh :
reference : http://id.wikipedia.org/wiki/Pemrograman_berorientasi_objek
Pemrograman berorientasi objek (Inggris: object-oriented programming disingkat OOP) merupakan paradigma pemrograman yang berorientasikan kepada objek. Semua data dan fungsi di dalam paradigma ini dibungkus dalam kelas-kelas atau objek-objek. Bandingkan dengan logika pemrograman terstruktur. Setiap objek dapat menerima pesan, memproses data, dan mengirim pesan ke objek lainnya.
Model data berorientasi objek dikatakan dapat memberi fleksibilitas yang lebih, kemudahan mengubah program, dan digunakan luas dalam teknik piranti lunak skala besar. Lebih jauh lagi, pendukung OOP mengklaim bahwa OOP lebih mudah dipelajari bagi pemula dibanding dengan pendekatan sebelumnya, dan pendekatan OOP lebih mudah dikembangkan dan dirawat.
2. Konstruktur dan Destruktur
*. Konstruktur adalah fungsi khusus anggota kelas yang otomatis dijalankan pada saat penciptaan objek (mendeklarasikan instancea). Konstruktur ditandai dengan namanya, yaitu sama dengan nama kelas. Konstruktur tidak mempunyai tipe hasil (return value). Biasanya konstruktur dipakai untuk inisialisai anggota data dan melakukan alokasi memori secara dinamis. Meskipun konstruktot tidak harus ada dalam kelas, tetappi jika diperlukan konstruktor dapat lebih dari satu.
Konstruktor adalah fungsi anggota yang mempunyai nama yang sam dengan nama kelas. Kegunaannya :
1. Mengalokasikan ruang bagi sebuah objek
2. Memberkan nilai awal terhadap anggota data suatu objek
3. Membentuk tugas-tugas lainnya
contoh:
*. Destruktur adalah pasangan konstruktur. Pada saat program membuat objek maka secara otomatis konstruktor akan dijalankan, yang biasanya dimaksudkan nuntuk memberi nilai awal variabel private. Sejalan dengan itu, C++ menyediakan fungsi destruktor (penghancur atau pelenyap) yang secara otomatis akan dijalankan pada saat berakhirnya objek. Setiap kelas mempunyai tepat satu destruktor. Jika kita mendeklarasian sebuah destruktor dalam sebuah kelas, maka destruktor akan deciptakan sendiri oleh compiler C++. Fungsi destruktor itu sendiri adalah untuk mendealokasikan memori dinamis yang diciptakan konstruktor. Destruktor adalah fungsi anggota yang mempunyai nama yang sama dengan nama kelas ditambah symbol tilde (~) didepannya.
contoh :
reference : http://id.wikipedia.org/wiki/Pemrograman_berorientasi_objek
Pencarian
1. Pencarian Sekuensial
“Sequential search atau Pencarian sekuensial” bisa disebut dengan pencarian linear yang merupakan model pencarian yang paling simpel dan sederhana banget deh yang dapat dilakukan terhadap suatu kumpulan data. Suatu tekhnik pencarian dalam array (1 dimensi) yang akan menelusuri semua elemen-elemen array dari awal sampai akhir, dimana data-data tidak perlu diurutkan terlebih dahulu.
Biar kalian lebih paham secara konsep, penjelasannya adalah sebagai berikut :
Keunggulan dari pencarian sekuensial ini adalah jika data yang dicari terletak di indeks array terdepan maka waktu dalam pencarian nya sangat cepat, dalam artian waktu yang minim sekali. Keburukannya adalah kalau jika data indeks array nya yang dicari paling belakang, maka waktu yang dicari tuh lama banget (maksimal).
Terdapat L yang merupakan larik yang berisi n buah data ( L[0],L[1]…….L[n-1]) dan k adalah data yang akan dicari. Pencarian dilakukan untuk menemukan L[i] = k dengan i adalah bilangan indeks terkecil yang memenuhi kondisi 0<= k <=n-1. Tentu saja bahwa data yang di cari tidak ditemukan. Jika misalnya terdapat angka 4, maka ditulis ada, sedangkan jika dimunculkan angka 6, namun angka 6 tidak ada maka akan muncul tulisan tidak ada. Algoritma Pada dasarnya, algoritma pencarian ini adalah proses membandingkan setiap elemen larik satu per satu secara beruntun sampai seluruh elemen diperiksa. program pencarian; uses crt; procedure seq_search; var L: array[1..5] of integer; bil,i: integer; begin write('Angka yang dicari= '); readln(bil); L[1]:=1; L[2]:=3; L[3]:=5; L[4]:=7; L[5]:= 9; i:=1; while (i<5) and (L[i] <> bil) do begin
i:=i+1;
end;
if (L[i]=bil) then
writeln('Ditemukan pada elemen larik ke-',i)
else
writeln('Tidak ditemukan!');
end;
begin
clrscr;
seq_search;
readkey;
end.
2.Pencarian Biner
Salah satu syarat agar pencarian biner dapat dilakukan adalah data sudah dalam
keadaan urut. Dengan kata lain, apabila data belum dalam keadaan urut, pencarian biner
tidak dapat dilakukan. Dalam kehidupan sehari-hari, sebenarnya kita juga sering
menggunakan pencarian biner. Misalnya saat ingin mencari suatu kata dalam kamus
Prinsip dari pencarian biner dapat dijelaskan sebagai berikut : mula-mula diambil
posisi awal 0 dan posisi akhir = N - 1, kemudian dicari posisi data tengah dengan rumus
(posisi awal + posisi akhir) / 2. Kemudian data yang dicari dibandingkan dengan data
tengah. Jika lebih kecil, proses dilakukan kembali tetapi posisi akhir dianggap sama
dengan posisi tengah –1. Jika lebih besar, porses dilakukan kembali tetapi posisi awal
dianggap sama dengan posisi tengah + 1. Demikian seterusnya sampai data tengah
sama dengan yang dicari.
Untuk lebih jelasnya perhatikan contoh berikut. Misalnya ingin mencari data 17
pada sekumpulan data berikut :
3 9 11 12 15 17 20 23 31 35
awal tengah akhir
Mula-mula dicari data tengah, dengan rumus (0 + 9) / 2 = 4. Berarti data tengah
adalah data ke-4, yaitu 15. Data yang dicari, yaitu 17, dibandingkan dengan data tengah
ini. Karena 17 > 15, berarti proses dilanjutkan tetapi kali ini posisi awal dianggap sama
dengan posisi tengah + 1 atau 5.
3 9 11 12 15 17 20 23 31 35
Awal tengah akhir
Data tengah yang baru didapat dengan rumus (5 + 9) / 2 = 7. Berarti data tengah
yang baru adalah data ke-7, yaitu 23. Data yang dicari yaitu 17 dibandingkan dengan
data tenah ini. Karena 17 < 23, berarti proses dilanjukkan tetapi kali ini posisi akhir dianggap sama dengan posisi tengah – 1 atau 6. 3 9 11 12 15 17 20 23 31 35 Awal tengah akhir Data tengah yang baru didapat dengan rumus (5 + 6) / 2 = 5. Berarti data tengah yang baru adalah data ke-5, yaitu 17. data yang dicari dibandingkan dengan data tengah ini dan ternyata sama. Jadi data ditemukan pada indeks ke-5. Pencarian biner ini akan berakhir jika data ditemukan atau posisi awal lebih besar daripada posisi akhir. Jika posisi sudah lebih besar daripada posisi akhir berarti data tidak ditemukan. Untuk lebih jelasnya perhatikan contoh pencarian data 16 pada data diatas. Prosesnya hampir sama dengan pencarian data 17. Tetapi setelah posisi awal 5 dan posisi akhir 6, data tidak ditemukan dan 16 < 17, maka posisi akhir menjadi posisi tengah – 1 atau = 4 sedangkan posisi awal = 5. 3 9 11 12 15 17 20 23 31 35 akhir awal Disini dapat dilihat bahwa posisi awal lebih besar daripada posisi akhir, yang artinya data tidak ditemukan. Algoritma pencarian biner dapat dituliskan sebagai berikut : 1 L ← 0 2 R ← N - 1 3 ketemu ← false 4 Selama (L <= R) dan (tidak ketemu) kerjakan baris 5 sampai dengan 8 5 m ← (L + R) / 2 6 Jika (Data[m] = x) maka ketemu ← true 7 Jika (x < Data[m]) maka R ← m – 1 8 Jika (x > Data[m]) maka L ← m + 1
9 Jika (ketemu) maka m adalah indeks dari data yang dicari, jika tidak data tidak
ditemukan
Di bawah ini merupakan fungsi untuk mencari data menggunakan pencarian biner.
int BinarySearch(int x)
{
int L = 0, R = Max-1, m;
bool ketemu = false;
while((L <= R) && (!ketemu))
{
m = (L + R) / 2;
if(Data[m] == x)
ketemu = true;
else if (x < data[m])
R = m - 1;
else
L = m + 1;
}
if(ketemu)
return m;
else
return -1;
}
Program 8.2 Fungsi Pencarian Data dengan Metode Biner
Fungsi diatas akan mengembalikan indeks dari data yang dicari. Apabila data
tidak ditemukan maka fungsi diatas akan mengembalikan nilai –1.
Jumlah pembandingan minimum pada pencarian biner adalah 1 kali, yaitu apabila
data yang dicari tepat berada di tengah-tengah. Jumlah pembandingan maksimum yang
dilakukan dengan pencarian biner dapat dicari menggunakan rumus logaritma, yaitu :
C = 2log(N)
refernce : http://informatika-hery.blogspot.com/2010/10/binary-search-pencarian-biner.html
“Sequential search atau Pencarian sekuensial” bisa disebut dengan pencarian linear yang merupakan model pencarian yang paling simpel dan sederhana banget deh yang dapat dilakukan terhadap suatu kumpulan data. Suatu tekhnik pencarian dalam array (1 dimensi) yang akan menelusuri semua elemen-elemen array dari awal sampai akhir, dimana data-data tidak perlu diurutkan terlebih dahulu.
Biar kalian lebih paham secara konsep, penjelasannya adalah sebagai berikut :
Keunggulan dari pencarian sekuensial ini adalah jika data yang dicari terletak di indeks array terdepan maka waktu dalam pencarian nya sangat cepat, dalam artian waktu yang minim sekali. Keburukannya adalah kalau jika data indeks array nya yang dicari paling belakang, maka waktu yang dicari tuh lama banget (maksimal).
Terdapat L yang merupakan larik yang berisi n buah data ( L[0],L[1]…….L[n-1]) dan k adalah data yang akan dicari. Pencarian dilakukan untuk menemukan L[i] = k dengan i adalah bilangan indeks terkecil yang memenuhi kondisi 0<= k <=n-1. Tentu saja bahwa data yang di cari tidak ditemukan. Jika misalnya terdapat angka 4, maka ditulis ada, sedangkan jika dimunculkan angka 6, namun angka 6 tidak ada maka akan muncul tulisan tidak ada. Algoritma Pada dasarnya, algoritma pencarian ini adalah proses membandingkan setiap elemen larik satu per satu secara beruntun sampai seluruh elemen diperiksa. program pencarian; uses crt; procedure seq_search; var L: array[1..5] of integer; bil,i: integer; begin write('Angka yang dicari= '); readln(bil); L[1]:=1; L[2]:=3; L[3]:=5; L[4]:=7; L[5]:= 9; i:=1; while (i<5) and (L[i] <> bil) do begin
i:=i+1;
end;
if (L[i]=bil) then
writeln('Ditemukan pada elemen larik ke-',i)
else
writeln('Tidak ditemukan!');
end;
begin
clrscr;
seq_search;
readkey;
end.
2.Pencarian Biner
Salah satu syarat agar pencarian biner dapat dilakukan adalah data sudah dalam
keadaan urut. Dengan kata lain, apabila data belum dalam keadaan urut, pencarian biner
tidak dapat dilakukan. Dalam kehidupan sehari-hari, sebenarnya kita juga sering
menggunakan pencarian biner. Misalnya saat ingin mencari suatu kata dalam kamus
Prinsip dari pencarian biner dapat dijelaskan sebagai berikut : mula-mula diambil
posisi awal 0 dan posisi akhir = N - 1, kemudian dicari posisi data tengah dengan rumus
(posisi awal + posisi akhir) / 2. Kemudian data yang dicari dibandingkan dengan data
tengah. Jika lebih kecil, proses dilakukan kembali tetapi posisi akhir dianggap sama
dengan posisi tengah –1. Jika lebih besar, porses dilakukan kembali tetapi posisi awal
dianggap sama dengan posisi tengah + 1. Demikian seterusnya sampai data tengah
sama dengan yang dicari.
Untuk lebih jelasnya perhatikan contoh berikut. Misalnya ingin mencari data 17
pada sekumpulan data berikut :
3 9 11 12 15 17 20 23 31 35
awal tengah akhir
Mula-mula dicari data tengah, dengan rumus (0 + 9) / 2 = 4. Berarti data tengah
adalah data ke-4, yaitu 15. Data yang dicari, yaitu 17, dibandingkan dengan data tengah
ini. Karena 17 > 15, berarti proses dilanjutkan tetapi kali ini posisi awal dianggap sama
dengan posisi tengah + 1 atau 5.
3 9 11 12 15 17 20 23 31 35
Awal tengah akhir
Data tengah yang baru didapat dengan rumus (5 + 9) / 2 = 7. Berarti data tengah
yang baru adalah data ke-7, yaitu 23. Data yang dicari yaitu 17 dibandingkan dengan
data tenah ini. Karena 17 < 23, berarti proses dilanjukkan tetapi kali ini posisi akhir dianggap sama dengan posisi tengah – 1 atau 6. 3 9 11 12 15 17 20 23 31 35 Awal tengah akhir Data tengah yang baru didapat dengan rumus (5 + 6) / 2 = 5. Berarti data tengah yang baru adalah data ke-5, yaitu 17. data yang dicari dibandingkan dengan data tengah ini dan ternyata sama. Jadi data ditemukan pada indeks ke-5. Pencarian biner ini akan berakhir jika data ditemukan atau posisi awal lebih besar daripada posisi akhir. Jika posisi sudah lebih besar daripada posisi akhir berarti data tidak ditemukan. Untuk lebih jelasnya perhatikan contoh pencarian data 16 pada data diatas. Prosesnya hampir sama dengan pencarian data 17. Tetapi setelah posisi awal 5 dan posisi akhir 6, data tidak ditemukan dan 16 < 17, maka posisi akhir menjadi posisi tengah – 1 atau = 4 sedangkan posisi awal = 5. 3 9 11 12 15 17 20 23 31 35 akhir awal Disini dapat dilihat bahwa posisi awal lebih besar daripada posisi akhir, yang artinya data tidak ditemukan. Algoritma pencarian biner dapat dituliskan sebagai berikut : 1 L ← 0 2 R ← N - 1 3 ketemu ← false 4 Selama (L <= R) dan (tidak ketemu) kerjakan baris 5 sampai dengan 8 5 m ← (L + R) / 2 6 Jika (Data[m] = x) maka ketemu ← true 7 Jika (x < Data[m]) maka R ← m – 1 8 Jika (x > Data[m]) maka L ← m + 1
9 Jika (ketemu) maka m adalah indeks dari data yang dicari, jika tidak data tidak
ditemukan
Di bawah ini merupakan fungsi untuk mencari data menggunakan pencarian biner.
int BinarySearch(int x)
{
int L = 0, R = Max-1, m;
bool ketemu = false;
while((L <= R) && (!ketemu))
{
m = (L + R) / 2;
if(Data[m] == x)
ketemu = true;
else if (x < data[m])
R = m - 1;
else
L = m + 1;
}
if(ketemu)
return m;
else
return -1;
}
Program 8.2 Fungsi Pencarian Data dengan Metode Biner
Fungsi diatas akan mengembalikan indeks dari data yang dicari. Apabila data
tidak ditemukan maka fungsi diatas akan mengembalikan nilai –1.
Jumlah pembandingan minimum pada pencarian biner adalah 1 kali, yaitu apabila
data yang dicari tepat berada di tengah-tengah. Jumlah pembandingan maksimum yang
dilakukan dengan pencarian biner dapat dicari menggunakan rumus logaritma, yaitu :
C = 2log(N)
refernce : http://informatika-hery.blogspot.com/2010/10/binary-search-pencarian-biner.html
pengurutan
1. Metode penyisipan langsung (Straight Insertion Sort)
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 :
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: void StraighInsertSort() { int i, j, x; for(i=1; i< Data[j]) { Data[j+1] = Data[j]; j--; } Data[j+1] = x; } } 2. Metode Penyisipan Biner (Binary Insertion Sort) 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<= 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;
}
}
3. Metode Seleksi (Selection Sort)
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 :
1. i = 0
2. selama (i < N-1) kerjakan baris 3 sampai dengan 9 3. k = i 4. j = i + 1 5. Selama (j < N) kerjakan baris 6 dan 7 6. Jika (Data[k] > Data[j]) maka k = j
7. j = j + 1
8. Tukar Data[i] dengan Data[k]
9. i = i + 1
Di bawah ini merupakan prosedur yang menggunakan metode seleksi:
void SelectionSort()
{
int i, j, k;
for(i=0; i Data[j])
k = j;
Tukar(&Data[i], &Data[k]);
}
}
4. Metode Shell (Shell Sort)
Metode ini disebut juga dengan metode pertambahan menurun (diminishing increment). Metode ini dikembangkan oleh Donald L. Shell pada tahun 1959, sehingga sering disebut dengan Metode Shell Sort. Metode ini mengurutkan data dengan cara membandingkan suatu data dengan data lain yang memiliki jarak tertentu, kemudian dilakukan penukaran bila diperlukan. Proses pengurutan dengan metode Shell dapat dijelaskan sebagai berikut :
Pertama-tama adalah menentukan jarak mula-mula dari data yang akan dibandingkan, yaitu N / 2. Data pertama dibandingkan dengan data dengan jarak N / 2. Apabila data pertama lebih besar dari data ke N / 2 tersebut maka kedua data tersebut ditukar. Kemudian data kedua dibandingkan dengan jarak yang sama yaitu N / 2. Demikian seterusnya sampai seluruh data dibandingkan sehingga semua data ke-j selalu lebih kecil daripada data ke-(j + N / 2).
Pada proses berikutnya, digunakan jarak (N / 2) / 2 atau N / 4. Data pertama dibandingkan dengan data dengan jarak N / 4. Apabila data pertama lebih besar dari data ke N / 4 tersebut maka kedua data tersebut ditukar. Kemudian data kedua dibandingkan dengan jarak yang sama yaitu N / 4. Demikianlah seterusnya hingga seluruh data dibandingkan sehingga semua data ke-j lebih kecil daripada data ke-(j + N / 4).
Pada proses berikutnya, digunakan jarak (N / 4) / 2 atau N / 8. Demikian seterusnya sampai jarak yang digunakan adalah 1.
Algoritma metode Shell dapat dituliskan sebagai berikut :
1. Jarak = N
2. Selama (Jarak > 1) kerjakan baris 3 sampai dengan 9
3. Jarak = Jarak / 2. Sudah = false
4. Kerjakan baris 4 sampai dengan 8 selama Sudah = false
5. Sudah = true
6. j = 0
7. Selama (j < N – Jarak) kerjakan baris 8 dan 9 8. Jika (Data[j] > Data[j + Jarak] maka tukar Data[j],
Data[j + Jarak].
Sudah = true
9. j = j + 1
Di bawah ini merupakan prosedur yang menggunakan metode Shell:
void ShellSort(int N)
{
int Jarak, i, j;
bool Sudah;
Jarak = N;
while(Lompat > 1)
{
Jarak = Jarak / 2;
Sudah = false;
while(!Sudah)
{
Sudah = true;
for(j=0; j Data[i])
{
Tukar(&Data[j], &Data[i]);
Sudah = false;
} } } } }
reference : http://www.seputarprogrammer.co.cc/2011/03/struktur-data-sorting-method.html
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 :
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: void StraighInsertSort() { int i, j, x; for(i=1; i< Data[j]) { Data[j+1] = Data[j]; j--; } Data[j+1] = x; } } 2. Metode Penyisipan Biner (Binary Insertion Sort) 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<= 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;
}
}
3. Metode Seleksi (Selection Sort)
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 :
1. i = 0
2. selama (i < N-1) kerjakan baris 3 sampai dengan 9 3. k = i 4. j = i + 1 5. Selama (j < N) kerjakan baris 6 dan 7 6. Jika (Data[k] > Data[j]) maka k = j
7. j = j + 1
8. Tukar Data[i] dengan Data[k]
9. i = i + 1
Di bawah ini merupakan prosedur yang menggunakan metode seleksi:
void SelectionSort()
{
int i, j, k;
for(i=0; i Data[j])
k = j;
Tukar(&Data[i], &Data[k]);
}
}
4. Metode Shell (Shell Sort)
Metode ini disebut juga dengan metode pertambahan menurun (diminishing increment). Metode ini dikembangkan oleh Donald L. Shell pada tahun 1959, sehingga sering disebut dengan Metode Shell Sort. Metode ini mengurutkan data dengan cara membandingkan suatu data dengan data lain yang memiliki jarak tertentu, kemudian dilakukan penukaran bila diperlukan. Proses pengurutan dengan metode Shell dapat dijelaskan sebagai berikut :
Pertama-tama adalah menentukan jarak mula-mula dari data yang akan dibandingkan, yaitu N / 2. Data pertama dibandingkan dengan data dengan jarak N / 2. Apabila data pertama lebih besar dari data ke N / 2 tersebut maka kedua data tersebut ditukar. Kemudian data kedua dibandingkan dengan jarak yang sama yaitu N / 2. Demikian seterusnya sampai seluruh data dibandingkan sehingga semua data ke-j selalu lebih kecil daripada data ke-(j + N / 2).
Pada proses berikutnya, digunakan jarak (N / 2) / 2 atau N / 4. Data pertama dibandingkan dengan data dengan jarak N / 4. Apabila data pertama lebih besar dari data ke N / 4 tersebut maka kedua data tersebut ditukar. Kemudian data kedua dibandingkan dengan jarak yang sama yaitu N / 4. Demikianlah seterusnya hingga seluruh data dibandingkan sehingga semua data ke-j lebih kecil daripada data ke-(j + N / 4).
Pada proses berikutnya, digunakan jarak (N / 4) / 2 atau N / 8. Demikian seterusnya sampai jarak yang digunakan adalah 1.
Algoritma metode Shell dapat dituliskan sebagai berikut :
1. Jarak = N
2. Selama (Jarak > 1) kerjakan baris 3 sampai dengan 9
3. Jarak = Jarak / 2. Sudah = false
4. Kerjakan baris 4 sampai dengan 8 selama Sudah = false
5. Sudah = true
6. j = 0
7. Selama (j < N – Jarak) kerjakan baris 8 dan 9 8. Jika (Data[j] > Data[j + Jarak] maka tukar Data[j],
Data[j + Jarak].
Sudah = true
9. j = j + 1
Di bawah ini merupakan prosedur yang menggunakan metode Shell:
void ShellSort(int N)
{
int Jarak, i, j;
bool Sudah;
Jarak = N;
while(Lompat > 1)
{
Jarak = Jarak / 2;
Sudah = false;
while(!Sudah)
{
Sudah = true;
for(j=0; j Data[i])
{
Tukar(&Data[j], &Data[i]);
Sudah = false;
} } } } }
reference : http://www.seputarprogrammer.co.cc/2011/03/struktur-data-sorting-method.html
Langganan:
Postingan (Atom)