Sorting (Pointer)

Pengurutan dalam struktur data sangat penting terutama untuk data yang bertipe data numeric ataupun. Pengurutan (Sorting) adalah proses pengurutan data yang sebelumnya disusun secara acak sehingga tersusun secara teratur menurut aturan tertentu.
Contoh:
Data Acak : 5 6 8 1 3 25 10
Ascending : 1 3 5 6 8 10 25 Descending : 25 10 8 6 5 3 1

Bubble Sort
Bubble sort melakukan pengurutan dengan cara membandingkan elemen sekarang dengan elemen berikutnya. Algoritma ini seolah-olah menggeser satu per satu elemen dari kanan ke kiri atau kiri ke kanan, tergantung jenis pengurutannya. Ketika satu proses telah selesai, maka bubble sort akan mengulangi proses, demikian seterusnya.





procedure bubblesort (Pertama:PtrSimpul);
var
PtrData,PtrData2:Ptrsimpul;
a :integer;
begin
PtrData:=Pertama;
while PtrData <> NIL do
begin
PtrData2:=PtrData^.lnjt;
while PtrData2 <> NIL do
begin
if PtrData^.x > PtrData2^.x then
begin
a:=PtrData^.x;
PtrData^.x:=PtrData2^.x;
PtrData2^.x:=a;
end;
PtrData2:=PtrData2^.lnjt;
end;
PtrData:=PtrData^.lnjt;
end;
end;

Quick Sort
Algoritma ini berdasarkan pada pola divide-and- conquer, adapun langkah-langkahnya:
1. Divide
Memilah rangkaian data mengjadi dua sub rangkaian A[p..q-1] dan A[q+1..r] dimana setiap elemen A[p..q-1] adalah kurang dari atau sama dengan A[q] dan setiap elemen pada A[q+1..r] adalah lebih besar atau sam dengan elemen pa A[q]. A[q] disebut sebagai elemen pivot. Perhitungan pada elemen q merupakan salah satu begian dari procedure pemisahan.
2. Conquer
Mengurutkan elemen pada sub-rangkaian secara reqursif


Insertsion Sort
Mirip dengan cara orang mengurutkan kartu, selembar demi selembar kartu diambil dan disisipkan ke tempat yang seharusnya.
Pengurtan dimulai dari data ke-2 sampai dengan data terakhir, jika ditemukan data yang lebih kecil, maka akan ditempatkan diposisi yang seharusnya. Pada penyisipan elemen, maka elemen-elemen lain akan bergeser ke belakang.


Selection Sort
Merupakan kombinasi antara sorting dan searching. Untuk setiap proses, akan dicari elemen-elemen yang belum diurutkan yang memiliki nilai terkecil atau terbesar akan dipertukarkan ke posisi yang tepat di dalam pointer.
Misalnya untuk putaran pertama, akan dicari data dengan nilai terkecil dan data ini akan ditempatkan di indeks terkecil (data[0]), pada putaran kedua akan dicari data kedua terkecil, dan akan ditempatkan di indeks kedua (data[1]). Selama proses, perbandingan dan pengubahan hanya dilakukan pada indeks perbandingan saja, pertukaran data secara fisik terjadi pada akhir proses.
procedure selection(Pertama:PtrSimpul);
var
PtrData,PtrData2:Ptrsimpul;
a,i,y,z :integer;
begin
i:=1;
while i <= n do
begin
PtrData:=Pertama;
while PtrData <> NIL do
begin
PtrData2:=PtrData^.lnjt;
if PtrData2 <> NIL then
begin
if PtrData2^.x < PtrData^.x then
begin
a:=PtrData^.x;
PtrData^.x:=PtrData2^.x;
PtrData2^.x:=a;
end;
end;
PtrData:=PtrData^.lnjt;
end;
i:=i+1;
end;
end;


Marge Sort
Marge sort menggunakan pola divide and conquer, yang dirumuskan dalam 3 langkah:
1. Divide
Memilah elemen-elemen dari rangkaian data menjadi dua bagian
2. Conquer
Conquer setiap bagian dengan memanggil procedure marge sort secara rekursif
3. Kombinasi
Mengkombinasikan dua bagian tersebut secara rekursif untuk mendapatkan rangkaian data berurutan.

Function MargeSort(var La:list; Ca:integer):list;
Var Temp,Temp1,Temp2: List;
Begin
If La=nil then
MargeSort:=nil
Else
Begin
If Ca>1 then
Begin
Temp1:=MargeSort(La,Ca div 2);
Temp2:=MargeSort(La,(Ca+1) div 2);
MargeSort:=Marge(Temp1,Temp2)
End
Else
Begin
Temp:=La;
La:=La^.Kanan;
Temp^.Kanan:=nil;
MargeSort:=Temp
End
End;

Queue (Antrian)

Queue (Antrian) adalah list linier yang :

1. Elemen yang pertama kali masuk antrian akan keluar pertama kalinya
2. Dikenali elemen pertama (Front) dan elemen terakhirnya (Tail)
3. Satu elemen dengan elemen lain dapat diakses melalui informasi Next
4. Antrian dapat dibuat dengan menggunakan: Linier Array dan Circular Array

 Aturan penyisipan dan penghapusan elemennya disefinisikan sebagai berikut ;

• Penyisipan selalu dilakukan setelah elemen terakhir
• Penghapusan selalu dilakukan pada elemen pertama

Front dan tail selalu bergerak maju/naik sehingga

1. Bila tail telah mencapai elemen terakhir array, antrian dianggap penuh walau sebenarnya mungkin elemen-elemen awal antrian telah dihapus (dikosongkan).
2. Bila front dan tail mencapai nilai yang sama berarti antrian dalam keadaan kosong maka front dan tail dapat diinisialisasi kembali ke kondisi semula.

Deklarasi queue menggunakan singly linked list:

Type
TData=…;
TKey= …;
PNode=^Node;
Node=record
Key:TKey;
Data:TData;
Next:PNode;
End;
Queue=record
Count:integer;
Front,tail:PNode;
End;
Opersi-operasi di QUEUE
1. InitQ(Q)menciptakan Qdengan queue kosong

Procedure InitQ(var Q:Queue);
Begin
Q.count:=0;
Q.front:=nil;
Q.tail:=nilai;
End;

2. AddQ(Q,x) menambah elemen x ke rear queue

Procedure AddQ(var Q:Queue; p:PNode);
{sama dengan insert last, yang elemen last-nya disimpan}
Begin
Q.tail^.next:=p;
Q.tail:=p;
If Q,front=nil then q.front:=Q.tail; {elemen pertama dan satu-satunya dari queue}
Q.count:=Q.count+1;
End;

3. RemoveQ(Q,x) menghilangkan elemen pada front dari queue Q

Procedure removeQ(var Q:Queue; var k:TKey; d:TData);
{sama dengan delete first}
Var p:PNode;
Begin
If (Q.front<>Nil) then
Begin
P:=Q.Front;
Q.front:=Q.front^.Next;
If Q.front=nil then Q.tail:=nil; {elemen satu2nya dihapus}
K:=p^.key;
D:=p^.data;
Q.Count:=Q.count-1;
Dispose(p);
End;
End;

4. Front(Q) mengirim elemen front dari queue

Function frontQ (Q:queue):listPtr;
Begin
FrontQ:=Q.front;
End;

5. IsEmptyQ(Q) yang mengembalikan true if Q kosong else false

Function isEmpityQ(Q:queue):Boolean;
Begin
isEmptyQ:=(S.front=nil);
end;

6. HowManyIn(Q) mengirimkan jumlah elemen di Queue

Function howManyInQ(Q:queue):integer;
Begin
howManyInQ:=Q.count;
End;