Ascending Descending sort metode Bubble, Selection dan Insertion dengan C

BAB I

PENDAHULUAN

1.       Latar Belakang

Didalam pemograman terdapat banyak macam-macam program dengan mempunyai ciri khas metodenya tersendiri. Seperti salah satunya yaitu sorting. Metode dari sorting ini terbagi menjadi delapan metode diantaranya, bubble sort, selection sort, insertion sort, shell sort, merge sort, radix sort, quick sort dan heap sort. Pada kesempatan ini penulis akan membahas tentang tiga macam metode sorting, yaitu bubble sort, selection sort dan insertion sort.

Dengan tiga metode sorting terebut penulis akan mengimplementasikannya dalam satu program. Sorting dapat dilakukan secara ascending maupun descending. Dalam program ini terdapat implementasi dari fungsi, seleksi kondisi, looping, array dan pendeklarasian.

2.       Rumusan Masalah

1.      Pengertian sorting.

2.      Pengertian dan prinsip kerja bubble sort.

3.      Pengertian dan prinsip kerja selection sort.

4.      Pengertian dan prinsip kerja insertion sort.

5.      Implementasi tiga metode sorting dalam satu program secara ascending dan descending dalam bahasa C.

a.       Deskripsi program.

b.      Flowchart.

c.       Koding program.

d.      Uji coba program.

BAB II

PEMBAHASAN

1.      Sorting

Sorting dalam hal ini diartikan mengurutkan data yang berada dalam suatu tempat penyimpanan, dengan urutan tertentu baik urutan menaik (ascending) dari nilai terkecil sampai terbesar, atau urut menurun (descending) dari nilai terbesar sampai dengan nilai terkecil. Sorting merupakan proses pengurutan. Dilihat dari tempat penyimpanan data, sort dibedakan antara external sort dan internal sort. External sort bila datanya berada dalam media external, atau external storage, seperti harddisk. Internal sort bila datanya ada dalam internal storage atau memori komputer. Dalam makalah ini yang akan dibahas adalah internal sort dengan data berada dalam array satu dimensi.

Dengan metode:

2.      Bubble Sort

Bubble sort (metode gelembung) adalah metode/algoritma pengurutan dengan cara melakukan penukaran data dengan tepat sebelahnya secara terus menerus sampai bisa dipastikan dalam satu iterasi tertentu tidak ada lagi perubahan. Jika tidak ada lagi perubahan berarti data sudah terurut. Disebut pengurutan gelembung karena masing-masing kunci akan dengan lambat menggelembung ke posisi yang tepat.

Ilutrasi konsep dari bubble sort ini adalah sebagai berikut:

Cara pengurutannya : bandingkan dua data kemudian swap.

Prinsip kerja dari bubble sort adalah:

1.    Pengecekan mulai dari data ke satu sampai data ke-n.

2.    Bandingkan data ke-1 sampai data ke-n dengan data setelahnya.

3.    Jika lebih besar maka tidak terjadi pemindahan atau swap.

4.    Jika data sebelumnya kecil bila dibandingkan dengan data setelahnya besar maka tidak akan terjadi pemindahan atau no swap.

5.    Ulang langkah diatas sampai data bisa tersusun baik secara ascending maupun descending. Sampai data terurutkan.

Metode pengurutan gelembung (Bubble Sort) diinspirasikan oleh gelembung sabun yang berada di permukaan air. Karena berat jenis gelembung sabun lebih ringan daripada berat jenis air, maka gelembung sabun selalu terapung ke atas permukaan. Prinsip di atas dipakai pada pengurutan gelembung.

3.      Selection Sort

 Selection sort adalah metode sorting dimana elemen di perbandingkan satu-persatu sampai pada elemen terakhir dan disusun berdasarkan ketentuan-ketentuan berlaku (terbesar atau terkecil).

Ilutrasi konsep dari selection sort ini adalah sebagai berikut :

Prinsip kerja selection short:

1)   Pengecekan dimulai data ke-1 sampai dengan ke-n.

2)   Tentukan bilangan dengan indeks terkecil dari bilangan tersebut.

3)   Tukar bilangan dengan indeks terkecil tersebut dengan bilangan pertama (I=1) dari data bilangan tersebut.

4)   Lakukan langkah 2 dan 3 untuk bilangan berikutnya (I=I+1) sampai didapatkan urutan yang optimal.

4.      Insertion Sort

Insertion sort adalah sebuah metode pengurutan data dengan menempatkan setiap elemen data pada pisisinya dengan cara melakukan perbandingan dengan data – data yang ada. Indeks algoritma dari metode insertion sort ini dapat dianalogikan sama seperti mengurutkan kartu, dimana jika suatu kartu dipindah tempatkan menurut posisinya, maka kartu yang lain akan bergeser mundur atau maju sesuai kondisi pemindahanan kartu tersebut. Dalam pengurutan data, metode ini dipakai bertujuan untuk menjadikan bagian sisi kiri array terurutkan sampai dengan seluruh array diurutkan.

Penganalogian Insertion Sort dengan pengurutan kartu. Berikut menjelaskan bagaimana algoritma Insertion Sort bekerja dalam pengurutan kartu, Anggaplah kita ingin mengurutkan satu set kartu dari kartu yang bernilai paling kecil hingga yang paling besar.

1)      Dimulai dengan posisi tangan kosong, dan semua kartu berada diatas meja. Dan anggaplah kita akan menyusun kartu ke tangan kiri kita.

2)      Mengamil kartu pertama dari meja dan meletakannya ke tangan kiri.

3)      Mengambil kartu kedua dan membandingkannya dengan kartu yang sudah ada di tangan kiri.

4)      Jika kartu yang diambil dari meja memenuhi syarat perbandingan, maka kartu tersebut akan diletakan didepan kartu yang dibandingkan, serta kartu yang lain yang telah dibandingkan akan bergeser mundur (ke belakang). Proses ini akan berlangsung sampai semua kartu akan terurutkan dengan benar sesuai criteria pengurutannya.

Demikian juga halnya dalam pengurutan data. Jika data sudah ada, maka pengurutan dimulai dengan mengambil satu data dan membandingkannya dengan data-data yang ada didepannya. Jika data yang diambil memenuhi syarat perbandingan, maka data yang diambil tersebut akan diletakan di depan data yang dibandingkan, kemudian data-data yang dibandingkan akan bergeser mundur.

Catatan: Dalam hal pengurutan data dengan metode insertion sort ini, data yang diambil pertama adalah data kedua, kemudian data yang diambil akan dibandingkan dengan data – data yang ada disebelah kiri / data sebelumnya (data- data sebelum data yang diambil). Jika proses tersebut selesai, maka akan dilanjutkan dengan data-data selanjutnya (data ke-3, data ke-4… dan seterusnya). Proses akan berlangsung sampai data – data terurutkan dengan benar.

Berikut adalah simulasi Algoritma Insertion Sort Jika digambarkan secara singkat, maka algoritma Insertion sort ini dapat digambar sebagai berikut.

Ilustrasi konsep insertion sort ini adalah sebagai berikut:

7 [3] 4 1 8 2 6 5

3 7 [4] 1 8 2 6 5

3 4 7 [1] 8 2 6 5

1 3 4 7 [8] 2 6 5

1 3 4 7 8 [2] 6 5

1 2 3 4 7 8 [6] 5

1 2 3 4 6 7 8 [5]

1 2 3 4 5 6 7 [8]

5.      Implementasi tiga metode sorting dalam satu program secara ascending dan descending dalam bahasa C

a.    Deskripsi program

Program ini merupakan gabungan dari ketiga metode sort, diantaranya: bubble sort, selection sort dan insertion sort. Dan program inipun berfungsi dalam mensorting suatu data yang berupa nominal angka. Penyortingan yang dilakukan dapat berbentuk ascending, yaitu dari bilangan terkecil ke yang terbesar atau descending, dari bilangan terbesar ke yang kecil. Dalam program ini disajikan tiga macam metode sorting yang mana user bebas untuk memilih salah satu dari metode sorting yang ada.

Dalam program ini terdapat 11 fungsi, yaitu:

1)             void output

2)             void metodesorting

3)             void carasortingAscending

4)             void carasortingDescending

5)             void bubbleAscending

6)             void bubbleDescending

7)             void selectionAscending

8)             void selectionDescending

9)             void insertAscending

10)         void insertDescending

11)         void main

Dalam koding dari program sorting ini juga, inisialisasi beberapa variabel yang digunakan ditempatkan sebagai variabel global, dimana variabel ini dioperasikan pada beberapa fungsi, sehingga penghematan penempatan varibel yang sama. Variabel yang dijadikan variabel global, yaitu int i, int step dan int tukar. Masing-masing fungsi dari 11 fungsi berfungsi sebagai induk dari suatu proses yang melibatkan subprogram, untuk penghematan penyusunan subprogram dilampirkan pada suatu fungsi tersendiri. Sehingga ketika suatu fungsi “A” berisi subprogram “B”, hanya cukup menampilkan fungsi “B-nya” saja.

Deklarasi-deklarasi yang digunakan diantaranya:

Printf(“statement”);, suatu deklarasi untuk menampilkan statement.

Scanf(“%d”,&a);, suatu deklarasi untuk memasukan suatu nilai pada variabel a.

Scanf(“%d”,&array[n]);, suatu deklarasi untuk memasukan suatu nilai pada array di indeks n.

Printf(“statement=%d”,a);, suatu deklarasi untuk menampilkan statement dan memanggil nilai dari a.

Printf(“statement=%d”,array[n]);, suatu deklarasi untuk menampilkan statement dan memanggil nilai dari array indeks n.

For(i=a;i<a;i++), suatu deklarasi pengulangan dimulai dari i=a, berhenti ketika i<a dan langkah pengulangan i++.

If(i=a) { eksekusi; }, suatu deklarasi seleksi kondisi jika nilai i=a maka eksekusi; dijalankan.

If(i=a) { eksekusi1; } else if(i=b) { eksekusi2; } else { eksekusi3 }, suatu deklarasi seleksi kondisi dengan ada kondisi berikutnya jika kondisi pertama tidak memenuhi syarat, yaitu jika i=a maka eksekusi1; dijalankan, jika i=b maka eksekusi2; dijalankan dan jika i!=a ataupun i!=b maka eksekusi3  dijalankan.

Switch(nilai) { case a: eksekusi1; break; case b: eksekusi2; break; default: eksekusi3; }, suatu deklarasi seleksi kondisi jika nilai=a maka eksekusi1; dijalankan, jika nilai=b maka eksekusi2; dijalankan dan jika nilai!=a ataupun nilai!=b maka eksekusi3; dijalankan.

Array[n];, suatu variabel array, yaitu variabel yang dapat menyimpan suatu nilai dengan jenis yang sama sebanyak n buah.

A=B;, suatu deklarasi bahwa A itu memiliki nilai B.

Array[n]=Array[n-1];, suatu deklarasi bahwa isi nilai dari array n itu memiliki isi nilai dari array n-1.

Void main(), yaitu fungsi utama, dimana semua deklarasi-deklarasi ataupun fungsi-fungi dieksekusi didalam kendali Void main().

Getch();, suatu deklarasi untuk meminta satu karakter sebelum program hasil running di-exit.

Void Data(int x, int y) dan Data(x,y);, suatu deklarasi fungsi dengan sistem kembalian void, dimana  fungsi Void Data(int x, int y) dipanggil oleh Data(x,y) dengan nilai x dan y adalah sama.

Secara umum sistematika program ini diilustrasikan pada gambar 5.a.1, dimana user harus memasukan jumlah indeks, kemudian memasukan angka-angka sebanyak jumlah indeks yang dimasukan sebelumnya, kemudian memilih metode sorting antara ascending atau descending, kemudian memilih subprogram sorting antara bubble, selection atau insertion dan terakhir output akan ditampilkan. Ilustrasi ditunjukan pada gambar berikut ini.

Gambar 5.a.1 Ilustrasi Program

b.   Flowchart (terlampir)

Flowchart dari program sorting ini ditampilkan dalam sebuah lampiran halaman tersendiri secara keseluruhan.

c.    Koding program

Koding dari program sorting ini ditampilkan secara keseluruhan dihalam berikutnya beserta keterangan ditiap segmen barisnya.

d.   Uji coba program

Gambar 1.1 Tampilan Awal

Gambar 1.2 Metode bubble secara ascending

           

Gambar 1.3 Metode bubble secara descending

            

Gambar 1.4 Metode selection secara ascending

Gambar 1.5 Metode selection descending

            

Gambar 1.6 Metode insertion ascending

Gambar 1.7 Metode insertion descending

BAB III

PENUTUP

SIMPULAN

Sorting merupakan suatu proses (operasi) yang mengurutkan data dalam suatu urutan yang dikehendaki. Pengurutan dapat dilakukan secara ascending (urut naik) maupun descending (urut turun). Sorting ini dibagi menjadi banyak metode diantaranya bubble sort, selection sort dan insertion sort.

Dari ketiga macam metode tersebut dapat diimplementasikan menjadi satu program, seperti yang telah dilakukan oleh penulis di atas. Penggabungan ke-tiga metode sorting dalam satu program tersebut dapat dilakukan dengan menggunakan banyak fungsi.  

Semoga makalah ini dapat bermanfaat bagi pembaca. Penulis berpesan kepada segenap pembaca untuk tidak bosan berlatih, karena ilmu itu harus diikat dengan menulisnya, maka pemrograman pun harus diikat dengan sering membuat kodingannya. Dan jangan pernah bosan untuk terus mencari ilmu, karena allah SWT telah berfirman: “ditinggikanlah derajatnya orang yang berilmu.”

DAFTAR PUSTAKA

Sjukani, Moh. 2013. ALGORITMA (Algoritma & Struktur Data 1) dengan C, C++, dan Java. Jakarta: Mitra Wacana Media.