Pengurutan data adalah algoritma yang meletakkan elemen pada sebuah list atau tabel dengan urutan tertentu. Algoritma pengurutan data saat ini telah demikian banyaknya, mulai dari yang sederhana sampai yang kompleks. Untuk saat ini, algoritma heap sort dan quicksort merupakan dua buah algoritma yang dianggap terbaik.
Penggunaan algoritma heap sort dan quick sort dalam pengurutan data berbeda. Perbedaan ini dipengaruhi oleh keunggulan dan kelemahan masing-masing algoritma pengurutan.
Algoritma Heap Sort dan Quick Sort
1. Heap Sort
Heapsort merupakan salah satu bentuk dari selection sort yang memiliki kompleksitas algorima O(n log(n)) yang menggunakan struktur data heap.
Algoritma ini bekerja dengan menentukan elemen terbesar (atau terkecil) dari sebuah daftar elemen, dan diletakkan pada akhir (atau awal) dari daftar tersebut. Heap sort menyelesaikan sebuah pengurutan menggunakan struktur data yang disebut heap.
Heap merupakan sebuah pohon biner hampir lengkap dimana isi dari simpul ayah selalu lebih besar dari isi simpul anak-anaknya sehingga simpul akar selalu merupakan elemen terbesar.
2. Quick Sort
Quick sort adalah algoritma yang menggunakan metode divide and qonquer yaitu dengan mempartisi tabel dengan acuan elemen tabel yang dijadikan sebagai pivot. Tabel dipartisi menjadi tabel dengan elemen pivot, <> pivot, hingga elemen tersebut terurut. pengurutan hanya dengan 1 kali pass saja. Namun sampai saat ini, belum ada algoritma yang mampu untuk mencapai keadaan ini.
Kompleksitas waktu dari kedua algoritma ini, secara rata-rata adalah sama, yaitu O(n log n). Saat ini, kompleksitas waktu O(n log n) merupakan kompleksitas algoritma sorting yang paling mendekati algoritma pengurutan ideal yaitu O(n). Hal inilah yang menyebabkan kedua buah algoritma ini dipandang sebagai yang terbaik saat ini.
Walaupun memiliki kompleksitas algoritma yang sama yaitu O(n log n), dalam praktiknya, algoritma quicksort memiliki kecepatan pemrosesan yang lebih baik dari heap sort. Penyebabnya adalah algoritma heapsort membutuhkan tahapan-tahapan yang lebih banyak daripada quicksort.
Namun untuk quicksort, pada kasus terburuknya memiliki kompleksitas O(n2). Sedangkan, pada heap sort, kompleksitas untuk kasus terburuknya sama dengan kasus rata-rata, yaitu O(n log n). Jadi pada kasus terburuk, algoritma heap sort lebih baik daripada algoritma quicksort.
Klasifikasi AlgoritmaPengurutan (sorting)
* Exchange Sort : Melakukan pembandingan antar data, dan melakukan pertukaran apabila urutan yang didapat belum sesuai. Contohnya : Bubble sort, Cocktail sort, Comb sort, Gnomesort, Quicksort.
* Selection Sort : Mencari elemen yang tepat untuk diletakkan diposisi yang telah diketahui, dan meletakkannyadi posisi tersebut setelah data tersebutditemukan. Contohnya :Selection sort, Heapsort, Smoothsort, Strand sort
* Insertion Sort : Mencari tempat yang tepat untuk suatu elemen data yang telah diketahui ke dalam sub kumpulan data yang telah terurut, kemudian melakukan penyisipan (insertion) data di tempat yang tepat tersebut. Contohnya adalah : Insertion sor, Shell sort, Tree sort, Library sort, Patience sorting.
* Merge Sort : Data dibagi menjadi subkumpulan-subkumpulan yang kemudian subkumpulan tersebut diurutkan secara terpisah, dan kemudian digabungkan kembali dengan metode merging. Algoritma ini melakukan metode pengurutan merge sort juga untuk mengurutkan sub kumpulan data tersebut, atau dengan kata lain, pengurutan dilakukan secara rekursif. Contohnya adalah : Merge sort.
* Non-Comparison Sort : Proses pengurutan data yang dilakukan algoritma ini tidak terdapat pembandingan antar data, data diurutkan sesuai dengan pigeon hole principle. Contohnya adalah : Radix sort, Bucket sort, Counting sort, Pigeonhole sort, Tally sort.
Ide Dasar
Ide dasar dari metode Radix sort ini adalah mengkategorikan data-data menjadi sub kumpulan sub kumpulan data sesuai dengan nilai radix-nya, mengkonkatenasinya, kemudian mengkategorikannya kembali berdasar nilai radix lainnya.
Algoritma Bubble Sort
1. Setiap pasangan data: x[j] dengan x[j-1], untuk semua i=1,...,n-1 harus memenuhi keterurutan, yaitu x[j] > x[j-1].
2. Apabila tidak memenuhi maka posisi kedua data harus ditukar.
3. Untuk pemrograman konvensional maka pemeriksaan-pemeriksaan pasangan tersebutharus dilakukan satu demi satu, misalnya oleh bubble-sort dilakukan dari kanan ke kiri serta di dalam sejumlah iterasi.
4. Keuntungan lain dari algoritma ini adalah dapat dijalankan dengan cukup cepat dan efisien untuk mengurutkan list yang urutannya sudah hampir benar.
5. Selain kasus terbaik tersebut, komleksitas untuk algoritma ini adalah O(n²), karenanya algoritma ini termasuk sangat tidak efisien untuk dilakukan, apalagi jika pengurutan dilakukan terhadap elemen yang banyak jumlahnya. Biasanya bubble sort digunakan untuk mengenalkan konsep dari sorting algoritma pada pendidikan komputer karena idenya yang cukup sederhana.
* Metode Selection Short
Metode selection sort merupakan perbaikan dari metode bubble sort dengan mengurangi jumlah perbandingan. Selection sort merupakan metode pengurutan yang mencari nilai data terbesar atau terkecil dan kemudian menempatkannya pada posisi yang sebenarnya, dimulai dari data diposisi 0 hingga data diposisi N-1.
* Metode Insertion Short
Metode insertion sort adalah metode pengurutan yang biasa dipakai oleh pemain kartu dalam mengurutkan kartunya, yaitu menyisipkan kartu dengan nilai yang lebih kecil ke posisi sebelum kartu pembandingnya. Selection Sort merupakan kombinasi antara sorting dan searching. Untuk setiap proses, akan dicari elemen-elemen yang belum diurutkan yang memiliki nilai terkecil atau terbesar
kan dipertukarkan ke posisi yang tepat di dalam array. Misalnya untuk putaran pertama, akan dicari data dengan nilai terkecil dan data ini akan ditempatkan di indeks terkecil (data[0]), pada putaran kedua akan dicari data kedua terkecil, dan akan ditempatkan di indeks kedua (data[1]). Selama proses, pembandingan dan pengubahan hanya dilakukan pada indeks pembanding saja, pertukaran data secara fisik terjadi pada akhir proses.Tehnik pengurutan dgn cara pemilihan elemen atau proses kerja dgnmemilih elemen data terkecil utk kemudian dibandingkan & ditukarkan dgn elemen pd data awal, dst s/d seluruh elemen shg akan menghasilkan pola data yg telah disort.
Kelebihan dan kekurangan Selection Sort:
1. Kompleksitas selection sort relatif lebih kecil
2. Mudah menggabungkannya kembali, tetapi sulit membagi masalah
3. Membutuhkan method tambahan.
* Metode Insertion Sort
Prinsip dasar Insertion adalah secara berulangulang menyisipkan / memasukan setiap elemen. ke dlm posisinya / tempatnya yg benar. Mirip dengan cara orang mengurutkan kartu, selembar demi selembar kartu diambil dan disisipkan (insert) ke tempat yang seharusnya. Pengurutan dimulai dari data ke-2 sampai dengan data terakhir, jika ditemukan data yang lebih kecil, maka akan ditempatkan (diinsert) diposisi yang seharusnya. Pada penyi sipan elemen, maka elemen-elemen lain akan bergeser ke belakang.
* Quick Short : Quick sort banyak digunakan utk proses sorting, karena merupakan proses sorting yang umum digunakan, mudah untuk diimplementasikan, prosesnya sangat cepat.
Aturan Quick Sort:
1. Select, pertama kita pilih elemen yang ditengah sebagai pivot, misalkan X.
2. Partition, kemudian semua elemen tersebut disusun dengan menempatkanX mpada posisi j sedemikian rupa sehingga elemen disebelah kiri1 lebih <> X.
3. Rekursif, kemudian proses diulang untuk bagian kiri dan kanan elemenX dengan cara yg sama dengan langkah 1 sampai kondisi terurut
* Metode Heap Short adalah binary tree dengan menggunakan tree , dimana mempunyai aturan-aturan sebagai berikut :
1. Untuk mengisikan heap dimulai dari level 1 sampai ke level dibawahnya, bila dalam level yang sama semua kunci heap belum terisi maka tidak boleh mengisi dibawahnya.
2. Heap dlm kondisi terurut apabila left child <> parent.
3. Penambahan kunci diletakkan pada posisi terakhir dari level dan disebelah kanan child yg terakhir, kemudian diurutkan dengan cara upheap.
4. Bila menghapus heap dgn mengambil kunci pada parent di level 1 kemudian digantikan posisi kunci terakhir, selanjutnya disort kembali metode downheap.
Labels
- Cari duwit lewat internet (2)
- Info IT (2)
- Internet (2)
- Islam (1)
- Kesehatan (1)
- Materi kuliah (7)
- Music (1)
- Networking (2)
- photoshop (6)
- Programing (5)
- Software (2)
- software dan driver (2)
- Tips Dan Trik (15)
Blog Archive
-
▼
2010
(42)
-
▼
Februari
(37)
- "SIN" ROKOK YANG MENYEHATKAN for everyone Komposis...
- Membuat “Real” Tatoo
- Membuat Efek Cinema pada Foto Saya suka bang...
- Membuat Efek Reflection Atau Bayangan Cermin denga...
- Desain Kartu Kredit dengan Photoshop
- Download eBook 1000 Hacking Tutorial
- Hacking Facebook Using Fake Login
- Facebook Hack Tool
- Menggunakan Google dengan Javascript
- Membuat Folder Pribadi Tanpa Menggunakan Software
- PENGURUTAN DATA
- STATEMENT - STATEMENT PEMROGRAMAN PASCAL
- Cara Memasang Kabel UTP Tipe Straight dan Cross
- Hemi-Sync - Metamusic - The Visitation
- Memasang Iklan Google Adsense Pada Blog
- Usaha Saya Sebagai Publisher Adsense
- Situs-situs terbaik penyedia driver komputer
- Atasi masalah pada data di harddisk anda (Windows ...
- Update Windows 7 Terbaru Akan Kenali Crack OS Illegal
- Asesoris mempercantik Blog
- Kumpulan link download WIFItool
- -- Melumpuhkan Access Point dengan Void11 --
- Bagaimana Cara Mengamankan W-LAN ???
- Driver Epson R230
- Pengulangan (ALGORITMA)
- Contoh Soal
- Kumpulan Program Pascal
- Meningkatkan Kecepatan Koneksi Internet dengan Dns...
- BERSIN DAN MENGUAP
- SIFAT TRANSISTOR & TRANSISTOR PADA FREKUENSI REND...
- RANGKAI TRANSISTOR
- TRANSISTOR SEBAGAI SUATU AMPLIFIER
- Transistor FET - JFET dan MOSFET
- Melakukan Perbaikan dan atau Setting Ulang Koneksi...
- PROSEDUR INSTALASI WIRELESS WAN
- Hacking Wireless Hotspot
- Membuat Blog Itu Mudah
-
▼
Februari
(37)
Rabu, 17 Februari 2010
Posted in |
Programing
|
0 Comments »
About Me
- Arif Fatkur Rahman
- saya adalah seorang yang haus akan ilmu pengetahuan, bagi saya menuntut ilmu adalah wajib tak kenal umur dan waktu dimanapun kapanpun...
One Responses to "PENGURUTAN DATA"