SORTING (PENGURUTAN)

PENDAHULUAN

Setelah mempelajari bab ini diharapkan mahasiswa mampu :

1. Menunjukkan beberapa algoritma dalam pengurutan.
2. Menunjukkan bahwa pengurutan merupakan suatu persoalan yang bisa diselesaikan dengan sejumlah algoritma yang berbeda satu sama lain.
3. Dapat memilih algoritma yang paling sesuai untuk menyelesaikan suatu permasalahan pemrograman.

PENYAJIAN (TUTORIAL)

Pengurutan data (sorting)  didefinisikan sebagai suatu proses untuk menyusun kembali himpunan obyek menggunkan aturan tertentu. Ada dua macam urutan yang bisa digunakan dalam proses pengurutan yaitu :

• Urutan naik (ascending) yaitu dari data yang mempunyai nilai paling kecil sampai paling besar.
• Urutan turun (descending) yaitu dari data yang mempunyai nilai paling besar sampai paling kecil.

Contoh : data bilangan 5, 2, 6, dan 4 dapat diurutkan naik menjadi 2, 4, 5, 6 atau diurutkan menjadi 6, 5, 4, 2. Pada data yang bertipe char, nilai data dikatakan lebih kecil atau lebih besar dari yang lain didasarkan pada urutan relative (collating sequence) seperti dinyatakan dalam tabel ASCII. Keuntungan dari data yang sudah dalam keadaan terurut yaitu :

Data mudah dicari, mudah untuk dibetulkan, dihapus, disisipi atau digabungakan. Dalam keadaan terurutkan, kita mudah melakukan pengecekan apakah ada data yang hilang. Misalnya kamus Bahasa, buku telepon. Mempercepat proses pencarian data yang harus dilakukan berulang kali.

Beberapa factor yang berpengaruh pada efektifitas suatu algoritma pengurutan antara lain :

-          Banyak data yang diurutkan.

-          Kapasitas pengingat apakah mampu menyimpan semua data yang kita miliki.

-          Tempat penyimpanan data, misalnya piringan, pita tau kartu, dll.

Beberapa algoritma metode pengurutan dan prosedurnya sebagai berikut :

1. Bubble Sort

Bubble Sort  adalah suatu metode pengurutan yang membandingkan elemen yang sekarang dengan elemen berikutnya. Apabila elemen sekarang > elemen berikutnya, maka posisinya ditukar. Kalua tidak, tidak perlu ditukar. Diberi nama “Bubble” karena proses pengurutan secara berangsur-angsur bergerak/berpindah ke posisinya yang tepat, seperti gelembung yang keluar dari sebuah gelas bersoda.

Proses Bubble Sort:

Data paling akhir dibandingkan dengan data di depanya, jika ternyata lebih kecil atau besar maka tukar sesuai dengan kekuatan ( descending atau ascending). Dan pengecekan yang sama dilakukan terhadap data yang selanjutnya sampai data yang paling awal.

Algoritma Bubble Sort :

1. i=0
2. selama (i<N-1) kerjakan baris 3 sampai 7
3. j=N-1
4. selama (j>=i) kerjakan baris 5 sampai 7
5. jika (Data[j-1] > Data[j]) maka tukar Data[j-1] dengan Data[j]
6. j=j-1
7. i=i+1

prosedur yang menggunakan metode gelembung :

void BubbleSort()

{

            int i,j;

            for(i=1; i<Max; i++)

            for(j=Max-1; j>=I; j--)

            if(Data[j-1] > Data[j])

            Tukar(&Data[j-1], &Data[j]);

}

2. Selection Sort

Metode seleksi melakukan pengurutan dengan cara mencari data yang terkecil kemudian menukarkanya dengan data yang digunakan sebagai acuan atau sering dinamakan pivot. Selama proses, pembandingan dan pengubahan hanya dilakukan pada indeks pembanding saja, pertukaran data secara fisik terjadi pada akhir proses. Proses pengurutan dengan metode seleksi dapat dijelaskan sebagai berikut :

            Langkah pertama dicari data terkecil dari data pertama sampai data terakhir. Kemudian data terkecil ditukar dengan data pertama. Dengan demikian, data pertama sekarang mempunyai nilai paling kecil dibanding data yang lainnya.

            Langkah kedua, data terkecil kita cari mulai dari data kedua sampai terakhir. Data terkecil yang kita peroleh ditukar dengan data kedua dan deikian seterusnya sampai semua elemen dalam keadaan terurutkan.

Algoritma seleksi dapat dituliskan sebagai berikut :

1. i=0
2. selama (i<N-1) kerjakan baris 3 sampai dengan 9
3. k=i
4. j=i+1
5. selama (j<N) kerjakan baris 6 dan 7
6. jika (Data[k] > Data[j]) maka k=j
7. j=j+1
8. Tukar Data[i] dengan Data[k]
9. i=i+1

Di bawah ini merupakan prosedur yang menggunakan metode seleksi :

void SelectionSort()

{

            k=i;

            for(j=i+1; j<Max; j++)

            if(Data[k] > Data[j])

            k=j;

            Tukar(&Data[i], &Data[k]);

            }

}

3. Marger Sort

Algoritma Marge Sort ialah algoritma pengurutan yang berdasarkan pada strategi dovide and conquer. Algoritma ini terdiri dari dua bagian utama, pembagian list yang diberikan untuk di-sort ke dalam beberapa sublist yang lebih kecil, dan sort (mengurutkan) dan marge (menggabungkan) sublist-sublist yang lebih kecil ke dalam list yang sudah diurutkan. Pembagian bisa dikatakan cukup mudah karena sublist-sublist tersebut dibagi kedalam dua sublist yang ukuranya adalah setengah dari ukuran semula. Hal ini terus diulang sampai sublist itu cukup kecil untuk di-sort secara efisien (umumnya telah terdiri dari satu atau dua elemen). Dalam langkah marge dua sublist disatukan kembali dan diurutkan pada saat yang sama. Algoritma untuk merge sort ialah sebagai berikut :

A.    Untuk kasus n=1, maka tabe a sudah terurut sendirinya (langkah solve)

B.     Untuk kasus n>1, maka :

a.       DIVINE: bagi table a menjadi dua bagian, bagian kiri dan bagian kanan, masing-masing bagian berukuran n/2 elemen.

b.      CONOQUER: secara rekursif, terapkan algoritma D-and-C pada masing-masing bagian.

c.       MERGE: gabung hasil pengurutan kedua bagian sehingga diperoleh table a yang terurut.