Algoritma Sorting (Pengurutan)

STRUKTUR DATA

Kali ini saya berbagi pengetahuan tentang 3 cara pengurutan data, yaitu quicksort, mergesort, dan shellsort. Kebetulan saya habis mendapat tugas tentang itu.. Hehehehe..

QUICKSORT

Ditemukan oleh C.A.R Hoare. Pengurutan ini berdasar pada prinsip devide and conquer. Devide adalah suatu langkah memilah masalah menjadi sub – masalah dalam proses rekursi, sedangkan conquer adalah proses menyelesaikan sub masalah tersebut, kemudian dilakukan pendekatan terhadap masalah utama.

Pada dasarnya prinsip kerjanya adalah membagi atau memartisi sekumpulan data menjadi dua bagian sedemikian rupa sehingga elemen ke-i berada tepat pada posisisnya, dimana semua elemen yang nilainya lebih kecil daripada elemen ke-i akan terletak disebelah kirinya, sedangkan yang mempunyai nilai lebih besar berada disebelah kanannya. Algoritma ini memiliki kompleksitas O(n log n). Berikut adalah langkah kerja dari quicksort :

1. Devide

Memilah data menjadi dua sub – rangkaian A[p…q-1] dan A[q+1…r] dimana setiap elemen A[p…q-1] adalah kurang dari atau sma dengan A[q] dan setiap elemen pada A[q+1…r] adalah lebih besar atau sama dengan elemen A[q]. A[q] disebut juga elemen pivot. Perhitungan pada elemen q merupakan salah satu bagian dari prosedur pemisahan.

1. Conquer

Mengurutkan elemen pada sub-rangkaian secara rekursif.

Contoh :

Rangkaian data :

3

1

4

1

5

9

2

6

5

3

5

8

Langkah pertama diawali dengan pemilihan sebuah elemen pivot :

3

1

4

1

5

9

2

6

5

3

5

8

Selanjutnya adalah inisialisasi elemen kiri sebagai elemen kedua dna elemen kanan sebagai elemen akhir.

KIRI KANAN

3

1

4

1

5

9

2

6

5

3

5

8

Geser elemen kiri kearah kanan sampai ditemukan nilai yang lebih besar dari elemen pivot tersebut. Geser elemen kanan ke kiri sampai ditemukan nilai dari elemen yang tidak lebih besar dari elemen tersebut. Maka didapat hasil :

KIRI KANAN

3

1

4

1

5

9

2

6

5

3

5

8

Langkah selanjutnya adalah menukarkan elemen kiri dan kanan yang telah terpilih tersebut, maka

didapatkan hasil penukarannya sebagai berikut :

KIRI KANAN

3

1

3

1

5

9

2

6

5

4

5

8

Geser lagi lemen kiri dan kanan sesuai aturan sebelumnya.

KIRI KANAN

3

1

3

1

5

9

2

6

5

4

5

8

Menukarkan kembali elemen kiri dan kanan yang telah terpilih tersebut :

KIRI KANAN

3

1

3

1

2

9

5

6

5

4

5

8

Kemudian geser kembali elemen kiri dan kanan sesuai aturan sebelumnya dan didapat hasil :

KANAN KIRI

3

1

3

1

2

9

5

6

5

4

5

8

Dapat kita lihat bahwa titik kanan dan kiri telah bergeser sehingga mendapatkan nilai elemen kanan kurang dari elemen kiri, Dalam hal ini maka tukarkan elemen pivot dengan elemen kanan, dan hasilnya adalah :

PIVOT

2

1

3

1

3

9

5

6

5

4

5

8

Pengurutan dengan langkah – langkah siatad terus dilakukan pada setiap elemen sub-rangkaian pada setiap sisi dari elemen pivot samapai menghasilkan urutan yang benar, yaitu :

1

1

2

3

3

4

5

5

5

6

8

9

Proses quicksort akan selesai bila proses tersebut telah menyisakan satu buah partisi data. Kompleksitas dari algoritma ini dalam kondisi stabil adalah n log (n) atau seburuk – buruknya adalah n² .

Berikut adalah source code dari quicksort :

void quicksort (int *arr, int kr, int kn)

{

int i, j, k;

if (kr<kn)

{

j=kr;

k=kn+;

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

} }

MERGESORT

Merge sort merupakan salah satu teknik sorting yang menurutkan suatu data dengan cara penggabungan. Merge sort juga menggunakan proses divide and conquer pada rekursi.Berikut adalah langkah kerja merge sort :

1. Devide

Memilah elemen – elemen dari data menjadi dua bagian.

1. Conquer

Menyelesaikan setiap bagian dengan memanggil prosedur merge sort secara rekursif.

1. Kombinasi

Mengkombinasikan dua bagian tersebut secara rekursif untuk mendapatkan rangkaian data berurutan.

Proses rekursi akan berhenti jika telah mencapai lemen dasar, atau artinya jika bagian yang diurutkan menyisakan tepat satu elemen. Sisa pengurutan satu elemen tersebut menandakan bahwa bagian tersebut telah sesuai rangkaian.

Contoh :

7

2

5

6

Langkah pertama adalah membagi rangkaian menjadi dua bagian (LeftArr dan RightArr)

7

2

5

6

Berikutnya adalah membagi LeftArr menjadi dua bagian :

7

2

Kemudian mengkombinasikannya menjadi :

2

7

Pembagian menjadi dua bagian dan kemudian mengkombinasikannya dilakukan juga pada RightArr dan berikut hasil pengkombinasiannya :

5

6

Dan langkah terakhir adalah mengkombinasikan LeftArr dan RightArr :

2

5

6

7

Sebagai catatan, pengkombinasian dilakukan dengan cara pembandingan. Elemen yang nilainya lebih kecil akan masuk ke kotak terlebih dahulu dan mengisi bagian disebelah kiri terlebih dahulu.Pada merge sort, data yang akan digabungkan berada pada suatu array, sebutlah array x dan array yang digunakan untuk menampung hasil gabung adalah array yang berbeda dari array x tersebut, sebutlah array y. Penyalinan elemen data dari array x ke array y ditentukan oleh hasil perbandingan data kelompok pertama x(i) dan data kelompok setelahnya x(j). Apabila nilai x(i) lebih kecil dibanding x(j) maka x(i) disalin ke y(k) kemudian indeks I dan k masing – masing ditambah satu. Proses ini akan berulang sampai seluruh data habis diproses.

Berikut adalah source code dari merge sort :

void mergesort (int *x, int n)

{

int *r, i, j, k, l1, l2, u1, u2, size;

r = (int *) malloc (n * sizeof (int));

size = 1;

while (size < n)

{

l1 = 0; k = 0;

while (l1+size < n)

{

l2 = l1+size;

u1 = l2 – 1;

u2 = (l2 + size – 1 < n) ? l2 + size – 1 : n-1;

for (i=l1; j=l2; i<=u1 && j<=u2; k++)

r[k] = (x[i] <= x[j]) ? x[i++] : x[j++];

while (i<=u1) r[k++] = x[i++];

while (j<=u2) r[k++] = x[j++];

l1 = u2+1;

}

for(i=l1; k<n; i++) r[k++] = x[i];

for(i=0; i<n; i++) x[i] = r[i];

size *= 2;

}

free(r); }

SHELLSORT

Ditemukan oleh Donal Shell pada tahun 1959. Merupakan algoritma paling efisien dari kelas sorting O(n²). Algoritma ini memiliki kesamaan cara kerja dengan insertion sort, yaitu membandingkan elemen-elemen dengan jarak tertentu. Insertion sort membandingkan elemen – elemen data yang berdekatan (berjarak satu posisi), sedangkan shell sort membandingkan elemen berjarak tertentu, misalnya elemen yang berjarak 5 posisi atau 2 posisi dan pada akhirnya akan selesai pada pengurutan data yang berjarak 1 posisi. Namun nilai ini haruslah dicari sedemikian rupa agar tidak menulangi atau merusak hasil sorting sebelumnya. Adapula nilai – nilai jarak yang dianjurkan adalah sebagai berikut :

1. Shell’s increment

1, 2, 4, 8

1. Hibbard’s increment

1, 3, 7, 15, …, 2^k – 1

1. Sedgewick’s increment

1, 5, 19, 41, 109

Pada proses sorting, jarak yang diambil dilakukan secara menurun, sedangkan proses sorting elemennya dilakukan seperti insertion. Pada pengurutan elemen – elemen jarak lima, pengurutan dilakukan terhadap data ke-9, ke-4, ke-8, ke-3, dan seterusnya. Dimana jumlah data yang terlibat dalam suatu rangkaian pengurutan tidak selalu dua tetapi tergantung pada banyak data. Andaikan jumlah data adalah 11 maka pada rangkaian pengurutan pertama dilakukan pengurutan terhadap data ke-10, ke-5, dank e-0.

Contoh :

Rangkaian data :

1 2 3 4 5 6 7 8 9 10

2

5

1

3

9

7

8

0

5

4

Increment : 5

Maka data yang pertama dibandingkan adalah data ke-6 dengan ke-1 kemudian ke-7 dengan ke-2 , ke-8 dengan ke-3, ke-9 dengan ke-4, ke-10 dengan ke-5. Dan hasilnya adalah :

1 2 3 4 5 6 7 8 9 10

2

5

0

3

4

7

8

5

5

9

Increment : 2

Maka data yang selanjutnya dibandingkan adalah data ke-3 dengan ke-1, ke-4 dengan ke-2, ke-5 dengan ke-3, ke-6 dengan ke-4, ke-7 dengan ke-5, ke-8 dengan ke-6, ke-9 dengan ke-7,dan ke-10 dengan ke-8. Dan hasilnya adalah sebagai berikut :

1 2 3 4 5 6 7 8 9 10

0

3

2

5

4

5

5

7

8

9

Increment : 1

Maka data yang akan diurutkan adalah data ke-2 dengan ke-1, ke-3 dengan ke-2, ke-4 dengan ke-3, dan seterusnya sampai data ke-10 dengan ke-9. Dan hasilnya adalah sebagai berikut :

1 2 3 4 5 6 7 8 9 10

0

2

3

4

5

5

5

7

8

9

Dalam proses pengurutannya shell sort dapat lima kali lebih cepat bila dibandingkan dengan bubble sort dan kurang lebih dua kali lebih cepat bila dibandingkan dengan insertion sort. Namun, jika dibandingkan dengan merge, heap, ataupun quicksort, shellsort masih tergolong lebih lambat. Tetapi algoritma sorting yang begitu sderhana membuat shellsort merupakan pilihan yang cocok untuk melakukan sorting pada data kurang dari 5000 item atau data dengan ukuran tidak terlalu besar.

Berikut adalah source code dari shellsort :

void shellsort (int *r, int lo, int hi)

{

int d, i, j, temp;

for (d = hi – lo + 1; d>1; )

{

if (d>5) d = 1;else d=(5*d – 1)/11;

for (i=hi – d; i>=lo; i–)

{

temp = r[i];

for (j=i+d; (j<=hi) && (temp>r[j]); j+=d)

r[j-d] = r[j];

r[j-d] = temp;

}

}

}