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;
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;
