Struktur Data
Obyektif :
Mengetahui maksud struktur data dan menjelaskan penggunaannya dalam pemrograman
Mengetahui operasi yang terkait dengan struktur data dan metode pemrograman paling umum yang terkait dengan struktur tersebut.
Mengetahui metode dan notasi yang digunakan untuk menspesifikasi apa-apa yang perlu dikerjakan oleh program dan bagaimana program ini melakukan pekerjaan tersebut.
Jenis/Tipe Data (Data Type) :
Terdiri dari
– Set nilai data
– Set operasi yang bisa diterapkan pada nilai tersebut
Klasifikasi Jenis Data :
Simple Data Type (Jenis Data Sederhana)
– Item data individual
Data Structures / data aggregates (struktur data)
– Kombinasi dari item data individual
– Membentuk item data lain
Jenis Data Sederhana :
Numerik, terdiri dari :
– Numerik integer (bilangan bulat)
– Numerik real (bilangan riil)
Karakter, terdiri dari :
– Alfabet : a .. z, A .. Z
– Angka : 0 .. 9
– Simbol khusus : + ? ‘ ! [ ] { } … dll
Boolean (logika), terdiri dari :
– True
– False
Identifikasi :
Dalam bahasa pemrograman, item data diidentifikasi menurut namanya, bukan menurut alamat lokasinya dalam memori
Identifier akan merupakan konstanta jika ia selalu dikaitkan dengan nilai data yang sama
Identifier akan merupakan variabel jika nilai datanya yang terkait bisa berubah
Literal, nilai data yang tertera dalam program namun bukan sebagai identifier
Deklarasi Data :
Jenis data konstanta dan variabel harus didefinisikan dalam program sehingga :
– operasi yang tepat dapat dijalankan pada nilai data dan
– Jumlah ruang penyimpanan yang tepat bisa ditentukan
Statement untuk mendefinisikan jenis data disebut declarative statement
Beberapa bahasa pemrograman memiliki sintaks pendeklarasian yang berbeda
Beberapa contoh program (pendeklarasian data) yang akan diberikan ditulis dalam pseudo-code
Contoh :
Constants
pi = 3.141592654
Variables
i, qty : integer
harga_satuan, harga_beli : real
status : boolean
nama : character(25)
Struktur Data
Kelompok item data yang terorganisasi yang dianggap sebagai suatu unit
Disebut juga sebagai jenis data kompleks (complex data type) atau data aggregates
Beberapa struktur data :
– Array (larik)
– String
– Record
– List (daftar)
– Tree
Kamis, 30 September 2010
PEMROGRAMAN
Nama : Angga Surahman Sudibya
Npm : 10407113
Kelas : 4ib01
Mata Kuliah : Organisasi & Arsitektur Komputer
Definisi Program/Pemrograman
• Adalah kumpulan instruksi-instruksi tersendiri yang biasanya disebut source code yang dibuat oleh programmer (pembuat program)
• Program adalah kumpulan instruksi atau perintah yang disusun sedemikian rupa sehingga mempunyai urutan nalar yang tepat untuk menyelesaikan suatu persoalan. (Menurut P. Insap Santosa)
• Instruksi (statement) yang dimaksud adalah syntax (cara penulisan) sesuai dengan bahasa pemrograman yang digunakan yang mempunyai komponen-komponen : Input, Output, Proses, Percabangan dan Perulangan.
Bahasa Pemrograman
• Adalah alat untuk membuat program
• Contoh: C, C++, C#, Pascal, Basic, Perl, PHP, ASP, JHP, Java, dll.
• Perbedaan: cara memberikan instruksi
• Persamaan: bertujuan menghasilkan output yang sama
Paradigma Pemrograman
• Pemrograman Prosedural
– Berdasarkan urutan-urutan, sekuensial
– Program adalah suatu rangkaian prosedur untuk memanipulasi data. Prosedur merupakan kumpulan instruksi yang dikerjakan secara berurutan.
– Harus mengingat prosedur mana yang sudah dipanggil dan apa yang sudah diubah.
• Pemrograman Fungsional
– Berdasarkan teori fungsi matematika
– Fungsi merupakan dasar utama program.
• Pemrograman Terstruktur
– Secara berurutan dan terstrukrtur.
– Program dapat dibagai-bagi menjadi prosedur dan fungsi.
– Contoh: PASCAL dan C
• Pemrograman Modular
– Pemrograman ini membentuk banyak modul.
– Modul merupakan kumpulan dari prosedur dan fungsi yang berdiri sendiri
– Sebuah program dapat merupakan kumpulan modul-modul.
– Contoh: MODULA-2 atau ADA
• Pemrograman Berorientasi Obyek
– Pemrograman berdasarkan prinsip obyek, dimana obyek memiliki data/variabel/property dan method/event/prosedur yang dapat dimanipulasi
– Contoh: C++, Object Pascal, dan Java.
• Pemrograman Berorientasi Fungsi
– Pemrograman ini berfokus pada suatu fungsi tertentu saja. Sangat tergantung pada tujuan pembuatan bahasa pemrograman ini.
– Contoh: SQL (Structured Query Language), HTML, XML dan lain-lain.
• Pemrograman Deklaratif
– Pemrograman ini mendeskripsikan suatu masalah dengan pernyataan daripada memecahkan masalah dengan implementasi algoritma.
– Contoh: PROLOG
Npm : 10407113
Kelas : 4ib01
Mata Kuliah : Organisasi & Arsitektur Komputer
Definisi Program/Pemrograman
• Adalah kumpulan instruksi-instruksi tersendiri yang biasanya disebut source code yang dibuat oleh programmer (pembuat program)
• Program adalah kumpulan instruksi atau perintah yang disusun sedemikian rupa sehingga mempunyai urutan nalar yang tepat untuk menyelesaikan suatu persoalan. (Menurut P. Insap Santosa)
• Instruksi (statement) yang dimaksud adalah syntax (cara penulisan) sesuai dengan bahasa pemrograman yang digunakan yang mempunyai komponen-komponen : Input, Output, Proses, Percabangan dan Perulangan.
Bahasa Pemrograman
• Adalah alat untuk membuat program
• Contoh: C, C++, C#, Pascal, Basic, Perl, PHP, ASP, JHP, Java, dll.
• Perbedaan: cara memberikan instruksi
• Persamaan: bertujuan menghasilkan output yang sama
Paradigma Pemrograman
• Pemrograman Prosedural
– Berdasarkan urutan-urutan, sekuensial
– Program adalah suatu rangkaian prosedur untuk memanipulasi data. Prosedur merupakan kumpulan instruksi yang dikerjakan secara berurutan.
– Harus mengingat prosedur mana yang sudah dipanggil dan apa yang sudah diubah.
• Pemrograman Fungsional
– Berdasarkan teori fungsi matematika
– Fungsi merupakan dasar utama program.
• Pemrograman Terstruktur
– Secara berurutan dan terstrukrtur.
– Program dapat dibagai-bagi menjadi prosedur dan fungsi.
– Contoh: PASCAL dan C
• Pemrograman Modular
– Pemrograman ini membentuk banyak modul.
– Modul merupakan kumpulan dari prosedur dan fungsi yang berdiri sendiri
– Sebuah program dapat merupakan kumpulan modul-modul.
– Contoh: MODULA-2 atau ADA
• Pemrograman Berorientasi Obyek
– Pemrograman berdasarkan prinsip obyek, dimana obyek memiliki data/variabel/property dan method/event/prosedur yang dapat dimanipulasi
– Contoh: C++, Object Pascal, dan Java.
• Pemrograman Berorientasi Fungsi
– Pemrograman ini berfokus pada suatu fungsi tertentu saja. Sangat tergantung pada tujuan pembuatan bahasa pemrograman ini.
– Contoh: SQL (Structured Query Language), HTML, XML dan lain-lain.
• Pemrograman Deklaratif
– Pemrograman ini mendeskripsikan suatu masalah dengan pernyataan daripada memecahkan masalah dengan implementasi algoritma.
– Contoh: PROLOG
Rabu, 26 Mei 2010
BINARY SEARCH
Nama : angga surahman sudibya
NPM : 10407113
Kelas : 3 Ib01 B
Mata Kuliah : Algoritma dan pemrograman
BINARY SEARCH
Metoda Pencarian Biner ( Binary Search) hanya bisa diterapkan jika data array sudah teruru. pengurutan Array bisa menggunakan jenis sorting descending atau asscending. Kelebihan dari Searching dengan metode Binary Sort adalah Untuk Pencarian data yang jumlahnya banyak, waktu pencarian relatif cepat. selain itu beban komputasi juga lebih kecil karena pencarian dilakukan dari depan, belakang, dan tengah. namun ada pula kekurangannya, yaitu data harus disorting dahulu dan Algoritma lebih rumit, tidak baik untuk data berangkai.
Algoritma dari Binary Sort
Proses yang terjadi pada pencarian dengan metode ini adalah sebagai berikut :
1.Membaca Array data
2.Apabila Array belum terurut maka array diurutkan terlebih dahulu.
3.Menentukan data yang akan dicari
4.Menentukan elemen tengah dari array
5.Jika nilai elemen tengah sama dengan data yang dicari, maka pencarian berhenti.
6.Jika elemen tengah tidak sama dengan data yang dicari maka :
a.Jika nilai elemen tengah > data yang dicari maka pencarian dilakukan pada setengah array pertama.
b.Jika nilai elemen tengah lebih kecil dari pada data yang dicari maka pencarian dilakukan pada setengah array berikutnya.
ILUSTRASI BINARY SEARCH
Misalkan saya mempunyai data sebagai berikut : 3,1,4,7,25,12,40,78,90,65. Maka data tersebut akan dicek, ternyata setelah dicek datanya belum terurut, maka dengan menggunakan metoda sorting yang sudah ada, maka kita bisa mengurut data tersebut, menjadi : 1,3,4,7,12,25,40,65,78,90
Setelah data tersebut diurutkan maka fungsi binary sort baru mulai bekerja mencari data. berikut cara dari Binary sort mencari data tersebut. misalnya data yang dicari adalah 65. maka pencariannya dijelaskan pada tabel berikut ini :
Pada data range diberi warna Hijau. Pencarian dimulai dari tengah,Kiri dan kanan. rumus untuk Posisi tengahnya adalah ( Posisi Akhir + Posisi Awal )/2. jadi Nilai tengah pada langkah pertama yaitu adalah 12 (berwarna merah) dan nilai targetnya adalah 65 (kuning). Karena nilai data yang dicari > dari data yang ditengah, maka pencarian menjadi dikanan dari nilai tengah. Setelah itu, Maka nilai 12 menjadi awal pencarian, selanjutnya dicari kembali nilai tengah pada range nilai 12 ke kanan sampai pada array dengan nilai 90. ternyata nilai tengahnya adalah 40. kemudian array dari nilai 40 dibandingkan dengan target, ternyata lebih besar, maka pencarian kembali mengarah ke kanan nilai tengah. Array dengan nilai 40 menjadi titik awal pencarian sekarang. dan sekarang nilai tengah nya adalah 65. maka dibandingkan dengan target ternyata sama, maka data sudah Ditemukan.
Referensi : http://dharmaatmaja.wordpress.com/tag/binary-search/
NPM : 10407113
Kelas : 3 Ib01 B
Mata Kuliah : Algoritma dan pemrograman
BINARY SEARCH
Metoda Pencarian Biner ( Binary Search) hanya bisa diterapkan jika data array sudah teruru. pengurutan Array bisa menggunakan jenis sorting descending atau asscending. Kelebihan dari Searching dengan metode Binary Sort adalah Untuk Pencarian data yang jumlahnya banyak, waktu pencarian relatif cepat. selain itu beban komputasi juga lebih kecil karena pencarian dilakukan dari depan, belakang, dan tengah. namun ada pula kekurangannya, yaitu data harus disorting dahulu dan Algoritma lebih rumit, tidak baik untuk data berangkai.
Algoritma dari Binary Sort
Proses yang terjadi pada pencarian dengan metode ini adalah sebagai berikut :
1.Membaca Array data
2.Apabila Array belum terurut maka array diurutkan terlebih dahulu.
3.Menentukan data yang akan dicari
4.Menentukan elemen tengah dari array
5.Jika nilai elemen tengah sama dengan data yang dicari, maka pencarian berhenti.
6.Jika elemen tengah tidak sama dengan data yang dicari maka :
a.Jika nilai elemen tengah > data yang dicari maka pencarian dilakukan pada setengah array pertama.
b.Jika nilai elemen tengah lebih kecil dari pada data yang dicari maka pencarian dilakukan pada setengah array berikutnya.
ILUSTRASI BINARY SEARCH
Misalkan saya mempunyai data sebagai berikut : 3,1,4,7,25,12,40,78,90,65. Maka data tersebut akan dicek, ternyata setelah dicek datanya belum terurut, maka dengan menggunakan metoda sorting yang sudah ada, maka kita bisa mengurut data tersebut, menjadi : 1,3,4,7,12,25,40,65,78,90
Setelah data tersebut diurutkan maka fungsi binary sort baru mulai bekerja mencari data. berikut cara dari Binary sort mencari data tersebut. misalnya data yang dicari adalah 65. maka pencariannya dijelaskan pada tabel berikut ini :
Pada data range diberi warna Hijau. Pencarian dimulai dari tengah,Kiri dan kanan. rumus untuk Posisi tengahnya adalah ( Posisi Akhir + Posisi Awal )/2. jadi Nilai tengah pada langkah pertama yaitu adalah 12 (berwarna merah) dan nilai targetnya adalah 65 (kuning). Karena nilai data yang dicari > dari data yang ditengah, maka pencarian menjadi dikanan dari nilai tengah. Setelah itu, Maka nilai 12 menjadi awal pencarian, selanjutnya dicari kembali nilai tengah pada range nilai 12 ke kanan sampai pada array dengan nilai 90. ternyata nilai tengahnya adalah 40. kemudian array dari nilai 40 dibandingkan dengan target, ternyata lebih besar, maka pencarian kembali mengarah ke kanan nilai tengah. Array dengan nilai 40 menjadi titik awal pencarian sekarang. dan sekarang nilai tengah nya adalah 65. maka dibandingkan dengan target ternyata sama, maka data sudah Ditemukan.
Referensi : http://dharmaatmaja.wordpress.com/tag/binary-search/
Algoritma Devide and Conquer
Nama : angga surahman sudibya
NPM : 10407113
Kelas : 3 Ib01 B
Mata Kuliah : Algoritma dan pemrograman
Algoritma Devide and Conquer
Terdapat beragam klasifikasi algoritma dan setiap klasifikasi mempunyai alasan tersendiri. Salah satu cara untuk melakukan klasifikasi jenis-jenis algoritma adalah dengan memperhatikan paradigma dan metode yang digunakan untuk mendesain algoritma tersebut. Beberapa paradigma yang digunakan dalam menyusun suatu algoritma akan dipaparkan dibagian ini. Masing-masing paradigma dapat digunakan dalam banyak algoritma yang berbeda.
1.Divide and Conquer, paradigma untuk membagi suatu permasalahan besar menjadi permasalahan-permasalahan yang lebih kecil. Pembagian masalah ini dilakukan terus menerus sampai ditemukan bagian masalah kecil yang mudah untuk dipecahkan. Singkatnya menyelesaikan keseluruhan masalah dengan membagi masalah besar dan kemudian memecahkan permasalahan-permasalahan kecil yang terbentuk.
Divide and Conquer dulunya adalah strategi militer yang dikenal dengan nama divide ut imperes. Sekarang strategi tersebut menjadi strategi fundamental di dalam ilmu komputer dengan nama Divide and Conquer .
Definisi :
1.Divide: membagi masalah menjadi beberapa upa-masalah yang memiliki kemiripan dengan masalah semula namun berukuran lebih kecil (idealnya berukuran hampir sama),
2.Conquer: memecahkan (menyelesaikan) masing-masing upa-masalah (secara rekursif),
Obyek permasalahan yang dibagi :
masukan (input) atau instances yang berukuran n seperti:
- tabel (larik),
- matriks,
- eksponen,
- dll, bergantung pada masalahnya.
Tiap-tiap upa-masalah mempunyai karakteristik yang sama (the same type) dengan karakteristik masalah asal, sehingga metode Divide and Conquer lebih natural diungkapkan dalam skema rekursif.
2.Dynamic programming, paradigma pemrograman dinamik akan sesuai jika digunakan pada suatu masalah yang mengandung sub-struktur yang optimal (, dan mengandung beberapa bagian permasalahan yang tumpang tindih . Paradigma ini sekilas terlihat mirip dengan paradigma Divide and Conquer, sama-sama mencoba untuk membagi permasalahan menjadi sub permasalahan yang lebih kecil, tapi secara intrinsik ada perbedaan dari karakter permasalahan yang dihadapi.
3.Metode serakah. Sebuah algoritma serakah mirip dengan sebuah Pemrograman dinamik, bedanya jawaban dari submasalah tidak perlu diketahui dalam setiap tahap; dan menggunakan pilihan "serakah" apa yang dilihat terbaik pada saat itu.
Pembuat program bertanggung jawab atas implementasi solusi. Pembuatan program akan menjadi lebih sederhana jika masalah dapat dipecah menjadi sub masalah - sub masalah yang dapat dikelola.
Penyelesaian masalah dengan komputer berhadapan dengan 4 hal, yaitu :
1. Pemahaman keterhubungan elemen-elemen data yang relevan terhadap solusi secara menyeluruh.
2. Pengambilan keputusan mengenai operasi-operasi yang dilakukan terhadap elemen-elemen data.
3. Perancangan representasi elemen-elemen data di memori sehingga memenuhi kriteria berikut:
a. Memenuhi keterhubungan logik antara elemen-elemen data.
b. Operasi-operasi terhadap elemen-elemen data dapat dilakukan secara mudah dan efisien.
4. Pengambilan keputusan mengenai mengenai bahasa pemrograman terbaik untuk menerjemahkan solusi persoalan menjadi program.
Strategi Divide dan Conquer
Strategi Divide dan Conquer memecah masalah menjadi submasalah-submasalah independen yang lebih kecil sehingga solusi submasalah-submasalah dapat diperoleh secara mudah, solusi submasalah-submasalah digabung menjadi solusi seluruh masalah.
Skema umum algoritma divide dan conquer:
Procedure DNC ( i,j : integer )
Var K : integer ;
If SMALL (i,j) then SOLVE (i,j)
Else begin
K : = DIVIDE (i,j)
COMBINE (DNC(i,k),DNC(k+1,j))
End if
Keterangan:
1. SMALL adalah fungsi yang mengirim BOOLEAN, menentukan apakah ukuran telah cukup kecil sehingga solusi dapat diperoleh. Ukuran dinyatakan sebagai telah berukuran kecil bergantung masalah.
2. DIVIDE adalah fungsi membagi menjadi 2 bagian pada posisi K. Biasanya bagian berukuran sama.
3. COMBINE adalah fungsi menggabungkan solusi X dan Y submasalah. Solusi diperoleh dengan memanggil prosedur rekursif DNC.
Jika ukuran kedua submasalah sama, waktu komputasi DNC dideskripsikan hubungan rekuren berikut :
T(n) = g (n), n kecil
2 T (n/2) + f (n), selainnya
dimana :
• T(n) adalah waktu untuk DNC dengan n masukan,
• g(n) adalah waktu komputasi jawaban secara langsung untuk masukan kecil dan
• f(n) adalah waktu COMBINE.
Untuk algoritma divide dan conquer yang menghasilkan submasalah-submasalah dengan tipe masalah yang sama dengan masalah awal, sangat alami untuk mendeskripsikan algoritma secara rekursi. Kemudian untuk meningkatkan efisiensi dilakukan penerjemahan menjadi bentuk iterasi.
Pemakaian teknik Divide dan Conquer banyak digunakan dalam menyelesaikan berbagai macam persoalan, antara lain :
1. Searching
2. Sorting
Sumber:
1. http://mita.staff.gunadarma.ac.id/Downloads/files/14268/Divide%26Conquer.doc (21 Mei 2010)
2. : http://chelseafansclub.multiply.com/journal
http://www.informatika.org/~rinaldi/Stmik/Algoritma %20Divide%20and%20Conquer.ppt
NPM : 10407113
Kelas : 3 Ib01 B
Mata Kuliah : Algoritma dan pemrograman
Algoritma Devide and Conquer
Terdapat beragam klasifikasi algoritma dan setiap klasifikasi mempunyai alasan tersendiri. Salah satu cara untuk melakukan klasifikasi jenis-jenis algoritma adalah dengan memperhatikan paradigma dan metode yang digunakan untuk mendesain algoritma tersebut. Beberapa paradigma yang digunakan dalam menyusun suatu algoritma akan dipaparkan dibagian ini. Masing-masing paradigma dapat digunakan dalam banyak algoritma yang berbeda.
1.Divide and Conquer, paradigma untuk membagi suatu permasalahan besar menjadi permasalahan-permasalahan yang lebih kecil. Pembagian masalah ini dilakukan terus menerus sampai ditemukan bagian masalah kecil yang mudah untuk dipecahkan. Singkatnya menyelesaikan keseluruhan masalah dengan membagi masalah besar dan kemudian memecahkan permasalahan-permasalahan kecil yang terbentuk.
Divide and Conquer dulunya adalah strategi militer yang dikenal dengan nama divide ut imperes. Sekarang strategi tersebut menjadi strategi fundamental di dalam ilmu komputer dengan nama Divide and Conquer .
Definisi :
1.Divide: membagi masalah menjadi beberapa upa-masalah yang memiliki kemiripan dengan masalah semula namun berukuran lebih kecil (idealnya berukuran hampir sama),
2.Conquer: memecahkan (menyelesaikan) masing-masing upa-masalah (secara rekursif),
Obyek permasalahan yang dibagi :
masukan (input) atau instances yang berukuran n seperti:
- tabel (larik),
- matriks,
- eksponen,
- dll, bergantung pada masalahnya.
Tiap-tiap upa-masalah mempunyai karakteristik yang sama (the same type) dengan karakteristik masalah asal, sehingga metode Divide and Conquer lebih natural diungkapkan dalam skema rekursif.
2.Dynamic programming, paradigma pemrograman dinamik akan sesuai jika digunakan pada suatu masalah yang mengandung sub-struktur yang optimal (, dan mengandung beberapa bagian permasalahan yang tumpang tindih . Paradigma ini sekilas terlihat mirip dengan paradigma Divide and Conquer, sama-sama mencoba untuk membagi permasalahan menjadi sub permasalahan yang lebih kecil, tapi secara intrinsik ada perbedaan dari karakter permasalahan yang dihadapi.
3.Metode serakah. Sebuah algoritma serakah mirip dengan sebuah Pemrograman dinamik, bedanya jawaban dari submasalah tidak perlu diketahui dalam setiap tahap; dan menggunakan pilihan "serakah" apa yang dilihat terbaik pada saat itu.
Pembuat program bertanggung jawab atas implementasi solusi. Pembuatan program akan menjadi lebih sederhana jika masalah dapat dipecah menjadi sub masalah - sub masalah yang dapat dikelola.
Penyelesaian masalah dengan komputer berhadapan dengan 4 hal, yaitu :
1. Pemahaman keterhubungan elemen-elemen data yang relevan terhadap solusi secara menyeluruh.
2. Pengambilan keputusan mengenai operasi-operasi yang dilakukan terhadap elemen-elemen data.
3. Perancangan representasi elemen-elemen data di memori sehingga memenuhi kriteria berikut:
a. Memenuhi keterhubungan logik antara elemen-elemen data.
b. Operasi-operasi terhadap elemen-elemen data dapat dilakukan secara mudah dan efisien.
4. Pengambilan keputusan mengenai mengenai bahasa pemrograman terbaik untuk menerjemahkan solusi persoalan menjadi program.
Strategi Divide dan Conquer
Strategi Divide dan Conquer memecah masalah menjadi submasalah-submasalah independen yang lebih kecil sehingga solusi submasalah-submasalah dapat diperoleh secara mudah, solusi submasalah-submasalah digabung menjadi solusi seluruh masalah.
Skema umum algoritma divide dan conquer:
Procedure DNC ( i,j : integer )
Var K : integer ;
If SMALL (i,j) then SOLVE (i,j)
Else begin
K : = DIVIDE (i,j)
COMBINE (DNC(i,k),DNC(k+1,j))
End if
Keterangan:
1. SMALL adalah fungsi yang mengirim BOOLEAN, menentukan apakah ukuran telah cukup kecil sehingga solusi dapat diperoleh. Ukuran dinyatakan sebagai telah berukuran kecil bergantung masalah.
2. DIVIDE adalah fungsi membagi menjadi 2 bagian pada posisi K. Biasanya bagian berukuran sama.
3. COMBINE adalah fungsi menggabungkan solusi X dan Y submasalah. Solusi diperoleh dengan memanggil prosedur rekursif DNC.
Jika ukuran kedua submasalah sama, waktu komputasi DNC dideskripsikan hubungan rekuren berikut :
T(n) = g (n), n kecil
2 T (n/2) + f (n), selainnya
dimana :
• T(n) adalah waktu untuk DNC dengan n masukan,
• g(n) adalah waktu komputasi jawaban secara langsung untuk masukan kecil dan
• f(n) adalah waktu COMBINE.
Untuk algoritma divide dan conquer yang menghasilkan submasalah-submasalah dengan tipe masalah yang sama dengan masalah awal, sangat alami untuk mendeskripsikan algoritma secara rekursi. Kemudian untuk meningkatkan efisiensi dilakukan penerjemahan menjadi bentuk iterasi.
Pemakaian teknik Divide dan Conquer banyak digunakan dalam menyelesaikan berbagai macam persoalan, antara lain :
1. Searching
2. Sorting
Sumber:
1. http://mita.staff.gunadarma.ac.id/Downloads/files/14268/Divide%26Conquer.doc (21 Mei 2010)
2. : http://chelseafansclub.multiply.com/journal
http://www.informatika.org/~rinaldi/Stmik/Algoritma %20Divide%20and%20Conquer.ppt
Sabtu, 17 April 2010
spanning tree
SPANING TREE
Nama : Angga surahman sudibya
Kelas : 3 Ib01 B
Npm : 10407113
Mata kuliah : Algoritma & pemrograman
1. Cara membuat minimum spanning tree pada jaringan diatas :
Langkah-langkah dalam membuat spanning tree adalah sebagai berikut:
a. Langkah pertama, cari nilai cost yang terkecil. Dengan cost yang kecil maka biaya yang dibutuhkan lebih murah. Karena cost diatas yang terkecil nilainya 2 maka harus didahulukan terlebih dahulu.
b. Langkah kedua, mencari nilai cost yang terkecil pula. Terdapat 3 nilai edge yang kecil yaitu antara CE, DE, dan AF. Kita boleh mempergunakan salah satu dari edge tersebut. Saya mengambil edge antara DE.
c. Langkah ketiga, sekarang edge yang costnya terkecil tinggal CE dan AF. Untuk mencari nilai spanning tree harus membentuk cabang/pohon maka saya mempergunakan edge yang AF, karena jika saya mengabil edge CE maka spanning tree akan membentuk sebuah loop. Secara teori jika spanning tree membentuk sebuah loop maka costnya menjadi lebih besar. Oleh karena itu saya mengambil edge AF agar costnya menjadi murah.
d. Langkah keempat, mencari nilai cost yang lebih murah. Karena nilai cosnya bernilai 4 sudah tidak ada, maka saya mencari alternative cost yang lebih murah. Terdapat edge BC, BE, FE. Maka saya mengambil edge BC, FE, atau BE secara sembarang. Saya mengambil edge BC.
e. Langkah kelima, hasil akhir dari spanning tree sudah terlihat yaitu tinggal menghubungkan edge FE. Karena nilai costnya yang paling murah dibandingkan dengan nilai cost yang lainnya.
f. Kesimpulan, jika kita ingin membuat route spanning tree kita yang kita harus lakukan adalah mecari nlai cost yang terkecil, lalu jangan membuat suatu loop karena akan terjadi pemborosan.
2. Menghitung total cost diatas dengan cara menambahkan nilai semua cost dengan rumus:
Σ Cost = cost1 + cost2 + cost3 + cost4 + cost5
= 2 + 4 + 4 + 5 +5
= 20
Contoh kasus:
Pandang sebuah graph sebagai berikut:
1. Buat Minimum spanning tree
2. Hitung total cost-nya
Jawab:
Keterangan:
(-) Menandakan terhubung
Kesimpulan: total cost adalah 21
Nama : Angga surahman sudibya
Kelas : 3 Ib01 B
Npm : 10407113
Mata kuliah : Algoritma & pemrograman
1. Cara membuat minimum spanning tree pada jaringan diatas :
Langkah-langkah dalam membuat spanning tree adalah sebagai berikut:
a. Langkah pertama, cari nilai cost yang terkecil. Dengan cost yang kecil maka biaya yang dibutuhkan lebih murah. Karena cost diatas yang terkecil nilainya 2 maka harus didahulukan terlebih dahulu.
b. Langkah kedua, mencari nilai cost yang terkecil pula. Terdapat 3 nilai edge yang kecil yaitu antara CE, DE, dan AF. Kita boleh mempergunakan salah satu dari edge tersebut. Saya mengambil edge antara DE.
c. Langkah ketiga, sekarang edge yang costnya terkecil tinggal CE dan AF. Untuk mencari nilai spanning tree harus membentuk cabang/pohon maka saya mempergunakan edge yang AF, karena jika saya mengabil edge CE maka spanning tree akan membentuk sebuah loop. Secara teori jika spanning tree membentuk sebuah loop maka costnya menjadi lebih besar. Oleh karena itu saya mengambil edge AF agar costnya menjadi murah.
d. Langkah keempat, mencari nilai cost yang lebih murah. Karena nilai cosnya bernilai 4 sudah tidak ada, maka saya mencari alternative cost yang lebih murah. Terdapat edge BC, BE, FE. Maka saya mengambil edge BC, FE, atau BE secara sembarang. Saya mengambil edge BC.
e. Langkah kelima, hasil akhir dari spanning tree sudah terlihat yaitu tinggal menghubungkan edge FE. Karena nilai costnya yang paling murah dibandingkan dengan nilai cost yang lainnya.
f. Kesimpulan, jika kita ingin membuat route spanning tree kita yang kita harus lakukan adalah mecari nlai cost yang terkecil, lalu jangan membuat suatu loop karena akan terjadi pemborosan.
2. Menghitung total cost diatas dengan cara menambahkan nilai semua cost dengan rumus:
Σ Cost = cost1 + cost2 + cost3 + cost4 + cost5
= 2 + 4 + 4 + 5 +5
= 20
Contoh kasus:
Pandang sebuah graph sebagai berikut:
1. Buat Minimum spanning tree
2. Hitung total cost-nya
Jawab:
Keterangan:
(-) Menandakan terhubung
Kesimpulan: total cost adalah 21
Selasa, 06 April 2010
struktur data
nama : angga surahman sudibya
NPM : 10407113
Kelas : 3 Ib01 B
kuliah : Algoritma & pemrograman
Struktur data Objektif
• Mengetahui maksud struktur data dan menjelaskan penggunaannya dalam pemrograman
• Mengetahui operasi yang terkait dengan struktur data dan metode pemrograman paling umum yang terkait dengan struktur tersebut.
• Mengetahui metode dan notasi yang digunakan untuk menspesifikasi apa-apa yang perlu dikerjakan oleh program dan bagaimana program ini melakukan pekerjaan tersebut.
Jenis/Tipe Data (Data Type)
Terdiri dari
– Set nilai data
– Set operasi yang bisa diterapkan pada nilai tersebut.
Klasifikasi Jenis Data
Simple Data Type (Jenis Data Sederhana)
– Item data individual
Data Structures / data aggregates (struktur data)
– Kombinasi dari item data individual
– Membentuk item data lain
Jenis Data Sederhana
Numerik, terdiri dari :
– Numerik integer (bilangan bulat)
– Numerik real (bilangan riil)
Karakter, terdiri dari :
– Alfabet : a .. z, A .. Z
– Angka : 0 .. 9
– Simbol khusus : + ? ‘ ! [ ] { } … dll
Boolean (logika), terdiri dari :
– True
False
Identifier
Dalam bahasa pemrograman, item data diidentifikasi menurut namanya, bukan menurut alamat lokasinya dalam memori
Identifier akan merupakan konstanta jika ia selalu dikaitkan dengan nilai data yang sama
Identifier akan merupakan variabel jika nilai datanya yang terkait bisa berubah
Literal, nilai data yang tertera dalam program namun bukan sebagai identifier
Deklarasi Data
Jenis data konstanta dan variabel harus didefinisikan dalam program sehingga :
– operasi yang tepat dapat dijalankan pada nilai data dan
– Jumlah ruang penyimpanan yang tepat bisa ditentukan
Statement untuk mendefinisikan jenis data disebut declarative statement
Beberapa bahasa pemrograman memiliki sintaks pendeklarasian yang berbeda
Beberapa contoh program (pendeklarasian data) yang akan diberikan ditulis dalam pseudo-code
Contoh
Constants
pi = 3.141592654
Variables
i, qty : integer
harga_satuan, harga_beli : real
status : boolean
nama : character(25)
Struktur Data
Kelompok item data yang terorganisasi yang dianggap sebagai suatu unit
Disebut juga sebagai jenis data kompleks (complex data type) atau data aggregates
Beberapa struktur data :
– Array (larik)
– String
– Record
– List (daftar)
– Tree
Array (Larik)
Set item data yang disusun secara baik menjadi rangkaian dan diacu atau ditunjuk oleh satu identifier
Contoh : Nilai = (56 42 89 65 48)
Item data individual dalam array bisa ditunjuk secara terpisah dengan menyatakan posisinya dalam array itu
– Nilai(1) menunjuk 56
– Nilai(2) menunjuk 42
Bilangan yang ditulis dalam tanda kurung menandakan posisi item individual dalam array (disebut juga subscript / indeks)
sumber :
openstorage.gunadarma.ac.id
Binary Tree adalah struktur data yang hampir mirip juga dengan Linked List untuk
menyimpan koleksi dari data. Linked List dapat dianalogikan sebagai rantai linier
sedangkan Binary Tree bisa digambarkan sebagai rantai tidak linier. Binary Tree
dikelompokkan menjadi unordered Binary Tree (tree yang tidak berurut) dan ordered
Binary Tree (tree yang terurut).
TREE adalah :
Kumpulan node yang saling terhubung satu sama lain dalam suatu kesatuan yang membentuk layakya struktur sebuah pohon.
Struktur pohon adalah suatu cara merepresentasikan suatu struktur hirarki (one-to-many) secara grafis yang mirip sebuah pohon, walaupun pohon tersebut hanya tampak sebagai kumpulan node-node dari atas ke bawah.
Suatu struktur data yang tidak linier yang menggambarkan hubungan yang hirarkis (one-to-many) dan tidak linier antara elemen-elemennya.
NPM : 10407113
Kelas : 3 Ib01 B
kuliah : Algoritma & pemrograman
Struktur data Objektif
• Mengetahui maksud struktur data dan menjelaskan penggunaannya dalam pemrograman
• Mengetahui operasi yang terkait dengan struktur data dan metode pemrograman paling umum yang terkait dengan struktur tersebut.
• Mengetahui metode dan notasi yang digunakan untuk menspesifikasi apa-apa yang perlu dikerjakan oleh program dan bagaimana program ini melakukan pekerjaan tersebut.
Jenis/Tipe Data (Data Type)
Terdiri dari
– Set nilai data
– Set operasi yang bisa diterapkan pada nilai tersebut.
Klasifikasi Jenis Data
Simple Data Type (Jenis Data Sederhana)
– Item data individual
Data Structures / data aggregates (struktur data)
– Kombinasi dari item data individual
– Membentuk item data lain
Jenis Data Sederhana
Numerik, terdiri dari :
– Numerik integer (bilangan bulat)
– Numerik real (bilangan riil)
Karakter, terdiri dari :
– Alfabet : a .. z, A .. Z
– Angka : 0 .. 9
– Simbol khusus : + ? ‘ ! [ ] { } … dll
Boolean (logika), terdiri dari :
– True
False
Identifier
Dalam bahasa pemrograman, item data diidentifikasi menurut namanya, bukan menurut alamat lokasinya dalam memori
Identifier akan merupakan konstanta jika ia selalu dikaitkan dengan nilai data yang sama
Identifier akan merupakan variabel jika nilai datanya yang terkait bisa berubah
Literal, nilai data yang tertera dalam program namun bukan sebagai identifier
Deklarasi Data
Jenis data konstanta dan variabel harus didefinisikan dalam program sehingga :
– operasi yang tepat dapat dijalankan pada nilai data dan
– Jumlah ruang penyimpanan yang tepat bisa ditentukan
Statement untuk mendefinisikan jenis data disebut declarative statement
Beberapa bahasa pemrograman memiliki sintaks pendeklarasian yang berbeda
Beberapa contoh program (pendeklarasian data) yang akan diberikan ditulis dalam pseudo-code
Contoh
Constants
pi = 3.141592654
Variables
i, qty : integer
harga_satuan, harga_beli : real
status : boolean
nama : character(25)
Struktur Data
Kelompok item data yang terorganisasi yang dianggap sebagai suatu unit
Disebut juga sebagai jenis data kompleks (complex data type) atau data aggregates
Beberapa struktur data :
– Array (larik)
– String
– Record
– List (daftar)
– Tree
Array (Larik)
Set item data yang disusun secara baik menjadi rangkaian dan diacu atau ditunjuk oleh satu identifier
Contoh : Nilai = (56 42 89 65 48)
Item data individual dalam array bisa ditunjuk secara terpisah dengan menyatakan posisinya dalam array itu
– Nilai(1) menunjuk 56
– Nilai(2) menunjuk 42
Bilangan yang ditulis dalam tanda kurung menandakan posisi item individual dalam array (disebut juga subscript / indeks)
sumber :
openstorage.gunadarma.ac.id
Binary Tree adalah struktur data yang hampir mirip juga dengan Linked List untuk
menyimpan koleksi dari data. Linked List dapat dianalogikan sebagai rantai linier
sedangkan Binary Tree bisa digambarkan sebagai rantai tidak linier. Binary Tree
dikelompokkan menjadi unordered Binary Tree (tree yang tidak berurut) dan ordered
Binary Tree (tree yang terurut).
TREE adalah :
Kumpulan node yang saling terhubung satu sama lain dalam suatu kesatuan yang membentuk layakya struktur sebuah pohon.
Struktur pohon adalah suatu cara merepresentasikan suatu struktur hirarki (one-to-many) secara grafis yang mirip sebuah pohon, walaupun pohon tersebut hanya tampak sebagai kumpulan node-node dari atas ke bawah.
Suatu struktur data yang tidak linier yang menggambarkan hubungan yang hirarkis (one-to-many) dan tidak linier antara elemen-elemennya.
teknik sorting
ALGORITMA SORTING
Sorting memiliki kepentingan tambahan bagi perancang algoritma paralel; ia sering
digunakan untuk melakukan permutasi data umum pada komputer dengan memori
terdistribusi. Operasi pemidahan data ini dpt digunakan untuk menyelesaikan masalah pada:
• teori graf
• geometri komputasional
• image processing
dalam waktu optimal atau hampir optimal.
Algoritma yang akan dipelajari berikut merupakan internal sort - yaitu, tabel yang di-sort
cukup kecil untuk masuk seluruhnya di memori primer. Semua algoritma berikut ini juga
men-sort dengan membandingkan sepasang elemen.
ENUMERATION SORT
Asumsi:
• Tabel dengan n elemen: a0, a1, ..., an-1
• Untuk 2 elemen ai dan aj, salah satu kondisi ini pasti benar: ai < aj, ai = aj, atau ai > aj.
• Tujuan sorting: menemukan permutasi (p0, p1, ..., pn-1) sedemikian sehingga ap0 = ap1 = ...
= apn-1.
Enumeration sort:
• menghitung posisi akhir setiap elemen pada list yang di-sort dan membandingkannya
dengan elemen lain dan menghitung jumlah elemen yang memiliki nilai lebih kecil.
• Jika j elemen memiliki nilai lebih kecil dari ai, maka pj=i; yaitu, elemen ai adalah (j + 1)
elemen pada list yang di-sort setelah ap0, ..., apj-1.
• Jika diberikan n2 prosesor, model CRCW PRAM dapat menghitung setiap pasang elemen
dan menghitung posisi list setiap elemen dalam waktu konstan. Begitu mesin telah
menghitung posisi setiap elemen, diperlukan satu langkah lagi untuk memindahkan
elemen ybs ke lokasi yang telah urut.
ENUMERATION SORT (SPECIAL CRCW PRAM):
Parameter n {number of elements}
Global a[0...(n-1)] {elements to be sorted}
position[0...(n-1)] {sorted positions}
sorted[0...(n-1)] {Contains sorted elements}
begin
spawn(Pi,j, for all 0 = i, j < n)
for a ll Pi,j, where 0 = i, j < n do
position[i] 0
if a[i] < a[j] or (a[i] = a[j] and i < j) then
position[i] 1
endif
endfor
for a ll Pi,0, where 0 = i < n do
sorted[position[i]] a[i]
endfor
end
Satu set n elemen dapat di-sort dalam waktu T(log n) dengan n2 prosesor, jika dipakai model
PRAM CRCW dengan write simultan ke lokasi memori yang sama menyebabkan jumlah
nilai di-assign. Jika waktu yang diperlukan untuk spawn prosesor tidak dihitung, algoritma
berjalan dengan waktu konstan.
BATAS BAWAH UNTUK PARALLEL SORTING
Teorema 1:
Anggap ada n elemen yang akan di-sort pada array prosesor yang disusun menjadi mesh satu
dimensi. Juga asumsikan bahwa sebelum dan sesudah sort, elemen akan didistribusikan
merata, satu elemen per prosesor. Dengan demikian, batas bawah kompleksitas waktu pada
algoritma sorting yang mana pun adalah T(n).
Bukti:
Lebar biseksi dari jaringan mesh satu dimensi adalah 1. Misalkan posisi yang ter-sort dari
semua elemen yang pada awalnya ada pada satu sisi biseksi adalah pada sisi biseksi yang
lain, dan sebaliknya. Maka seluruh n elemen harus melewati satu link untuk mencapai sisi
yang lain. Karena link hanya dapat membawa satu elemen sekali, jumlah langkah yang
diperlukan untuk menukar elemen melalui biseksi paling tidak adalah sebesar n. Dengan
demikian, batas bawah kompleksitas jaringan mesh satu dimensi dengan syarat-syarat
tersebut adalah T(n).
Teorema 2:
Anggap ada n elemen yang akan di-sort pada array prosesor yang tersusun sebagai mesh dua
dimensi. Juga anggap bahwa sebelum dan sesudah sort, elemen-elemen tsb terdistribusi
merata, satu elemen per prosesor. Maka, batas bawah kompleksitas waktu untuk algoritma
sorting yang mana pun adalah T(vn).
Bukti:
Lebar biseksi jaringan mesh dua dimensi dengan n node adalah lebih kecil atau sama dengan
vn . Misalkan posisi ter-sort dari semua elemen yang pada awalnya ada pada satu sisi
biseksi adalah di sisi lain biseksi tsb, dan sebaliknya. Maka seluruh n elemen harus melalui
salah satu dari tidak lebih vn link untuk mencapai sisi lainnya. Karena satu link hanya
dapat membawa satu elemen sekali, jumlah langkah yang diperlukan untuk menukar elemen
melintasi biseksi paling tidak adalah n/ vn . Dengan demikian, batas bawah kompleksitas
array prosesor bagaimanapun yang disusun sebagai mesh dua dimensi dan berjalan dengan
ketentuan yang telah diberikan di atas adalah T(n/ vn ) = T(vn)
Teorema 3:
Anggap ada n = 2k elemen yang akan di-sort pada array prosesor yang tersusun sebagai
jaringan shuffle-exchange. Juga anggap bahwa sebelum dan sesudah sort, elemen
terdistribusi merata, satu elemen per prosesor. Batas bawah untuk algoritma sort mana pun
adalah T(log n).
Bukti:
Misalkan posisi ter-sort elemen yang pada awalnya berada pada node 0 adalah node n-1.
Pemindahan elemen tsb dari node 0 ke node n-1 menuntut paling tidak log n operasi
pertukaran dan paling tidak log n-1 operasi shuffle. Dengan alasan ini, batas bawah pada
algoritma sorting berbassis shuffle-exchange dengan batas-batas di atas adalah T(log n).
Sorting adalah proses menyusun elemen – elemen dengan tata urut tertentu dan
proses tersebut terimplementasi dalam bermacam aplikasi. Kita ambil contoh pada
aplikasi perbankan. Aplikasi tersebut mampu menampilkan daftar account yang aktif.
Hampir seluruh pengguna pada sistem akan memilih tampilan daftar berurutan
secara ascending demi kenyamanan dalam penelusuran data.
Beberapa macam algoritma sorting telah dibuat karena proses tersebut sangat
mendasar dan sering digunakan. Oleh karena itu, pemahaman atas algoritma –
algoritma yang ada sangatlah berguna.
Setelah menyelesaikan pembahasan pada bagian ini, anda diharapkan mampu :
1. Memahami dan menjelaskan algoritma dari insertion sort, selection sort,
merge sort dan quick sort.
2. Membuat implementasi pribadi menggunakan algoritma yang ada
6.2 Insertion Sort
Salah satu algoritma sorting yang paling sederhana adalah insertion sort. Ide dari
algoritma ini dapat dianalogikan seperti mengurutkan kartu. Penjelasan berikut ini
menerangkan bagaimana algoritma insertion sort bekerja dalam pengurutan kartu.
Anggaplah anda ingin mengurutkan satu set kartu dari kartu yang bernilai paling
kecil hingga yang paling besar. Seluruh kartu diletakkan pada meja, sebutlah meja
ini sebagai meja pertama, disusun dari kiri ke kanan dan atas ke bawah. Kemudian
kita mempunyai meja yang lain, meja kedua, dimana kartu yang diurutkan akan
diletakkan. Ambil kartu pertama yang terletak pada pojok kiri atas meja pertama
dan letakkan pada meja kedua. Ambil kartu kedua dari meja pertama, bandingkan
dengan kartu yang berada pada meja kedua, kemudian letakkan pada urutan yang
sesuai setelah perbandingan. Proses tersebut akan berlangsung hingga seluruh kartu
pada meja pertama telah diletakkan berurutan pada meja kedua.
Algoritma insertion sort pada dasarnya memilah data yang akan diurutkan menjadi
dua bagian, yang belum diurutkan (meja pertama) dan yang sudah diurutkan (meja
kedua). Elemen pertama diambil dari bagian array yang belum diurutkan dan
kemudian diletakkan sesuai posisinya pada bagian lain dari array yang telah
diurutkan. Langkah ini dilakukan secara berulang hingga tidak ada lagi elemen yang
tersisa pada bagian array yang belum diurutkan.
Selection Sort
Jika anda diminta untuk membuat algoritma sorting tersendiri, anda mungkin akan
menemukan sebuah algoritma yang mirip dengan selection sort. Layaknya insertion
sort, algoritma ini sangat rapat dan mudah untuk diimplementasikan.
Mari kita kembali menelusuri bagaimana algoritma ini berfungsi terhadap satu paket
kartu. Asumsikan bahwa kartu tersebut akan diurutkan secara ascending. Pada
awalnya, kartu tersebut akan disusun secara linier pada sebuah meja dari kiri ke
kanan, dan dari atas ke bawah. Pilih nilai kartu yang paling rendah, kemudian
tukarkan posisi kartu ini dengan kartu yang terletak pada pojok kiri atas meja. Lalu
cari kartu dengan nilai paling rendah diantara sisa kartu yang tersedia. Tukarkan
kartu yang baru saja terpilih dengan kartu pada posisi kedua. Ulangi langkah –
langkah tersebut hingga posisi kedua sebelum posisi terakhir dibandingkan dan
dapat digeser dengan kartu yang bernilai lebih rendah
Ide utama dari algoritma selection sort adalah memilih elemen dengan nilai paling
rendah dan menukar elemen yang terpilih dengan elemen ke-i. Nilai dari i dimulai
dari 1 ke n, dimana n adalah jumlah total elemen dikurangi 1.
Algoritma
void selectionSort(Object array[], int startIdx, int endIdx) {
int min;
for (int i = startIdx; i < endIdx; i++) {
min = i;
for (int j = i + 1; j < endIdx; j++) {
if (((Comparable)array[min]).compareTo(array[j])>0) {
min = j;
}
}
swap(array[min], array[i]);
sumber :
www.gunadarma.ac.id
www.wikipedia.com
Sorting memiliki kepentingan tambahan bagi perancang algoritma paralel; ia sering
digunakan untuk melakukan permutasi data umum pada komputer dengan memori
terdistribusi. Operasi pemidahan data ini dpt digunakan untuk menyelesaikan masalah pada:
• teori graf
• geometri komputasional
• image processing
dalam waktu optimal atau hampir optimal.
Algoritma yang akan dipelajari berikut merupakan internal sort - yaitu, tabel yang di-sort
cukup kecil untuk masuk seluruhnya di memori primer. Semua algoritma berikut ini juga
men-sort dengan membandingkan sepasang elemen.
ENUMERATION SORT
Asumsi:
• Tabel dengan n elemen: a0, a1, ..., an-1
• Untuk 2 elemen ai dan aj, salah satu kondisi ini pasti benar: ai < aj, ai = aj, atau ai > aj.
• Tujuan sorting: menemukan permutasi (p0, p1, ..., pn-1) sedemikian sehingga ap0 = ap1 = ...
= apn-1.
Enumeration sort:
• menghitung posisi akhir setiap elemen pada list yang di-sort dan membandingkannya
dengan elemen lain dan menghitung jumlah elemen yang memiliki nilai lebih kecil.
• Jika j elemen memiliki nilai lebih kecil dari ai, maka pj=i; yaitu, elemen ai adalah (j + 1)
elemen pada list yang di-sort setelah ap0, ..., apj-1.
• Jika diberikan n2 prosesor, model CRCW PRAM dapat menghitung setiap pasang elemen
dan menghitung posisi list setiap elemen dalam waktu konstan. Begitu mesin telah
menghitung posisi setiap elemen, diperlukan satu langkah lagi untuk memindahkan
elemen ybs ke lokasi yang telah urut.
ENUMERATION SORT (SPECIAL CRCW PRAM):
Parameter n {number of elements}
Global a[0...(n-1)] {elements to be sorted}
position[0...(n-1)] {sorted positions}
sorted[0...(n-1)] {Contains sorted elements}
begin
spawn(Pi,j, for all 0 = i, j < n)
for a ll Pi,j, where 0 = i, j < n do
position[i] 0
if a[i] < a[j] or (a[i] = a[j] and i < j) then
position[i] 1
endif
endfor
for a ll Pi,0, where 0 = i < n do
sorted[position[i]] a[i]
endfor
end
Satu set n elemen dapat di-sort dalam waktu T(log n) dengan n2 prosesor, jika dipakai model
PRAM CRCW dengan write simultan ke lokasi memori yang sama menyebabkan jumlah
nilai di-assign. Jika waktu yang diperlukan untuk spawn prosesor tidak dihitung, algoritma
berjalan dengan waktu konstan.
BATAS BAWAH UNTUK PARALLEL SORTING
Teorema 1:
Anggap ada n elemen yang akan di-sort pada array prosesor yang disusun menjadi mesh satu
dimensi. Juga asumsikan bahwa sebelum dan sesudah sort, elemen akan didistribusikan
merata, satu elemen per prosesor. Dengan demikian, batas bawah kompleksitas waktu pada
algoritma sorting yang mana pun adalah T(n).
Bukti:
Lebar biseksi dari jaringan mesh satu dimensi adalah 1. Misalkan posisi yang ter-sort dari
semua elemen yang pada awalnya ada pada satu sisi biseksi adalah pada sisi biseksi yang
lain, dan sebaliknya. Maka seluruh n elemen harus melewati satu link untuk mencapai sisi
yang lain. Karena link hanya dapat membawa satu elemen sekali, jumlah langkah yang
diperlukan untuk menukar elemen melalui biseksi paling tidak adalah sebesar n. Dengan
demikian, batas bawah kompleksitas jaringan mesh satu dimensi dengan syarat-syarat
tersebut adalah T(n).
Teorema 2:
Anggap ada n elemen yang akan di-sort pada array prosesor yang tersusun sebagai mesh dua
dimensi. Juga anggap bahwa sebelum dan sesudah sort, elemen-elemen tsb terdistribusi
merata, satu elemen per prosesor. Maka, batas bawah kompleksitas waktu untuk algoritma
sorting yang mana pun adalah T(vn).
Bukti:
Lebar biseksi jaringan mesh dua dimensi dengan n node adalah lebih kecil atau sama dengan
vn . Misalkan posisi ter-sort dari semua elemen yang pada awalnya ada pada satu sisi
biseksi adalah di sisi lain biseksi tsb, dan sebaliknya. Maka seluruh n elemen harus melalui
salah satu dari tidak lebih vn link untuk mencapai sisi lainnya. Karena satu link hanya
dapat membawa satu elemen sekali, jumlah langkah yang diperlukan untuk menukar elemen
melintasi biseksi paling tidak adalah n/ vn . Dengan demikian, batas bawah kompleksitas
array prosesor bagaimanapun yang disusun sebagai mesh dua dimensi dan berjalan dengan
ketentuan yang telah diberikan di atas adalah T(n/ vn ) = T(vn)
Teorema 3:
Anggap ada n = 2k elemen yang akan di-sort pada array prosesor yang tersusun sebagai
jaringan shuffle-exchange. Juga anggap bahwa sebelum dan sesudah sort, elemen
terdistribusi merata, satu elemen per prosesor. Batas bawah untuk algoritma sort mana pun
adalah T(log n).
Bukti:
Misalkan posisi ter-sort elemen yang pada awalnya berada pada node 0 adalah node n-1.
Pemindahan elemen tsb dari node 0 ke node n-1 menuntut paling tidak log n operasi
pertukaran dan paling tidak log n-1 operasi shuffle. Dengan alasan ini, batas bawah pada
algoritma sorting berbassis shuffle-exchange dengan batas-batas di atas adalah T(log n).
Sorting adalah proses menyusun elemen – elemen dengan tata urut tertentu dan
proses tersebut terimplementasi dalam bermacam aplikasi. Kita ambil contoh pada
aplikasi perbankan. Aplikasi tersebut mampu menampilkan daftar account yang aktif.
Hampir seluruh pengguna pada sistem akan memilih tampilan daftar berurutan
secara ascending demi kenyamanan dalam penelusuran data.
Beberapa macam algoritma sorting telah dibuat karena proses tersebut sangat
mendasar dan sering digunakan. Oleh karena itu, pemahaman atas algoritma –
algoritma yang ada sangatlah berguna.
Setelah menyelesaikan pembahasan pada bagian ini, anda diharapkan mampu :
1. Memahami dan menjelaskan algoritma dari insertion sort, selection sort,
merge sort dan quick sort.
2. Membuat implementasi pribadi menggunakan algoritma yang ada
6.2 Insertion Sort
Salah satu algoritma sorting yang paling sederhana adalah insertion sort. Ide dari
algoritma ini dapat dianalogikan seperti mengurutkan kartu. Penjelasan berikut ini
menerangkan bagaimana algoritma insertion sort bekerja dalam pengurutan kartu.
Anggaplah anda ingin mengurutkan satu set kartu dari kartu yang bernilai paling
kecil hingga yang paling besar. Seluruh kartu diletakkan pada meja, sebutlah meja
ini sebagai meja pertama, disusun dari kiri ke kanan dan atas ke bawah. Kemudian
kita mempunyai meja yang lain, meja kedua, dimana kartu yang diurutkan akan
diletakkan. Ambil kartu pertama yang terletak pada pojok kiri atas meja pertama
dan letakkan pada meja kedua. Ambil kartu kedua dari meja pertama, bandingkan
dengan kartu yang berada pada meja kedua, kemudian letakkan pada urutan yang
sesuai setelah perbandingan. Proses tersebut akan berlangsung hingga seluruh kartu
pada meja pertama telah diletakkan berurutan pada meja kedua.
Algoritma insertion sort pada dasarnya memilah data yang akan diurutkan menjadi
dua bagian, yang belum diurutkan (meja pertama) dan yang sudah diurutkan (meja
kedua). Elemen pertama diambil dari bagian array yang belum diurutkan dan
kemudian diletakkan sesuai posisinya pada bagian lain dari array yang telah
diurutkan. Langkah ini dilakukan secara berulang hingga tidak ada lagi elemen yang
tersisa pada bagian array yang belum diurutkan.
Selection Sort
Jika anda diminta untuk membuat algoritma sorting tersendiri, anda mungkin akan
menemukan sebuah algoritma yang mirip dengan selection sort. Layaknya insertion
sort, algoritma ini sangat rapat dan mudah untuk diimplementasikan.
Mari kita kembali menelusuri bagaimana algoritma ini berfungsi terhadap satu paket
kartu. Asumsikan bahwa kartu tersebut akan diurutkan secara ascending. Pada
awalnya, kartu tersebut akan disusun secara linier pada sebuah meja dari kiri ke
kanan, dan dari atas ke bawah. Pilih nilai kartu yang paling rendah, kemudian
tukarkan posisi kartu ini dengan kartu yang terletak pada pojok kiri atas meja. Lalu
cari kartu dengan nilai paling rendah diantara sisa kartu yang tersedia. Tukarkan
kartu yang baru saja terpilih dengan kartu pada posisi kedua. Ulangi langkah –
langkah tersebut hingga posisi kedua sebelum posisi terakhir dibandingkan dan
dapat digeser dengan kartu yang bernilai lebih rendah
Ide utama dari algoritma selection sort adalah memilih elemen dengan nilai paling
rendah dan menukar elemen yang terpilih dengan elemen ke-i. Nilai dari i dimulai
dari 1 ke n, dimana n adalah jumlah total elemen dikurangi 1.
Algoritma
void selectionSort(Object array[], int startIdx, int endIdx) {
int min;
for (int i = startIdx; i < endIdx; i++) {
min = i;
for (int j = i + 1; j < endIdx; j++) {
if (((Comparable)array[min]).compareTo(array[j])>0) {
min = j;
}
}
swap(array[min], array[i]);
sumber :
www.gunadarma.ac.id
www.wikipedia.com
Langganan:
Postingan (Atom)
