Archive for Januari 2014
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
Pustakawan
| Batas Waktu | 1 detik |
| Batas Memori | 32 MB |
Pak Dengklek mencoba bekerja paruh waktu menjadi pustakawan. Setiap hari, dia bertugas merapikan buku-buku di setiap rak sehingga urut sesuai nomor kodenya. Pak Dengklek merasa kerepotan karena harus menukar posisi buku-buku berkali-kali.
Kali ini, Pak Dengklek akan merapikan sebuah rak berisi N (1 ≤ N ≤ 1.000) buah buku. Buku ke-i memiliki kode Di (-32.768 ≤ Di < 32.768). Bantulah Pak Dengklek dengan menentukan jumlah penukaran buku minimum hingga buku dalam suatu rak terurut menaik berdasarkan nomor kodenya.
Format Masukan
Baris pertama berisi sebuah bilangan bulat N. N baris berikutnya masing-masing berisi sebuah bilangan bulat Di. Dijamin kode-kode buku tersebut berbeda-beda.
Format Keluaran
Sebuah baris berisi sebuah bilangan bulat yaitu jumlah penukaran minimum yang harus dilakukan untuk mengurutkan buku-buku tersebut.
Contoh Masukan
5124 35
Contoh Keluaran
2
Penyelesaian
