·
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://designkeyz.blogspot.com/2011/04/teknik-sorting-dan-searching.html
(Rabu, 01 April 2015 pukul 23.55WIB)
http://puguhjayadi.blogspot.com/2013/05/tree-sort-c.html
(Rabu, 01 April 2015 pukul 23.55WIB)
https://itprogrammingandlinux.wordpress.com/2011/05/22/buble-insertion-selection-shell-maxmin-quick-merge-sort/
(Rabu, 01 April 2015 pukul 00.01WIB)
0 komentar:
Posting Komentar