Kaito Project

Macam-macam Sorting.

            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 secaraascending demi kenyamanan dalam penelusuran data. Beberapa macam algoritmasorting telah dibuat karena proses tersebut sangat mendasar dan sering digunakan. Oleh karena itu, pemahaman atas algoritma – algoritma yang ada sangatlah berguna.

Ide utama dari algoritma selection sort adalah memilih elemen dengan nilai paling rendah dan menukar elemen yang terpilih dengan elemen ke-i. Nilai dari idimulai dari 1 ke n, dimana n adalah jumlah total elemen dikurangi 1.

 Proses pengurutan dengan menggunakan metode selection sort secara terurut naik adalah:

·       Mencari data terkecil dari data pertama sampai data terakhir, kemunian di tukar posisinya dengan data pertama

·       Mencari data terkecil dari data kedua sampai data terakhir, kemudian di tukar dengan posisinya dengan data kedua.

·       Mencari data terkecil dari data ketiga sampai data terakhir, kemudian di tukar posisinya dengan data ketiga

·       Dan seterusnya sampai semua data turut naik. apabila terdapat n buah data yang akan di urutkan, maka membutukan (n - 1) langkah pengurutan, dimana data terakhir yaitu data ke-n tidak perlu di urutkan karena hanya tinggal satu satunya.

Contoh:

Konsep Buble Sort

Merupakan algoritma pengurutan paling tua dengan metode pengurutan paling sederhana. Metode pengurutan gelembung (Bubble Sort) diinspirasikan oleh gelembung sabun yang berada dipermukaan air. Karena berat jenis gelembung sabun lebih ringan daripada berat jenis air, maka gelembung sabun selalu terapung ke atas permukaan. Prinsip di atas dipakai pada pengurutan gelembung.

Bubble sort (metode gelembung) adalah metode/algoritma pengurutan dengan dengan cara melakukan penukaran data dengan tepat disebelahnya secara terus menerus sampai bisa dipastikan dalam satu iterasi tertentu tidak ada lagi perubahan. Jika tidak ada perubahan berarti data sudah terurut. Disebut pengurutan gelembung karena masing-masing kunci akan dengan lambat menggelembung ke posisinya yang tepat contoh kasus bubble sort. 

Contoh :

Algoritma insertion sort pada dasarnya memilah data yang akan diurutkan menjadi dua bagian, yang belum diurutkan dan yang sudah diurutkan. 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.

Ilustrasi: :

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 sebelahkiri, maka ambil kartu tersebut dan sisipkan di tempat yang sesuai.

Contoh:

  Metode penggabungan biasanya digunakan pada pengurutan berkas. Prinsip dari metode penggabungan sebagai berikut : mula-mula diberikan dua kumpulan data yang sudah dalam keadaan urut. Kedua kumpulan data tersebut harus dijadikan satu table sehingga dalam keadaan urut.

Contoh:

Algoritma sortir yang efisien yang ditulis oleh C.A.R. Hoare pada 1962. Dasar strateginya adalah “memecah dan menguasai”. Quicksort dimulai dengan menscan daftar yang disortir untuk nilai median. Nilai ini, yang disebut tumpuan (pivot), kemudian dipindahkan ke satu sisi pada daftar dan butir-butir yang nilainya lebih besar dari tumpuan di pindahkan ke sisi lain.

Contoh:

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

Contoh:

Ide dasar dari metode Radix sort ini adalah mengkategorikan data-data menjadi sub kumpulan subkumpulan data sesuai dengan nilai radix-nya, mengkonkatenasinya, kemudian mengkategorikannya kembali berdasar nilai radix

Contoh:

Bucket sort adalah algoritma sorting yang bekerja dengan partisi array ke dalam jumlah terbatas sort. Setiap kotak ini kemudian diurutkan secara individual, baik menggunakan algoritma sorting yang berbeda, atau dengan rekursif menerapkan algoritma bucket sort. Sebuah variasi dari metode ini disebut semacam hitungan tunggal buffered lebih cepat dari jenis cepat dan membutuhkan waktu sekitar waktu yang sama untuk berjalan pada set data.

Algoritma:

Merupakan satu bentuk dari selection sort yang memiliki kompleksitas algoritma O (n log(n) ) yang menggunakan struktur data heap. Heap sort bekerja dengan menentukan elemen terbesar (atau terkecil) dari sebuah susunan elemen, dan diletakkan pada akhir (atau awal) dari daftar tersebut. Algoritma:

Pembahasan yang kedua mengenai Metode Exchange Sort. Metode ini merupakan metode pengurutan data yang hampir mirip dengan Bubble Sort ( Mirorr-Nya buble sort), bahkan mungkin juga metode Bubble Sort sama dengan Exchange Sort. Namun setiap metode pasti memiliki perbedaan, perbedaan antara Exchange Sort dan Bubble Sort terletak dalam hal bagaimana membandingkan antar elemen-elemennya.

Exchange sort membandingkan suatu elemen dengan elemen-elemen lainnya dalam array tersebut, dan melakukan pertukaran elemen jika perlu. Jadi ada elemen yang selalu menjadi elemen pusat (pivot). Sedangkan Bubble sort akan membandingkan elemen pertama/terakhir dengan elemen sebelumnya/sesudahnya, kemudian elemen tersebut itu  Untuk setiap proses, akan dilakukan dengan mencari elemen dari posisi yang belum diurutkan dan kemudian memilih elemen yang memiliki nilai terkecil atau terbesar yang akan ditukarkan ke posisi yang tepat di dalam array.

Misalnya untuk putaran pertama, akan dicari data dengan nilai terkecil dan data ini akan ditempatkan pada indeks terkecil, pada putaran kedua akan dicari data kedua terkecil, dan akan ditempatkan di indeks kedua, negitu seterusnya hingga tidak ada data yang dicari lagi.

Selama proses, pembandingan dan pengubahan hanya dilakukan pada indeks pembanding saja, pertukaran data secara fisik terjadi pada akhir proses.

Perbedaannya: dalam exchange sort ada elemen yang berfungsi sebagai pusat (pivot), pertukaran hanya akan dilakukan jika diperlukan saja dari pivot tersebut. Sedangkan bubble sort akan membandingkan elemen pertama/terakhir dengan elemen sebelumnya/sesudahnya, kemudian elemen sebelum/sesudahnya itu akan menjadi pusat (pivot) untuk dibandingkan dengan elemen sebelumnya/sesudahnya lagi, begitu seterusnya.

Contoh fungsi exchange sort:

11.  Tree Sort

Tree sort adalah metode sorting dengan cara membangun pohon biner dengan menampilkan 3 hasik output: PreOrder,InOrder,PostOrder.

Konsep dan Algoritma:

Konsep dasar dari tree sort adalah sebagaimana sebuah pohon, ada akar, batang, ranting, daun, dsb. Dalam tree sort ada istilah akar atau root dan daun atau leaf. 

Perhatikan gambar di bawah ini.

Ketentuan dari gambar diatas adalah :

1.  menjadi akar ,
2.  menjadi subtree kiri,
3.  menjadi subtree kanan,
4 & 5. menjadi daun dari subtree kiri ,
6. menjadi daun dari subtree kanan.

Setiap objek dalam pohon biner berisi dua pointer, biasanya disebut kiri dan kanan. Selain pointer ini tentu saja node dapat berisi tipe data lainnya. Misalnya, pohon biner integer bisa terdiri dari objek dari jenis berikut:

       struct Node {

           int item; / / Data dalam node ini.

           Node *kiri; / / Pointer ke subtree kiri.

           Node * kanan; / / ​​Pointer ke subtree kanan.

       }

http://agusjembung.blogspot.com/2012/02/macam-macam-sorting.html
http://includeryokom.blogspot.com/2012/04/jenis-jenis-penyortiran-beserta.html
http://myinspiration023.blogspot.com/

Minggu, 5 April 2015 / 20.03