[Praktikum Algoritma dan Struktur Data] Modul III - Sorting

MODUL  III

SORTING

3.1. TUJUAN

1. Mahasiswa dapat memahami algoritma sorting.

2. Mahasiswa dapat mengimplementasikan metode sorting dalam program.

3.2. DASAR TEORI

1. Pengertian Sorting

Sorting adalah suatu proses pengurutan data yang sebelumnya disusun secara acak atau tidak teratur menjadi urut atau teratur menurut suatu aturan tertentu. Pengurutan dapat dilakukan secara ascending (urut naik) maupun descending (urut turun).

2. Jenis-jenis sorting 

a. Bubble Sort

Bubble sort adalah suatu metode pengurutan yang membandingkan elemen sekarang dengan elemen berikutnya.

Algoritma :

1) Tentukan data-data yang akan diurutan dan disimpan dalam array.

2) Lakukan pengulangan dari data-data tersebut.

3) Lakukan pembandingan antara data yang satu dengan data yang lainnya, dimana kalau data yang satu lebih kecil dari data yang lain, maka posisinya ditukar. Kalau tidak, cek data selanjutnya.

4) Ulangi langkah 3, sampai semua data terurut.

5) Tampilkan data hasil pembandingan.

b. Straight Selection Sort

Selection sort adalah suatu metode pengurutan yang membandingkan elemen sekarang dengan elemen berikutnya sampai yang terakhir. Jika ditemukan elemen yang lebih kecil dari elemen yang sekarang maka dicatat posisinya dan langsung ditukar.

Algoritma :

1) Tentukan data-data yang akan diurutkan dan simpan dalam array.

2) Lakukan pengulangan dari data-data tersebut.

3) Seleksi data, cek apakah hasil seleksi data  yang  ditampung lebih besar dari data.

4) Jika pengecekan langkah 3 bernilai “true” lakukan pertukaran      posisi antara data yang ditampung dengan data terkecil.

5) Ulangi langkah 3 sampai 4, hingga nilai i sama dengan n.

c. Insertion Sort 

Insertion sort adalah sebuah algoritma pengurutan yang membandingkan dua elemen data pertama, mengurutkannya, kemudian mengecek elemen data berikutnya satu persatu dan membandingkannya dengan elemen data yang telah diurutkan. Cara pengurutannya dimulai dari data ke-2 sampai dengan data terakhir, jika ditemukan data yang lebih kecil, maka akan ditempatkan diposisi yang seharusnya. 

Algoritma :

1) Ambil satu data ke-i simpan di temp. Bandingkan data temp dengan data yang ada disebelah kiri satu per-satu 

2) Cek apakah data temp lebih kecil dari data sebelah kiri. 

3) Jika langkah nomor 3 bernilai “true” lakukan pergeseran data satu-persatu kemudian pada posisi yang tepat sisipkan data temp. 

4) Ulangi langkah 1 sampai 4, hingga i sama dengan n. 

d. Merge Sort 

Merge sort adalah pengurutan yang dilakukan dengan teknik merge (menggabungkan) dua buah array kedalam sebuah array yang baru. Algoritma merge sort membagi tabel menjadi dua tabel yang sama besar. Masing-masing tabel diurutkan secara rekursif, dan kemudian digabungkan kembali untuk membentuk tabel yang terurut. Implementasi dasar dari algoritma merge sort memakai tiga buah tabel, dua untuk menyimpan elemen dari tabel yang telah di bagi dua dan satu untuk menyimpan elemen yang telah terurut.

Algoritma : 

1. Tentukan data – data yang akan diurutkan dan disimpan dalam array.

2. Lakukan pengulangan dari data – data tersebut.

3. Data – data yang ada dibagi menjadi 2 bagian dimana bagian pertama merupakan setengah (jika data genap) atau setengah minus satu (jika data ganjil) dari seluruh data.

4. Lakukan pemecahan kembali untuk masing-masing blok sampai hanya terdiri dari satu data tiap blok. 

5. Setelah itu digabungkan kembali dengan membandingkan pada blok yang sama apakah data pertama lebih besar dari pada data ke-1, jika ya maka data ke-1 dipindah sebagai data pertama, kemudian data ke-pertama sampai ke-tengah digeser menjadi data ke-dua sampai ke-1. Data dibandingkan seterusnya sampai menjadi satu blok utuh seperti awalnya.

6. Tampilkan data hasil pembandingan.

3.3. PERMASALAHAN

Membuat program menggunakan double linked list dengan bubble sort, straight selection sort, insertion sort dan merge sort. 

3.4. HASIL DAN PEMBAHASAN

1. Algoritma 

a. Tambah data :

1) Membuat sebuah node baru bernama x.

2) Jika head sama dengan NULL, maka node baru dijadikan head dan tail.

3) Jika tidak, pointer before node baru tersebut dihubungkan dengan tail, pointer next tail dihubungkan dengan node baru dan kemudian tail dipindahkan ke node baru.

4) Setiap data ditambah, ukuran linked list juga ditambah, dan jika data dikurang, ukuran linked list dikurang.

b. Bubble sorting:

1) Memposisikan node sementara bernama tmp1 ke head.

2) Melakukan perbandingan antara isi data node tmp1 dengan node selanjutnya yang diberinama tmp2. Jika data dalam node tmp1 lebih besar dari data di node tmp2, tukar data dalam ke dua node tersebut. Jika tidak, geser posisi tmp2 kekanan.

3) Menggeser posisi tmp1 kekanan.

4) Mencetak proses pengurutan data-data dalam node.

5) Mengulangi langkah 1 sampai 4 sampai semua data terurut dengan benar.

c. Insertion Sorting :

1) Memposisikan node sementara bernama tmp1 ke head dan tmp2 ke data yang berada diposisi kedua.

2) Melakukan perbandingan antara isi data node tmp2 dengan isi data node tmp1. Jika data dalam node tmp2 lebih kecil dari data di node tmp1, tukar data dalam ke dua node tersebut. Jika tidak, geser posisi tmp2 kekanan.

3) Mencetak proses pengurutan data-data dalam node.

4) Mengulangi langkah 1 sampai 3 hingga semua data terurut dengan benar.

d. Cetak :

a) Memposisikan node sementara bernama tmp ke head.

b) Melakukan perulangan pada node tmp sampai nilai tmp sama dengan NULL.

c) Mencetak data yang ada dalam node tmp.

2. Source code

3. Hasil run program

Gambar 3.1 Tampilan fungsi addfront

Gambar 3.2 Tampilan fungsi bubblesort

Gambar 3.3 Tampilan fungsi insertion

3.5. ANALISA 

• “void insertion()” merupakan sebuah fungsi untuk mengurutkan data dengan metode insertion sort.

• “node *i”, “node *j” dan “node *tmp2” merupakan pendeklarasian variabel I, j dan tmp2.

• “node *tmp1=head”, mendeklarasikan variabel “tmp1” berada pada “head”.

• “for(i=tmp1->next;i!=NULL;i=i->next)” merupakan perulangan untuk mengecek data sampai data terakhir.

• “tmp2->data=i->data” mendeklarasikan nilai “tmp2” sama dengan “i”.

• “for(j=i->before;j!=NULL;j=j->before)” merupakan perulangan untuk kembali mengecek data dari belakang.

• Dibuatkan sebuah kondisi “if(tmp2->data > j->data)”, jika nilai pada “tmp2” lebih besar dari nilai “j”, maka akan menjalankan statement “j->next->data=j->data”, yaitu nilai di list setelah “j” akan berpindah menjadi “j”.

• Setelah itu “j->data=tmp2->data”, nilai yang ada pada “j” tadi akan berpindah pada variabel “tmp”, maka data akan tertukar.   

• “cetak()”, digunakan dalam fungsi untuk memangil fungsi cetak dengan menampilkan step by step dari penukaran data.

• “void bubblesort()” merupakan fungsi untuk mengurutkan data dengan cara membandingkan data satu per satu.

• “for (int i = 0; i<size+1 ; i++)” merupakan perulangan untuk mengecek jumlah datanya.

• “node *tmp = head”, yaitu menempatkan variabel “tmp” pada “head”.

• “for ( int j = 0; j < size-1; j++)”, merupakan perulangan yang akan mengecek data dari akhir setelah dilakukan perulangan sebelumnya.

• “if(tmp->data > tmp->next->data)”, jika nilai “tmp” lebih besar dari setelahnya, maka “tmp2 =tmp->data”, yaitu nilai “tmp2”-nya sama dengan “tmp”.

• “tmp->data=tmp->next->data”, nilai “tmp” sama dengan nilai setelahnya.

• “tmp->next->data=tmp2”, nilai data setelah “tmp” akan bertukar tempat dengan “tmp2”.

• “tmp=tmp->next”, merupakan statement yang dijalankan apabila kondisinya tidak terpenuhi.

• “void cetak()” merupakan sebuah fungsi untuk menampilkan hasil program dengan mendeklarasikan variabel “tmp” berada pada “head”.

• Jika node-nya kosong maka akan dicetak "data kosong", namun jika tidak maka, dibuatkan sebuah perulangan untuk untuk menampilkan data yang telah diurutkan.

• Script tersebut merupakan fungsi utama yang akan digunakan untuk melakukan pemanggilan fungsi-fungsi yang telah dibuat dengan menggunakan switch case untuk mempermudah dalam pemilihan program pengurutan yang ingin dipilih.

3.6. KESIMPULAN

1. Sorting merupakan kegiatan mengurutkan data baik dari yang terkecil ke terbesar (ascending) maupun dari yang terbesar ke terkecil (descending). Cara pengurutannya atau algoritmanya disesuaikan dengan jenis sorting yang digunakan. 

2. Sorting terdiri dari beberapa jenis, diantaranya bubble sort, straight selection sort, insertion sort dan merge sort. Dalam pengaplikasiannya didalam program, dapat dipilih metode mana yang tepat untuk digunakan dalam sebuah program.