Sorting didefinisikan sebagai pengurutan sejumlah data berdasarkan nilai kunci tertentu. Pengurutan dapat dilakukan dari nilai terkecil ke nilai terbesar (ascending) atau dari nilai terbesar ke nilai terkecil (descending).
Algoritma sorting merupakan algoritma yang
menempatkan elemen list pada urutan tertentu. Jenis Algoritma Sorting diantaranya :
1.
Buble Sort (Metode Gelembung)
Adalah
algoritma pengurutan yang membandingkan nilai satu dan nilai sebelahnya secara
terus menerus sampai bisa di pastikan dalam satu iterasi tidak ada perubahan
lagi. Metode ini terinpirasi dari gelembung yang beratnya lebih ringan dari air
sehingga gelembung terus menaik secara perlahan.
Algoritma Buble_Sort;
DEKLARASI
:
A := array [1…n] of
integer;
i,n,j,temp : integer;
ALGORITMA
:
for
i :=1 to n do
for j :=5 downto i do
if A[j] > A[j+1]
then
temp :=A[i];
A[i] := A[j];
A[j]:=temp;
endif
endfor
endfor
2.
Straight Insertion Sort (Metode
Penyisipan Langsung)
Adalah
algoritma pengurutan yang membandingkan nilai yang kedua sampai dengan yang
terakhir, apabila di temukan data di posisi yang tidak sesuai maka data
tersebut akan di sisipkan pada posisi yang sesuai.
Algoritma
Insertion_Sort;
DEKLARASI
:
data := array
[1..n] of integer;
i, j, n, x =:
integer;
ALGORITMA :
i := 1;
while I < n
do
x := data[i];
j := i-1;
while x <
data[j] do
data[j+1] :=
data[j]
j:= j-1;
endwhile
data[j+1] := x;
i := i+1;
endwhile
3.
Binary Insertion Sort (Penyisipan Biner)
Adalah
metode yang memperbaiki Straight Insertion Sort dengan melakukan proses
perbandingan yang lebih sedikit sehingga proses pengurutan menjadi lebih cepat.
Metode penyisipan biner melakukan proses
perbandingan dengan membagi dua bagian data dari posisi 0 sampai dengan N-1.
Algoritma
Binary_Insertion_Sort;
DEKLARASI
:
data : array
[1..n] of integer;
i, l, r, m, n, x
: integer;
ALGORITMA :
i := 1;
while i < n do
x := data[i]
l := 0;
r := i-1;
while l <= r do
m := (l+r)/2
if x < data[m] then
r := m-1;
else
l := m+1;
endif
endwhile
j:= i-1;
while j >= l do
data[j+1] := data[j];
j:= j-1;
endwhile
data[l] := x;
l := i +1;
endwhile
4.
Selection Sort
Adalah
algortitma pengurutan dengan cara mencari data terkecil kemudian menukarkannya
dengan data yang di pakai sebagai acuan (pivot).
Algoritma Selection_Sort;
DEKLARASI
:
data := array
[1..n] of integer;
k,i,j,temp,n :=
integer;
ALGORITMA :
i:=0;
while
i < n-1 do
k:=i
j:=i+1
while j < n do
if data[k] > data[j]
then
k := j;
j:= j+1;
temp:= data[i];
data[i]:= data[k];
data[k]:=temp;
i:=i+1;
endif
endwhile
endwhile
5.
Shell Short
Adalah
algoritma pengurutan dengan cara membandingkan data dengan data lain yang
memiliki jarak tertentu, kemudian dilakukan penukaran jika di perlukan.
Algoritma Shell_Sort;
DEKLARASI
:
data := array
[1..n] of integer;
jarak,i,j,n,temp
:= integer;
s:=boolean;
ALGORITMA :
jarak:=n;
while
jarak > 1 do
jarak := jarak/2;
s:=false;
while sudah:=false do
sudah:= true;
j := 0;
while j < n-jarak do
if data[j] > data[j+jarak]
then
temp:= data[j];
data[j]:= data[j+jarak];
data[j+jarak]:=temp;
s:=
true;
j
:= j+1;
endif
endwhile
endwhileendwhile
6.
Radix Sort
Adalah
algoritma pengurutan dengan cara mengelompokan digit terakhir nilai dari suatu
data kemudian mengurutkannya sampai dengan digit pertama.
Algoritma Radix_Sort;
ALGORITMA :
-
Kelompokan data berdasarkan nilai digit
terakhir suatu data pada suatu tempat.
-
Urutkan data tersebut.
-
Pindah ke digit sebelum terakhir lalu
urutkan lagi.
-
Lakukan pengurutan sampai dengan digit
pertama.
7.
Merge Sort (Penggabungan)
Adalah
algoritma pengurutan yang biasanya digunakan pada pengurutan berkas. Merge Sort
ini biasanya digunakan untuk menggabungkan dua kumpulan data yang sudah terurut
sehingga ketika bergabung data ini akan terurut.
DEKLARASI
:
t1, t2, t3 :=
array [1..n] of integer;
i, j, n, j1, j2,
j3 := integer;
ALGORITMA :
i:=
0;
j:=
0;
j3
:= 0;
while
i <= j1 or I <= j2 do
j3
:= j3 +1;
if
t1[i] < t2[j] then
t3[j3]
:= t1[i];
i:=
i+1;
elseif
t1[i] >= t2[j] then
t3[j3]
:= t2[j];
j:=
j+1;
endif
endwhile
if
i > j1 then
i:=j;
while
i < j2 do
j3
:= j3+1;
t3[j3]
:= t2[i];
i
:= i+1;
endwhile
else
j
:= i;
while
j < j1 do
j3
:= j3 +1;
t3[j3]
:= t1[j];
j:=
j+1;
endwhile
endif
8.
Quick Sort (Partition Exchange Sort)
Adalah
algoritma pengurutan dengan cara memilih suatu data sebagai pivot untuk mengatur
data di sebelah kiri lebih kecil dari pivot dan data di sebelah kanan agar
lebih besar dari pivot.
Algoritma Quick_Sort_Rekursif;
DEKLARASI
:
T1 := array
[1..n] of integer;
T2 := array
[1..n] of integer;
i, j, l, r, n, x,
temp := integer;
ALGORITMA :
x:=
data[(l+r)/2]
i:=
l;
j:=
r;
while
i <= j do
while
data[i] < x do
i:=
i+1
while
data[j] > x do
j:=
j-1
if i <= j then
temp := data[i];
data[i] := data[j];
data[j] := temp;
i:= i+1;
j:= j-1;
elseif l < j then
x := data[(l+j)/2];
elseif i < r then
x := data[(i+r)/2];
endif
endwhile
endwhile
endwhile
Perbandingan Algoritma Pengurutan
Tidak ada komentar:
Posting Komentar