Sorting (Pengurutan)
Pengertian Sorting:
Proses pengurutan data banyak ditemukan dalam komputer. Hal ini karena data yang sudah di susun atau di urut lebih mudah di cari dengan cepat. Untuk membentuk data yg tidak terurut menjadi data yang urut, terdapat berbagai algoritma yang bisa di gunakan. Pada pengurutan data terdapat beberapa istilah, yaitu pengurutan ascending dan descending
Pengurutan dengan dasar dari nilai yang kecil menuju ke nilai yang besar (urutan naik)
Pengurutan data yang disusu atas dasar nilai besar ke kecil (urutan turun ).
Metode Shell Sort ( Pengurutan Cangkang )
Shell sort adalah algoritma dengan kompleksitas algoritma 0 (n ^ 2) dan yang paling efisien jika disbanding algoritma lain dengan kompleksitas yang sama. Algoritma shell sort lima kali lebih cepat dibandingkan algoritma pengurutan gelembung dan dua kali lebih cepat di bandingkan algoritma pengurutan dengan penyisipan. Dan tentu saja shell sort juga merupakan algoritma yang paling kompleks dan sulit dipahami.
Algoritma Shell sort melakukan pass atau traversal berkali-kali dan setiap kali pass mengurutkan sejumlah nilai yang sama dengan ukuran set menggunakan insertion set. Ukuran dari set yang harus diurutkan semakin membesar setiap kali melakukan pada tabel,sampai set tersebut mancakup seluruh elemen tabel. Ketika ukuran dari set semakin membesar, sejumlah nilai yang harus diurutkan semakin mengecil. Ini menyebabkan insertion sort yang dijalankan mengalami kasus terbaik dengan kompleksitas algoritma mendekati 0(n). Ikuran dari set yang digunakan untuk setiap kali iterasi ( iteration ) mempunyai efek besar terhadap efisiensi pengurutan.
Tetapi, walaupun tidak se-efisien algoritma merge sort, heap sort, atau quick sort , algoritma shell sort adalah algoritma yang relative sederhana. Hal ini menjadikan algritma shell sort adalah pilihan yang baik dan efisien untuk mengurutkan nilai dalam suatu table berukuran sedang ( mengandung 500 – 5000 elemen ).
Metode Quick Sort
Quick sort juga disebut juga dengan partition Exchange sort. Disebut Quick Sort, karena terbukti mempunyai "average behaviour" yang terbaik di antara metode pengurutan yang lain. Disebut Partition Exchange Sort karena konsepnya membuat partisi-partisi, dan pengurutan dilakukan perpartisi.
1) Pilih x E {a1, a2, ..., an} sebagai elemen pivot(median).
2) Pindai tabel dari kiri sampai ditemukan elemen ap E x.
3) Pindai tabel dari kanan sampai ditemukan elemen aq ≤ x.
4) Pertukarkan ap <-> aq (v) ulangi (ii) dari posisi p+1.
5) Dari posisi q-1, sampai kedua pemindaian bertemu di tengah tabel.
Langkah pertama : Tentukan pivot(median), awal=p dan akhir=q.
Apakah nilai p lebih kecil pivot dan q lebih besar pivot. Jika ya increment(p) dan decrement(q), sampai nilai p lebih besar pivot dan q lebih kecil pivot.
Kemudian tukarkan nilai p ke q.
Lakukan lagi, sampai p lebih besar q (berhenti). Berikutnya untuk partisi sebelah kiri:
Tentukan pivot(median), awal=p dan akhir=q.
Apakah nilai p lebih kecil pivot dan q lebih besar pivot. Jika ya increment(p) dan decrement(q), sampai nilai p lebih besar pivot dan q lebih kecil pivot.
Kemudian tukarkan nilai p ke q.
Lakukan lagi, sampai p lebih besar q (berhenti). Berikutnya untuk partisi sebelah kiri:
Tentukan pivot(median), awal=p dan akhir=q.
Apakah nilai p lebih kecil pivot dan q lebih besar pivot. Jika ya increment(p) dan decrement(q), sampai nilai p lebih besar pivot dan q lebih kecil pivot.
Data telah terurut.
Metode Heap Sort
Heap adalah sebuah binary tree dengan ketentuan sebagai berikut :
1. Tree harus complete binary tree
· Semua level tree mempunyai simpul maksimum kecuali pada level terakhir.
· Pada level terakhir, node tersusun dari kiri ke kanan tanpa ada yang dilewati.
2. Perbandingan nilai suatu node dengan nilai node child-nya mempunyai ketentuan berdasarkan jenis heap, diantaranya :
· Max Heap mempunyai ketentuan bahwa nilai suatu node lebih besar atau sama dengan ( >= ) dari nilai childnya.
· Min Heap mempunyai ketentuan bahwa nilai suatu node lebih kecil atau sama dengan ( <= ) dari nilai childnya.
Contoh :
Contoh heap maksimum ( Max Heap )
Contoh heap minimum ( Min Heap )
Heap dan Operasinya
Contoh penggunaan heap adalah pada persoalan yang mempertahankan antrian prioritas (priority queue). Dalam antrian prioritas, elemen yang dihapus adalah elemen yang mempunyai prioritas terbesar (atau terkecil, tergantung keperluan), dan elemen inilah yang selalu terletak di akar (root). Suatu heap dapat sewaktu-waktu berubah baik itu penambahan elemen (insert) dan penghapusan elemen (delete).
Ada beberapa operasi yang dapat terjadi di sebuah heap, yaitu :
1. Reorganisasi Heap (mengatur ulang heap).
2. Membantuk Heap (mengatur binary tree agar menjadi heap).
3. Penyisipan Heap (menyisipkan node baru).
4. Penghapusan Heap (menghapus node root).
5. Pengurutan Heap (Heap sort)
Tidak ada komentar:
Posting Komentar