This is default featured slide 2 title

Go to Blogger edit html and find these sentences.Now replace these sentences with your own descriptions.

This is default featured slide 3 title

Go to Blogger edit html and find these sentences.Now replace these sentences with your own descriptions.

This is default featured slide 4 title

Go to Blogger edit html and find these sentences.Now replace these sentences with your own descriptions.

This is default featured slide 5 title

Go to Blogger edit html and find these sentences.Now replace these sentences with your own descriptions.

Sabtu, 04 April 2015

5 Metode dalam Teknik Sorting


1.       Pengurutan berdasarkan penyisipan dan penjagaan terurut (insert and keep sorted method)
·         Insertion sort
Teknik sorting ini dibuat dengan cara menyisipkan atau memasukkan satu-persatu, bila kita akan mengurutkan data, kemudian ingin menyisipkan suatu data maka data tersebut akan otomatis masuk dimana dia berada.Pengurutan dilakukan dengan cara membandingkan data ke – i dengan data berikutnya, (dimana i dimulai dari data di index ke 1 sampai dengan data terakhir). Jika ditemukan data yang lebih kecil maka data tersebut disisipkan ke depan sesuai dengan posisi yang seharusnya, dan saat ada elemen yang disispkan, maka elemen-elemen lainnya akan bergeser kebelakang.
Contoh procedure insertion sort ascending :
Procedure asc_insert;
Var
i, j, temp : byte;
begin
for i := 2 to max do
begin
temp := data [i] ;
j :=i-1;
while (data [j] > temp ) and (j>0) do
begin
data [j+1] := data [j];
dec (j) ;
end;
data [j+1] := temp ;
end;
end;

·         Tree sort
Metode sorting dengan cara membangun pohon biner dengan menampilkan 3 hasil output: PreOrder, InOrder, dan PostOrder.
Konsep dasar dari tree sort adalah sebagaimana sebuah pohon, ada akar, batang, ranting, daun, dan sebagainya. Dalam tree sort ada istilah akar atau root dan daun atau leaf.
2.      Pengurutan berdasarkan perbandingan (compirasion-based sorting)
·         Bubble sort
Teknik ini dilakukan dengan pola membawa nilai terbesar menjadi nilai index terakhir array. Jadi sistem ini melakukan pengecekan nilai 1 dengan 2, lalu 2 dengan 3 sampai dengan data terakhir, bila nilai index yang lebih kecil lebih besar maka akan dilakukan pertukaran. Proses ini dilakukan hingga jumlah data.
Membandingkan elemen yang sekarang dengan elemen yang berikutnya, jika elemen sekarang>elemen berikutnya, maka tukar.
Contoh procedure tukar data:
Procedure asc_buble (var data :array; jmldata:integer);
Var
i,j : integer;
begin
for i := 2 to jmldata do
for j :=jmldata downto i do
if data [j] <  data [j-1] then
tukardata (data[j], data [j-1] ) ;
end;
·         Exchange sort
Teknik sorting ini dibuat dengan cara pola membawa nilai terbesar menjadi nilai index terakhir array. Jadi sistem ini melakukan pengecekan nilai 1 dengan 2, lalu 2 dengan 3 sampai dengan data terakhir, bila nilai index yang lebih kecil lebih besar maka akan dilakukan pertukaran. Proses ini dilakukan hingga jumlah data dikurangi 1 atau sampai program tidak melakukan pertukaran. Jadi waktu untuk melakukan proses sorting lebih cepat. Exchange sort itu sangat mirip dengan buble sort. Bahkan banyak yang mengatakan bahwa exchange sort sama dengan buble sort.


Contoh procedure exchange sort :
Procedure asc_buble (var data :array; jmldata:integer);
Var
i,j : integer;
begin
for i := 2 to jmldata do
for j :=jmldata downto i do
if data [j] <  data [j-1] then
tukardata (data[j], data [j-1] ) ;
end;
perbedaannya terdapat dalam hal bagaimana membandimgkan antar elemen-elemennya:

Exchange sort
Buble sort


·         Membandingkan suatu elemen dengan elemen-elemen yang lainnya dalam array tersebut.
·         Melakukan pertukaran elemen jika perlu.
·         Jadi ada elemen yang selalu menjadi elemen pusat (pivot).
·         Membandingkan elemen pertama atau terakhir dengan elemen sebelumnya/  sesudahnya.
·         Kemudian elemen tersebut akan menjadi pusat (pivot) untuk dibandingkan dengan elemen sebelum/ sesudahnya lagi.
·         Begitu seterusnya








3.      Penguurutan berdasarkan prioritas (priority queue sorting method)
·         Selection sort
Teknik sorting ini dibuat dengan cara melakukan pengecekan satu-persatu, bila kita akan mengurutkan secara ascending maka kita lakukan pengecekan nilai tempat yang pertama (index pertama pada array) kita bandingkan semua nilai yang ada kita cari nilai minimalnya, lalu simpan index/ letak nilai minimum itu ditemukan, setelah pengecekan selesai tukar index awal pengecekan dengan nilai minimum yang telah simpan tadi. Proses ini dilakukan terus-menerus sampai pada pengecekan index terakhir minimal dengan index terakhir, beda dengan streith selection sort adalah dengan teknik ini melakukan pertukaran nilai lebih sedikit, hanya jumlah data-1 pertukaran. Jadi waktu untuk melakukan proses sorting lebih cepat.Membandingkan elemen yang sekarang dengan elemen yang berikutnya sampai dengan elemen yang terakhir. Jika ditemukan elemen yang lebih kecil, maka dicatat posisinya. Namun jika ditemukan elemen terkecil, maka dicatat posisinya dan kemudian di TUKAR dengan elemen sekarang.
Contoh procedure selection sort secara ascending :
Procedure asc_selection;
Var
Min,pos : byte;
Begin
For i:= 1 to max-1 do
Begin
Pos :=i ;
For j := i+1 to max do
If data [j] < data [pos] then pos :=j;
If i <> pos then tukardata (data[i] , data[pos] );
End;
End;

·         Heap sort (menggunakan tree)
Teknik sorting ini dibuat dengan versi yang jauh lebih efisien selection sort. Ia juga bekerja dengan menentukan elemen (atau terkecil) terbesar daftar, menempatkan bahwa pada akhir (atau awal) dari daftar, kemudian melanjutkan dengan sisa daftar tapi menyelesaikan tugas ini secara efisien dengan menggunakan struktur data yang disebut tumpukan, tipe khusus pohon biner. Setelah daftar data telah dibuat menjadi tumpukan, simpul akar dijamin menjadi unsur (atau terkecil) terbesar. Ketika dipindahkan dan ditempatkan di akhir daftar, tumpukan adalah ulang sehingga elemen terbesar yang tersisa bergerak ke akar. Menggunakan heap, menemukan elemen terbesar berikutnya membutuhkan O (log n) waktu, bukan O (n) untuk linear scan di selection sort sederhana. Hal ini memungkinkan heapsort untuk menjalankan dalam O (n log n) waktu, dan ini juga merupakan kompleksitas kasus terburuk.
4.      Pengurutan berdasarkan pembagian dan penguasaan (devide and conquer method)
·         Quick sort
Teknik sorting ini dibuat dengan cara yang menggunakan partisi. Pada teknik ini, data dibagi menjadi dua bagian, yaitu data disebelah kiri partisi selalu lebih kecil dari data disebelah kanan. Namun data pada kedua patisi belum terurut, sehingga untuk mengurutkannya, proses pengurutan dilakukan pada kedua partisi secara terpisah. Selanjutnya, data di sebelah kiri dan kanan dipartisi lagi.Merupakan proses penyusunan elemen yang membandingkan suatu elemen (pivot) denan elemen yang lain, dan menyusunnya sedemikian rupa sehingga elemen –elemen lain yang lebih kecil dari pivot terletak disebelah kiri pivot. Dan elemen yang lebih besar dari pivot terletak disebelah kanan pivot.Dengan demikian akan terbentuk dua sublist, yang terletak disebelah kanan dan kiri pivot.Lalu pada sublist kiri dan kanan itu kita anggap sebuah list baru, dan kita kerjakan proses yang sama seperti yang sebelumnya.Demikian seterusnya sampai tidak terdapat sublist lagi.
Contoh procedure quick sort secara ascending :
Procedure asc_quick (l , r :integer) ;
Var
i, j : integer;
begin
if l < r then
begin
i := l ;    j := r+1;
repeat
repeat inc (i) until data [i] >= data [l] ;
repeat dec (j) until data [j] <= data [l] ;
if i<j then tukardata (data [i], data [j]) ;
until i>j ;
tukardata (data [l], data [j] );
asc_quick (l, j-1);
asc_quick (j+1, r);
end;
end;
·         Merge sort
Teknik sorting ini dibuat dengan cara mengambil keuntungan dari kemudahan penggabungan daftar sudah disortir ke daftar diurutkan baru. Dimulai dengan membandingkan setiap dua elemen (yaitu: 1 dengan 2, kemudian 3 dengan 4) dan swapping mereka jika yang pertama datang setelah kedua. Kemudian masing-masing menggabungkan daftar yang dihasilkan dari dua ke daftar empat, kemudian menggabungkan daftar tersebut empat, dan seterusnya, sampai akhirnya dua daftar digabungkan ke dalam daftar diurutkan akhir.
5.      Pengurutan berkurang menurun (diminishing increment sort method)
·         Shell sort (pengembangan insertion)
Merupakan proses pengurutan data yang sebelumnya acak menjadi data yang terurut dengan cara menentukan jarak antar elemen yang akan dibandingkan.Teknik sorting ini dibuat dengan cara meningkatkan atas bubble sort dan insertion sort dengan menggerakkan keluar dari elemen-elemen memesan lebih dari satu posisi pada suatu waktu. Salah satu implementasi dapat digambarkan sebagai mengatur urutan data dalam array dua dimensi dan kemudian menyortir kolom baru array menggunakan insertion sort.


http://puguhjayadi.blogspot.com/2013/05/tree-sort-c.html (Rabu, 01 April 2015 pukul 23.55WIB)