Daftar Isi :
- Mengenal Sorting Berserta Contoh Source Code Pada Struktur Data
- Contoh Sorting pada Struktur Data
- Proses Algoritma Bubble Sort
- Contoh Source Code Implementasi Algortima Bubble Sort
- Proses Algortima Selection Sort
- Contoh Source Code Implementasi Algortima Selection Sort
- Proses Algoritma Insertion Sort
- Contoh Source Code Implementasi Algortima Insertion Sort
- Contoh Source Code Implementasi Algoritma Quick Sort
Sorting Pada Struktur Data sangat penting dalam sebuah pemrograman komputer. Apa itu Sorting pada struktur data? Sorting adalah proses pengurutan data yang sebelumnya disusun secara acak sehingga tersusun secara teratur menurut aturan tertentu. Pengurutan dapat dilakukan secara ascending (urut naik) dan descending (urut turun)
Sebagai Contoh Sebuah Kamus. Jika Anda ingin mencari terjemahan pada kamus pasti melihat urutan alphabet bukan? Secara tidak langsung itulah manfaat sorting. Jadi akan lebih mudah mencari kata dalam kamus ketika abjad diurutkan sesuai urutan alfabet. Namun Jika Contoh Seperti Gambar dibawah ini bagaimana proses pengurutan secara ascending atau Descending?
Untuk Menyelesaikan Contoh diatas ada banyak metode dalam melakukan Sorting. Algoritma Sorting berdasarkan perbandingan meliputi sebagai berikut :
- pengurutan gelembung (bubble sort)
- pengurutan seleksi (selection sort)
- pengurutan sisip (insertion sort)
- pengurutan cepat (quick sort)
- pengurutan gabung (merge sort)
- pengurutan himpun (heap sort)
- pengurutan shell (shell sort)
- pengurutan pohon (tree sort)
Tentu dari banyak metode tersebut memiliki konsep yang berbeda – beda. Disini akan menjelaskan metode – metode tersebut mulai dari bubble sort.
Bubble Sort ( Pengurutan Gelembung )
Bubble sort (metode gelembung) adalah metode/algoritma pengurutan dengan dengan cara melakukan penukaran data dengan data sebelahnya secara terus menerus sampai bisa dipastikan dalam satu iterasi tertentu tidak ada lagi perubahan (data sudah terurut secara benar).
Berikut Langkah Langkah dari Bubble Sort :
- Input data
- Setiap data, misalnya data pertama akan dibandingkan dengan data yang ada di sebelahnya (dari data kedua sampai selesai).
- Bila data pertama tersebut lebih besar dari data yang ada pada data sesudahnya, dilakukan penukaran tempat atau posisi data.
- Demikian untuk data kedua sampai dengan data terakhir dilakukan dengan cara serupa.
Jika Digambarkan dalam Ilustrasi Gambar seperti berikut :
Bagaimana Mengimplementasi Algoritma Bubble Sort dalam pemrograman. Sangat gampang yang penting pahami terlebih dahulu tahapan tahapan algoritma bubble sort. Berikut contoh Implementasi algoritma bubble sort ke dalam bahasa pemograman C++ :
Selection Sort
Selection Sort adalah algoritma pengurutan data dengan cara membandingkan elemen yang sekarang dengan elemen yang berikutnya sampai dengan elemen yang terakhir. Jika ditemukan elemen lain yang lebih kecil dari elemen sekarang maka dicatat posisinya dan kemudian ditukar.
Algoritma selection sort akan memindai nilai terkecil dari suatu kumpulan data dan jika ada, data tersebut akan diletakkan pada urutan pertama. Begitu selanjutnya untuk urutan kedua dan seterusnya.
Adapun Langkah – Langkah Algoritma Selection Sort seperti berikut :
- Melakukan pengecekan dimulai dari data pertama hingga data ke-n.
- Menentukan data dengan indeks minimum (jika acending) atau maksimum (jika descending) dalam sebuah data tersebut.
- Menukarkan data dengan indeks minimum (jika ascending) atau maksimum (jika descending) dengan bilangan pertama (i = 1) dari data tersebut.
- Mengulangi langkah di atas untuk sisa data bilangan berikutnya (i = i +1) sampai didapatkan urutan yang sesuai
Jika diilustrasikan dalam Gambar untuk Algoritma Selection Sort seperti berikut :
Dan Untuk Source Code Untuk Algoritma Selection dalam bahasa pemrohraman c++ seperti berikut :
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.
Adapun Langkah – Langkan Algoritma Insertion Sort :
- Membandingkan dua elemen data pertama, mengurutkannya,
- Kemudian mengecek elemen data berikutnya satu persatu
- Dan membandingkannya dengan elemen data yang telah diurutkan
Berikut Ilustrasi Gambar Algoritma Insertion Sort :
Dan Berikut Implementasi Algoritma Insertion Sort dalam bahasa pemrograman C++:
Quick Sort
Quick Sort adalah salah satu algoritma pengurutan data yang paling cepat, yaitu dengan membagi list menggunakan sebuah pivot. pemilihan pivot adalah hal yang menentukan apakah algoritma quick sort tersebut akan memberikan performa terbaik atau terburuk.
Berikut beberapa cara pemilihan pivot :
- Pivot dipilih elemen pertama, elemen terakhir, atau elemen tengah array.
- Pivot dipilih secara acak dari salah satu elemen array
Adapun Algoritma Quick Sort seperti berikut :
- Pilih nilai pivot.
- Partisi. Atur ulang semua elemen sedemikian rupa, lalu semua elemen yang lebih rendah daripada pivot dipindahkan ke sebelah kiri dari array/list dan semua elemen yang lebih besar dari pivot dipindahkan ke sebelah kanan dari array/list.
- Nilai yang sama dengan pivot dapat diletakkan di mana saja dari array.
- Urutkan semua bagian (kiri/kanan).
- Aplikasikan algoritma quicksort secara rekursif pada bagian sebelah kiri dan kanan.
- Ada dua indeks i dan j dan pada awal algoritma partisi i menunjuk ke elemen pertama dalam array dan poin j yang terakhir.
- algoritma menggerakkan i ke depan, sampai elemen dengan nilai yang lebih besar atau sama dengan pivot ditemukan.
- Indeks j bergerak mundur, sampai elemen dengan nilai yang lebih rendah atau sama dengan pivot ditemukan.
- Jika i ≤ j maka mereka bertukar dan nilai langkah ke posisi berikutnya (i + 1), langkah-langkah j dengan yang sebelumnya (j - 1).
- Algoritma berhenti, ketika nilai menjadi lebih besar dari j. Setelah partisi, semua nilai sebelum elemen ke-i kurang atau sama dengan pivot dan semua nilai setelah elemen ke-j lebih besar atau sama dengan pivot
Dalam Implementasi Source Code dalam bahasa pemrograman C++ seperti berikut :
Demikian Pengenalan Sorting beserta Contoh SOurce Code pada Struktur Data Semoga bermanfaat
Referensi :
- Antony Pranata, Pemrograman Borland C++, Andi Offset, Yogyakarta
- Moh. Sjukani, Algoritma dan Struktur data dengan C, C++, dan Java, Mitra Wacana Media , 2005
- Walter Savitch , Problem Solving With C++: The Object of Programming, forth edition, Addison Wesley
- Lamhot Sitorus & David J.M. Sembiring, Konsep dan Implementasi Struktur Data dengan C++, Andi Offset, Yogyakarta
- Online Reading, www://cplusplus.com