Tampilkan postingan dengan label Sorting. Tampilkan semua postingan
Merge sort adalah algoritma yang berjalan dengan waktu O(N log N), yang jauh lebih efisien daripada O(N^2), dan akan berjalan jauh lebih cepat untuk N yang besar.
Algoritma merge sort sesungguhnya sangat sederhana: Bagi array menjadi dua sama besar, sort bagian pertama, sort bagian kedua, lalu gabungkan. Tentu sort ini menggunakan prosedur rekursif dengan parameter index paling kiri (a) dan index paling kanan (b).
Algoritma merge sort sesungguhnya sangat sederhana: Bagi array menjadi dua sama besar, sort bagian pertama, sort bagian kedua, lalu gabungkan. Tentu sort ini menggunakan prosedur rekursif dengan parameter index paling kiri (a) dan index paling kanan (b).
procedure
sort(terkiri,terkanan:longint);
begin
if terkiri < terkanan then
begin
sort(terkiri,(terkiri+terkanan) div 2);
sort(((terkiri+terkanan) div 2) + 1,
terkanan);
merge(terkiri,(terkiri+terkanan) div 2,
((terkiri+terkanan) div
2)+1,terkanan);
end;
end;
Quick Sort adalah algoritma sort yang tercepat dari antara sort-sort O(N log N) lainnya. Tetapi, Quick Sort juga algoritma yang running timenya tidak stabil. Artinya, dijamin 99,9999% bahwa Quick Sort akan berjalan dengan sangat cepat, tetapi pada kasus-kasus tertentu Quick Sort akan berjalan agak lambat, dan kalau sedang sial, untuk input tertentu (worst case) Quick Sort akan berjalan dengan waktu O(N2). Tapi pada umumnya (average case), Quick Sort berjalan dengan waktu O(N log N).
procedure
quicksort(terkiri,terkanan:longint);
var
kiri,kanan,temp,pivot:longint;
begin
if terkiri
begin
kiri:=terkiri;
kanan:=terkanan;
pivot:=data[(kiri+kanan) div 2];
while kiri<=kanan do
begin
while data[kiri]
while data[kanan]>pivot do dec(kanan);
if kiri<=kanan then
begin
temp:=data[kiri];
data[kiri]:=data[kanan];
data[kanan]:=temp;
inc(kiri);
dec(kanan);
end;
end;
quicksort(terkiri,kanan);
quicksort(kiri,terkanan);
end;
end;
Selection Sort merupakan sorting yang bisa dibilang cukup mudah dan bisa dilakukan di tempat (tanpa bantuan array lain).Dasarnya pada setiap langkah, carilah elemen terkecil yang tersisa lalu letakkan di depan.
procedure selectionsort;
var i,j,min,temp :integer;
begin
for i:=1 to n-1 do
begin
min:=i;
for j:=i+1 to n do
begin
if data[j] < data[min] then min:=j;
end;
if min <>i then
begin
temp:=data[min];
data[min]:=data[i];
data[i]:=temp;
end;
end;
end.
Keterangan :
i,j digunakan untuk looping.
data[] array bertipe integer (di deklarasikan pada program utama)
n adalah jumlah data (dideklarasikan pada program utama)
temp adalah var temporary digunakan untuk swap
Bubble sort merupakan sorting yang berprinsip pada sifat gelembung. Dasarnya, bilangan yg lebih kecil dari bilangan yang dibandingkan, akan di swap ke kiri (jika ascending).
Berikut Procedure Bubble Sort
Procedure BubbleSort;
var i,j,temp:integer // menyesuaikan masalah /soal
begin
for i := 1 to N do
for j := 1 to N - 1 do
if data[j] > data[j + 1] then
begin
temp := data[j];
data[j] := data[j + 1];
data[j + 1] := temp;
end;
end;
Keterangan :
data[] adalah array yang bernama data
n adalah jumlah data yang akan ditukar
temp adalah temporary, gunanya untuk tempat sementara agar bisa melakukan swap
