ALGORITMA DAN STRUKTUR DATA : BAB 13

SORTING II

13.1 Advanced Sorting

Kelemahan dari Simple Sort Teknik adalah diperlukannya waktu yang lama untuk melakukan sorting ,
terutama bila data yang hendak disort panjang. Kelemahan ini diatasi dengan Advanced Sort Teknik
yang pada umumnya memerlukan waktu yang lebih sedikit.

13.2 Quick Sort

Konsep dalam Quick Sort adalah “ memecah “ list yang akan di sort menjadi dua bagian, dan masingmasing
bagian akan dilakukan Sort tersendiri. Misalkan elemen yang diurutkan adalah :
r[1], r[2],……….r[n]

Maka satu langkah dalam quicksort akan menghasilkan :
r[1], r[2], ….. r[j-1], r[j] r[j+1],…..r[n]
(a) (b) (c)

Dapat dikatakan bahwa r[j] berada pada posisi yang “tepat” dengan pengertian bahwa semua elemen
yang berada dikiri r[j] LEBIH KECIL dibandingkan r[j], dan smeua elemen yang berada dikanan r[j]
LEBIH BESAR dibandingkan r[j]

Langkah berikutnya adalah mengurutkan elemen r[1] sampai dengan r[j-1] dan elemen r[j+1] sampai
r[n] dengan teknik yang sama seperti diatas.

Contoh ;
1. 73 79 76 72 75 78 71 77 74
2. 72 71 73 76 75 78 79 77 74
3. [71] 72 [73] 76 75 78 79 77 74
4. [71 72 73] 76 75 78 79 77 74
5. [71 72 73] 74 75 [76] 79 77 78
6. [71 72 73 74] 75 [76] 79 77 78
7. [71 72 73 74 75 76] 79 77 78
8. [71 72 73 74 75 76] 77 78 [79]
9. [71 72 73 74 75 76 77 78 79]

Langkah-langkahnya adalah sebagai berikut :

1. Carilah posisi yang paling tepat untuk angka 73. arti posisi paling tepat adalah bahwa semua
angka di sebelah kiri 73, harus lebih kecil dari 73 dan yang sebelah kanan 73 harus lebih
besar dari 73.

2. Cara mencari posisi yang paling tepat adalah ;
a. Cari dari kiri ke kanan sampai ketemu angka yang lebih besar dari 73.
b. Cari dari kanan ke kiri sampai ketemu angka yang lebih kecil dari 73.
c. Cek apakah sudah overlapping (apakah j >= k).

• Jika belum overlapping, maka tukar elemen, yang berada pada posisi j dengan
elemen yang berada pada posisi k.

• Jika sudahOverlapping, maka tukar elemen yang lebih kecil, dengan elemen
yang ingin dicarikan posisi tepatnya.
Contoh : akan dicarikan posisi yang paling tepat untuk angka 73.
73 79 76 72 75 78 71 77 74

• Dicari dari kiri kanan, sampai ketemu angka yang lebih besar dari 73, ketemu dengan angka

• Dicari dari kanan ke kiri, sampai ketemu angka yang lebih kecil dari 73, ketemu dengan
angka 71.

• Cek apakah sudah overlapping, bila belum maka tukar tempat antara 79 dengan 71 hasilnya
adalah:
73 71 76 72 75 78 79 77 74

• Pencarian diteruskan dari tempat berakhir tadi, dicari lagi dari kiri kanan, sampai ketemu
angka yang lebih besar dari 73, ketemu dengan angka 76.

• Pencarian dari kanan juga diteruskan dari tempat berakhir tadi, dicari ke kanan untuk
menemukan angka yang lebih kecil dari 73, ketemu dengan angka 72.

• Cek apakah sudah overlapping, ternyata belum, maka tukar tempatkan antara angka 76
dengan 72.hasilnya adalah.
73 71 72 76 75 78 79 77 74

• Pencarian diteruskan lagi, mencari dari kiri ke kanan sampai ketemu angka yang lebih besar
dari 73 , ketemu dengan angka 76.

• Pencarian dari kanan ke kiri juga dilakukan untuk mencari angka yang lebih kecil dari 73,
ketemu dengan angka 72,

• Ternyata sudah overlapping, sehingga dilakukan pertukaran tempat antara angka yang kecil
yaitu : 72 dengan angka yang ingin dicarikan tempat yang tepat, yaitu 73 hasilnya adalah :
72 71 [73] 76 75 78 79 77 74
(a) (b)

Sekarang angka 73 sudah berada pad posisi yang tepat, artinya semua angka di sebelah kirinya lebih
kecil darinya dan semua angka di sebelah kanannya lebih besar darinya. Pencarian diteruskan untuk
dua sub-list berikutnya, yaitu sub list (a) dan sub list (b).

Prosedur untuk melakukan Quick Sort adalah sesuai dengan menggunakan Recursive yaitu suatu
fungsi yang memanggil dirinya sendiri.

void quicksort (int *arr, int kr, int kn)
{
int i, j, k;
if (kr < kn)
{
j = kr;
k = kn + 1;
do {
do j++; while (j <= kn && arr[j] < arr[kr]);
do k–; while (arr[k] > arr[kr]);
if (j < k) tukar (&arr[j], &arr[k]);
} while (j<= k);
tukar (&arr[kr], &arr[k]);
quicksort (arr, kr, k-1);
quicksort (arr, k+1, kn);
}
}

13. 3 Heap Sort

Heap Sort adalah suatu teknik sorting yang memanfaatkan Heap / Complete Binary Tree yang telah
dibahas pada bab terdahulu. seperti diketahui ada 2 tipe Heap, yaitu Minimum Heap dan Maksimum
Heap. Bila dipergunakan minimum Heap dalam melakukan sorting maka hasil pengurutan berbentuk
Descending, sedangkan
kebalikannya bila menggunakan Maksimum Heap, maka akan dihasilkan sorting secara Ascending.

Tahapan dalam melakukan Heap Sort adalah :
• Membangun Heap Awal sehingga memenuhi kondidi heap (heapify)
• Mengambil data dari heap untuk diurutkan sesuai dengan urutannya, dengan cara pertukaran
data [1] dengan data [j] dengan j = n, n-1, …., 2. Setiap pertukaran ini menyebabkan kondisi
heap rusak. Untuk menanggulangi ini maka harus dibangun lagi heap ke kondisi semula.
Contoh lakukanlah sorting terhadap angka-angka 390, 205, 182, 45, 235 dengan mempergunakan
teknik Heap Sort dan menggunakan Minimum Heap.

Langkah 1: membangun Heap awal

Gambar

Tree yang dibangun berdasarkan list angka, tetapi masih belum berupa Maximum Heap. Lakukan
pertukaran tempat sampai terjadi Maximum Heap seperti pada gambar berikut ini

Gambar

Gambar

Gambar

Gambar

Gambar

Gambar

Gambar

Proses pengurutan dengan metode heapsort maximum selesai dan menghasilkan urutan elemen

secara ascending.

void addroot(int *arr, int i, int n)
{
int child, temp;
for (temp = arr[i]; i*2 <= n; i =child)
{
child = i * 2;
if ((child != n) && (arr[child +1] > arr[child])) child++;
if (temp < arr[child]) arr[i] = arr[child];
else break;
}
arr[i] = temp;
}
void heapsort(int *arr, int n)
{
int i
for (i = n/2; i > 0; i–) addroot(arr, i, n);
for (i = n; i > 1; i–)
{
tukar(&arr[1], arr[i]);
addroot(arr, 1, i-1);
}
}

13.4 Merge Sort dengan metode rekursif
Terdapat 3 prosedur dalam metode ini, yaitu prosedur mergesort, merge, dan insert.
Prosedur mergesort
Langkah – langkahnya:

1. membagi 1 array menjadi 2 dengan cara:
cari tengahnya mid = (a+b) div 2 sehingga terdapat 2 bagian, (a, mid) dan (mid+1, b)
lakukan terus pembagian samapi pada leaves (daun) yang tidak bisa dibagi lagi.

2. lakukan merge pada daun yang tidak bisa dibagi lagi

3. kedua langkah diatas dilakukan apabila a < b (indeks kiri lebih kecil dari indeks kanan)

algoritmanya:
procedure mergesort(a, b: integer)
begin
if a < b then
begin
mid := (a+b) div 2
mergesort(a, mid)
mergesort(mid+1, b)
merge (a,b)
end if
end

Prosedur merge
Langkah – langkahnya:
1. cari mid-nya
2. tentukan indeks i 􀃆 a = i
3. tentukan k 􀃆 k = mid + 1
4. bandingkan elemen yang ke-i dengan elemen yang ke-k
jika nilai elemen yang ke-i <= nilai elemen yang ke-k, maka
naikkan jumlah
jika tidak, maka

  • insert elemen yang ke-k ke elemen yang ke-i
  • naikkan jumlah i
  • naikkan jumlah k
  • naikkan mid

5. lakukan langkah 4 sampai i > mid atau k > b

algoritmanya:
prosedure merge(a,b: integer)
begin
mid = (a+b) div 2
i = a
k = mid +1
repeat
if a[i] <= a[k] then i = i+1
else
begin
insert (k, i)
i = i+1
k = k+1
mid = mid + 1
endif
until i > mid or k > b
end

Prosedur insert
Langkahnya:
1. tentukan nilai yang akan di insert (k), lalu masukkan nilai dari elemen ke-k ke variabel temp.
2. tentukan bahwa j = k 􀃆 posisi dari j sampai i + 1 menggeser ke kanan.
3. masukkan temp ke a[i]

algoritmanya:
procedure insert(k,i)
begin
temp = a[k]
for j = k downto i + 1
a[j] = a[j-1]
endfor
a[i] = temp
end

misalkan ada 10 elemen, yaitu

Gambar

Gambar
Gambar
Gambar

Gambar
Gambar

Iklan

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s