MODEL SORTING

MODEL SORTING

  

Counting Sort

       program counting_sort;
uses wincrt;
type
nilai = array[1..50] of integer;
var
nl : nilai;
mindata,maxdata: integer;
jumlah ,i:integer;
procedure isinilai(var nl:nilai; var n:integer);
var
j:integer;
begin
write('banyak data : ');
readln(n);
for j:=1 to n do
begin
write('data ke ',j,' : ');
readln(nl[j]);
end;
end;

procedure minmax(nl:nilai;n:integer;var mindata:integer;var maxdata:integer);
begin
mindata :=nl[1];
maxdata :=nl[1];
for i:=2 to n do
begin
if nl[i] < mindata then mindata :=nl[i];
if nl[i] > maxdata then maxdata :=nl[i];
end;
end;

       procedure minmax(nl:nilai;n:integer;var mindata:integer;var maxdata:integer);
begin
mindata :=nl[1];
maxdata :=nl[1];
for i:=2 to n do
begin
if nl[i] < mindata then mindata :=nl[i];
if nl[i] > maxdata then maxdata :=nl[i];
end;
end;

procedure countsort(var tabint:nilai;n:integer;mindata:integer;maxdata:integer);
const min=1;max=100;
var
i,j,k:integer;
tabcount:array [min..max] of integer;
begin
for i:=mindata to maxdata do
tabcount[i]:=0;

for i:=1 to n do
tabcount[tabint[i]]:=tabcount[tabint[i]]+1;
k:=0;
for i :=mindata to maxdata do
if tabcount[i]<>0 then
for j:=1 to tabcount[i] do
begin
k:=k+1;
tabint[k]:=i;
end;
end;

procedure cetak(nl:nilai;n:integer);
begin
for i:=1 to n do
write(nl[i],' ');
writeln;
end;

for i:=1 to n do
tabcount[tabint[i]]:=tabcount[tabint[i]]+1;
k:=0;
for i :=mindata to maxdata do
if tabcount[i]<>0 then
for j:=1 to tabcount[i] do
begin
k:=k+1;
tabint[k]:=i;
end;
end;

procedure cetak(nl:nilai;n:integer);
begin
for i:=1 to n do
write(nl[i],' ');
writeln;
end;

pengertian sorting

       Sorting merupakan suatu proses untuk menyusun kembali humpunan obyek menggunakan aturan tertentu. Sorting disebut juga sebagai suatu algoritma untuk meletakkan kumpulan elemen data kedalam urutan tertentu berdasarkan satu atau beberapa kunci dalam tiap-tiap elemen. Pada dasarnya ada dua macam urutan yang biasa digunakan dalam suatu proses sorting:
1. Urut naik (ascending) 

       Mengurutkan dari data yang mempunyai nilai paling kecil sampai paling besar

2. Urut turun (descending)

       Mengurutkan dari data yang mempunyai nilai paling besar sampai paling kecil.

  Mengapa harus melakukan sorting data? Ada banyak alasan dan keuntungan dengan mengurutkan data. Data yang terurut mudah untuk dicari, mudah untuk diperiksa, dan mudah untuk dibetulkan jika terdapat kesalahan. Data yang terurut dengan baik juga mudah untuk dihapus jika sewaktu-waktu data tersebut tidak diperlukan lagi.

contoh program buble sort dalam bahasa pascal.

Program Bubble_Sort;

Uses WinCrt;

const

max = 100;

type

Larik = array [1..max] of integer;

varA: Larik;

I: integer;

N: integer;

pil:byte;

procedure Jumlah_Data;

begin

write(‘Masukkan banyaknya data = ‘); readln(N);

writeln;

end;

procedure Input;

var

I: integer;

begin

for I:=1 to N do

begin

write(‘Masukkan data ke-‘, I, ‘ = ‘); readln(A[I]);

end;

end;

procedure Change(var A, B: integer);

var

T: integer;

begin

T:=A;

A:=B;

B:=T;

end;

procedure asc_buble;

var

p,q :INTEGER;

flag:boolean;

begin

flag:=false;

p:=2;

while (p<N) and (not flag) do

begin

flag:=true;

for q:=N downto p do

if A[q]<A[q-1] then

begin

change(A[q],A[q-1]);

flag:=false;

end;

inc(i);

end;

writeln;

write(‘Data Diurutkan Secara Ascending: ‘);

end;

procedure desc_buble;

var

p,q :byte;

flag:boolean;

Begin

flag:=false;

p:=2;

while (p<max) and (not flag) do

begin

flag:=true;

for q:=max downto p do

if A[q]>A[q-1] then

begin

change(A[q],A[q-1]);

flag:=false;

end;

inc(i);

end;

algoritma quick rekursif.

  Kode berikut memperlihatkan contoh fungsi rekursif, untuk menghitung hasil kali dari dua bilangan:

  def kali(a, b): return a if b == 1 else a + kali(a, b - 1)

  Bagaimana cara kerja fungsi rekursif ini? Sederhananya, selama nilai b bukan 1, fungsi akan terus memanggil perintaha + kali(a, b - 1), yang tiap tahapnya memanggil dirinya sendiri sambil mengurangi nilai b. Mari kita coba panggil fungsi kali dan uraikan langkah pemanggilannya

  kali(2, 4) -> 2 + kali(2, 3) -> 2 + (2 + kali(2, 2)) -> 2 + (2 + (2 + kali(2, 1))) -> 2 + (2 + (2 + 2)) -> 2 + (2 + 4) -> 2 + 6 -> 8

  Perhatikan bahwa sebelum melakukan penambahan program melakukan pemanggilan fungsi rekursif terlebih dahulu sampai fungsi rekursif mengembalikan nilai pasti (2). Setelah menghilangkan semua pemanggilan fungsi, penambahan baru dilakukan, mulai dari nilai kembalian dari fungsi yang paling terakhir.

       Mari kita lihat contoh fungsi rekursif lainnya, yang digunakan untuk melakukan perhitungan faktorial:

  def faktorial(n): return n if n == 1 else n * faktorial(n - 1)

        Fungsi faktorial memiliki cara kerja yang sama dengan fungsi kali. Mari kita panggil dan lihat langkah pemanggilannya:

  faktorial(5) -> 5 * faktorial(4) -> 5 * (4 * faktorial(3)) -> 5 * (4 * (3 * faktorial(2))) -> 5 * (4 * (3 * (2 * faktorial(1)))) -> 5 * (4 * (3 * (2 * 1))) -> 5 * (4 * (3 * 2)) -> 5 * (4 * 6) -> 5 * 24 -> 120

metode-metode 

Buble Sort :

  Merupakan algoritma pengurutan paling tua dengan metode pengurutan paling sederhana. Pengurutan yang dilakukan dengan membandingkan masing-masing item dalam suatu list secara berpasangan, menukar item jika diperlukan, dan mengulaginya sampai akhir list secara berurutan, sehingga tidak ada lagi item yang dapat ditukar.

Selection Sort :

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

Insertion Sort :

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.

head dan tail

                                                                                                                       NAMA:  RIZKI FITRIA

                                                                                                                       NIM    : 1405020046

                                                                                                                       UNIT  : B

Berikan gambaran/ilustrasi dari kasus antrian berikut

1.        diketahui suatu antrian/queue dgn max =6?

2.      lakukan enqueue 4 elemen ke dalam antrian dimanakah posisi head dan tail?

3.      kemudian lakukan dequeue 2 elemen dari antrian maka dimana posisi head dan tail?

4.     dari keadaan di atas bagaimanakah kondisi isfull dan isempety nya ?

JAWABAN

1.          0          1           2          3          4          5          6
            A          B          C          D
            haed(0)                                   tail(3)


.enqueue 4 elemen
-tail = -1+1
            =0 enqueue (A)                                   0          1           2          3                      5
                                                            A
                                                            head dan tail (0)

2.  enqueue 4 elemen
-tail = o+1
            =1 enqueue (B)                                    0          1           2          3          4          5
                                                            A          B
                                                            head    tail

c. enqueue 4 elemen                          0          1           2          3          4          5
-tail = 1+1                                             A          B          C
            =2 enqueue (C)                                   head                tail

d. enqueue 4 elemen                          0          1           2          3          4          5
-tail = 2+1                                            A          B          C          D
            =3 enqueue (D)                                  head                            tail

perbedaan utama stack dan queue

Perbedaan utama stack dan queue adalah :

Stack memakai sistem LIFO atau last in first out (yang pertama masuk akan keluar terakhir, begitu pula yang terakhir masuk akan keluar pertama kali) yang apabila kita mengahapus/ keluar data, maka data yang terakhirlah yang akan terhapus/ keluar terlebih dahulu.

Sementara queue memakai siste FIFO atau first in first out (yang pertama masuk akan keluar pertama, begitu pula yang masuk terakhir akan keluar terakhir) yang apabila kita menghapus / mengeluarkan data, maka data yang pertamalah yang akan terhapus/ keluar terdahulu dan data yang terakhir akan terhapus/ keluar terakhir.

Guna counter pada rangkaian stack dan queue adalah untuk menentukan apakah stack atau queue tersebut sudah full atau masih empty.

Queue mempunyai struktur data yang hampir sama dengan Stack. Yang membedakan adalah procedure Deque, dimana terjadi iterasi untuk pergeseran komponen2 array, karena Queue menggunakan metode FIFO (First In First Out) sedangkan Stack menggunakan metode LIFO (Last In First Out). Berikut adalah listing program Queue yang  ditulis dalam bahasa Pascal.

Contoh program:

PROGRAM QUEUE01;

uses wincrt;

const MAX=50;

type

larik = Array[0..MAX] of char;

RecQueue = RECORD

info : larik;

awal : integer;

akhir : integer;

END;

var

antri : RecQueue;

pilih,elm : char;

procedure init;

begin

antri.awal := 0;

antri.akhir := 0;

end;

function Isfull:boolean;

begin

if antri.akhir = MAX then

Isfull := true

else

Isfull := false;

end;

function IsEmpty:boolean;

begin

if antri.akhir = 0 then

Isempty := true

else

Isempty := false;

end;

procedure baca;

var i:integer;

begin

writeln('Isi queue sekarang : ');

for i := antri.awal to antri.akhir do

write(antri.info[i], ' ');

writeln('');

end;

procedure inQueue(elemen:char);

begin

if Isempty = true then

begin

antri.awal := 1;

antri.akhir:= 1;

antri.info[antri.awal] := elemen;

end

else if Isfull <> true then

begin

antri.akhir := antri.akhir + 1;

antri.info[antri.akhir]:=elemen;

end

else

writeln('Queue overflow...');

end;

function deQueue:char;

var isi:char;

i : integer;

begin

if Isempty <> true then

begin

isi := antri.info[antri.awal];

for i:=antri.awal to antri.akhir - 1 do

antri.info[i] := antri.info[i+1];

antri.akhir := antri.akhir - 1;

deQueue := isi;

end

else

writeln('Queue underflow...');

end;

BEGIN

CLRSCR;

writeln('--- Demo Queue dg Linear Array ---');

init;

repeat

writeln('OPERASI QUEUE dg Linear Array :');

writeln('[1] InQueue (Insert Queue)');

writeln('[2] DeQueue (Delete Queue)');

writeln('[3] Baca');

writeln('[4] Selesai...');

write(' Pilihan : ');

readln(pilih);

case pilih of

'1' : begin

write('Antrian Masuk : ');

readln(elm);

inQueue(elm);

end;

'2' :

 begin

 elm:=deQueue;

writeln(elm,' Keluar dr antrian');

end;

'3' : baca;

'4' : writeln('Wakarimasuta (?_?)');

else writeln('Salah pilih...');

end;

writeln('');

until (pilih = '4');

readln;

END.

Contoh penerapan Antrian (Queue) dalam kehidupan sehari-hari:

Contohnya yaitu antrian pada kasir pada sebuah bank. Ketika seorang pelanggan datang, akan menuju ke belakang dari antrian. Setiap pelanggan dilayani, antrian yang berada di depan akan maju. Jika kita ada di antrian kedua, maka kita akan menunggu antrian pertama melakukan prosesnya. Nah, ketika selesai proses dari antrian pertama dia akan pergi, dan giliran kita untuk maju untuk melakukan proses. Begitu juga arti dari antrian dalam bahasan kali ini, jika pengantri pertama datang maka dia juga yang akan keluar pertama kali atau bahasa kerennya tu FIFO ( First In First Out ).

Kondisi antrian yang menjadi perhatian :

            1.Penuh

Bila elemen pada antrian mencapai kapasitas maksimum antrian, maka tidak mungkin dilakukan penambahan ke antrian. Penambahan elemen menyebabkan kondisi kesalahan overflow

            2.  Kosong

Bila tidak ada elemen pada antrian, maka tidak mungkin dilakukan pengambilan elemen dari antrian. Pengambilan elemen menyebabkan kondisi kesalahan overflow.

Operasi-operasi pada Queue:

1. Create Queue (Q) : membuat antrian baru Q, dengan jumlah elemen kosong.
2. Make NullQ (Q) : mengosongkan antrian Q, jika ada elemen maka semua elemen dihapus.
3. EnQueue : berfungsi memasukkan data kedalam antrian.
4. DeqQueue : berfungsi mengeluarkan data terdepan dari antrian.
5. Clear : Menghapus seluruh Antrian
6. IsEmpty : memeriksa apakah antrian kosong
7. IsFull : memeriksa apakah antrian penuh.

Operasi-operasi pada Antrian (queue):
1.Create()
Untuk menciptakan dan menginisialisasi Queue dengan cara membuat Head dan Tail  = -1
2. IsEmpty()
Untuk memeriksa apakah antrian masih kosong atau sudah terisi dengan cara memeriksa nilai tail, jika tail = -1,maka empty pergerakan pada Antrian terjadi dengan penambahan data Antrian kebelakang, yaitu menggunakan nilai tail
3. IsFull()
Untuk mengecek apakah Antrian sudah penuh atau belum dengan cara mengecek nilai tail, jika tail >= MAX-1 (karena MAX-1 adalah batas data array pada C) berarti sudah penuh.

4. Enqueue
Untuk menambahkan data ke dalam antrian, penambahan data selalu ditambahkan di data paling belakang penambahan data selalu menggerakan variabel tail dengan cara increment counter tail.

5. Dequeue()
Digunakan untuk menghapus data terdepan dari Antrian dengan cara mengurangi counter tail dan menggeser semua data antrian kedepan. penggeseran dilakukan dengan menggunakan looping
6. Clear()
Untuk menghapus semua data Antrian dengan cara membuat tail dan head = -1 penghapusan data-data antrian sebenarnya tidak menghapus arraynya, namun hanya mengeser indeks pengaksesannya ke nilai -1 sehingga data-data Antrian tidak lagi terbaca
7. Tampil()
Untuk menampilkan nilai-nilai data Antrian menggunakan looping dari head s/d tail.

EnQueue : Masukkan data ke dalam antrian
DeQueue : Mengeluarkan data terdepan dari antrian
Clear : Menghapus seluruh antrian
IsEmpty : Memeriksa apakah antrian kosong
IsFull : Memeriksa apakah antrian penuh

1. Create

Untuk menciptakan dan menginisialisasi Queue

Dengan cara membuat Head dan Tail  = -1.

2. IsEmpty

Untuk memeriksa apakah Antrian sudah penuh atau belum dengan cara memeriksa nilai Tail, jika Tail = -1 maka empty

Kita tidak memeriksa Head, karena Head adalah tanda untuk kepala antrian (elemen pertama dalam antrian) yang tidak akan berubah-ubah

Pergerakan pada Antrian terjadi dengan penambahan elemen Antrian kebelakang, yaitu menggunakan nilai Tail.

3. IsFull

Untuk mengecek apakah Antrian sudah penuh atau belum

Dengan cara mengecek nilai Tail, jika Tail >= MAX-1 (karena MAX-1 adalah batas elemen array pada C) berarti sudah penuh.

4. Enqueue

Untuk menambahkan elemen ke dalam Antrian, penambahan elemen selalu ditambahkan di elemen paling belakang

Penambahan elemen selalu menggerakan variabel Tail dengan cara increment counter Tail terlebih dahulu.

5. Dequeue

Digunakan untuk menghapus elemen terdepan/pertama (head) dari Antrian

Dengan cara menggeser semua elemen antrian kedepan dan mengurangi Tail dgn 1

Penggeseran dilakukan dengan menggunakan looping.

6. Clear

Untuk menghapus elemen-elemen Antrian dengan cara membuat Tail dan Head = -1

Penghapusan elemen-elemen Antrian sebenarnya tidak menghapus arraynya, namun hanya mengeset indeks pengaksesan-nya ke nilai -1 sehingga elemen-elemen Antrian tidak lagi terbaca.

7. Tampil

Untuk menampilkan nilai-nilai elemen Antrian

Menggunakan looping dari head s/d tail