Metode Pengurutan data dan contoh array

Metode Pengurutan Data

Pengurutan Gelembung (Bubble Sort)

Pengurutan gelembung adalah algoritma pengurutan yang paling tua dan sederhana untuk diimplementasikan. Algoritma ini juga cukup mudah untuk dimengerti.

• Metode sorting termudah
• Diberi nama “Bubble” karena proses pengurutan secara berangsur angsur bergerak/berpindah ke posisinya yang tepat, seperti gelembung yang keluar dari sebuah gelas bersoda.
• Bubble Sort mengurutkan data dengan cara membandingkan elemen sekarang dengan elemen berikutnya.
• Jika elemen sekarang lebih besar dari elemen berikutnya maka kedua elemen tersebut ditukar, jika pengurutan ascending.
• Jika elemen sekarang lebih kecil dari elemen berikutnya, maka kedua elemen tersebut ditukar, jika pengurutan descending.
• Algoritma ini seolah-olah menggeser satu per satu elemen dari kanan ke kiri atau kiri ke kanan, tergantung jenis pengurutannya.
• Ketika satu proses telah selesai, maka bubble sort akan mengulangi proses, demikian seterusnya.
• Kapan berhentinya? Bubble sort berhenti jika seluruh array telah diperiksa dan tidak ada pertukaran lagi yang bisa dilakukan, serta tercapai perurutan yang telah diinginkan.

Algoritma ini bekerja dengan cara membandingkan nilai tiap elemen dalam table dengan elemen setelahnya, dan menukar nilainya jika sesuai dengan kondisi yang diperlukan. Proses ini akan terus berulang hingga seluruh elemen dalam tabel telah diproses dan elemen dalam tabel telah terurut.
Algoritma pengurutan gelembung ini adalah algoritma yang paling lamban dan tidak mangkus dibandingkan dengan algoritma pengurutan yang lain dalam penggunaan secara umum. Dalam kasus terbaik (yaitu list sudah terurut), kompleksitas algoritma pengurutan gelembung adalah O(n). Namun, untuk kasus umum, kompleksitas algoritma pengurutan gelembung adalah O(n2).


Grafik di atas menggambarkan kompleksitas algoritma dari pengurutan gelembung.

Pengurutan Cangkang (Shell Sort)

Shell sort adalah algoritma dengan kompleksitas algoritma O(n2) dan yang paling efisien dibanding algoritma-algoritma lain dengan kompleksitas algoritma yang sama. Algoritma shell sort lima kali lebih cepat dibandingkan algoritma pengurutan gelembung dan dua kali lebih cepat dibandingkan algoritma pengurutan dengan penyisipan. Dan tentu saja shell sort juga merupakan algoritma yg paling yang paling kompleks dan sulit dipahami.
Algoritma shell sort melakukan pass atau traversal berkali-kali, dan setiap kali pass mengurutkan sejumlah nilai yang sama dengan ukuran set menggunakan insertion sort. Ukuran dari set yang harus diurutkan semakin membesar setiap kali melakukan pass pada tabel, sampai set tersebut mencakup seluruh elemen tabel. Ketika ukuran dari set semakin membesar, sejumlah nilai yang harus diurutkan semakin mengecil. Ini menyebabkan insertion sort yang dijalankan mengalami kasus terbaik dengan kompleksitas algoritma mendekati O(n). Ukuran dari set yang digunakan untuk setiap kali iterasi (iteration) mempunyai efek besar terhadap efisiensi pengurutan.
Tetapi, walaupun tidak se-efisien algoritma merge sort, heap sort, atau quick sort , algoritma shell sort adalah algoritma yang relatif sederhana. Hal ini menjadikan algoritma shell sort adalah pilihan yang baik dan efisien untuk mengurutkan nilai dalam suatu tabel berukuran sedang (mengandung 500-5000 elemen).


Grafik di atas menggambarkan kompleksitas algoritma dari shell sort.

Pengurutan Cepat (Quick Sort)
Algoritma quick sort sangat sederhana dalam teori, tetapi sangat sulit untuk diterjemahkan ke dalam sebuah code karena pengurutan dilakukan dalam sebuah list dan diproses secara rekursif. Algoritma ini terdisi dari empat langkah (yang mana menyerupai merge sort) yaitu :

• Memilih sebuah elemen untuk dijadikan poros atau pivot point (biasanya elemen paling kiri dari tabel).
• Membagi tabel menjadi dua bagian, satu dengan elemen yang lebih besar dari poros, dan satu lagi untuk elemen yang lebih kecil dari poros.
• Mengulang algoritma untuk kedua buah tabel secara rekursif.

Tingkat keefektifan dari algoritma ini dangat bergantung pada elemen yang dipilih menjadi poros. Kasus terburuk terjadi ketika tabel sudah terurut dan elemen terkecil di sebelah kiri menjadi poros. Kasus ini mempunyai kompleksitas algoritma O(n2). Maka dari itu sangat disarankan untuk memilih poros bukan dari elemen paling kiri dari tabel, tetapi dipilih secara random. Selama poros dipilih secara random, algoritma quick sort mempunyai kompleksitas algoritma sebesar O(n log n).
Algoritma quick sort mengurutkan dengan sangat cepat, namun algoritma ini sangat komplex dan diproses secara rekursif. Sangat memungkinkan untuk menulis algoritma yang lebih cepat untuk beberapa kasus khusus, namun untuk kasus umum, sampai saat ini tidak ada yang lebih cepat dibandingkan algoritma quick sort.
Walaupun begitu algoritma quick sort tidak selalu merupakan pilihan yang terbaik. Seperti yang telah disebutkan sebelumnya, algoritma ini dilakukan secara rekursif yang berarti jika dilakukan untuk tabel yang berukuran sangat besar, walaupun cepat, dapat menghabiskan memori yang besar pula. Selain itu, algoritma ini adalah algoritma yang terlalu komplex untuk mengurutkan tabel yang berukuran kecil (hanya puluhan elemen misalnya). Selain itu algoritma quick sort mempunyai tingkat efisiensi yang buruk ketika dioperasikan pada tabel yang hampir terurut atau pada tabel yang terurut menurun.

Grafik di atas menggambarkan kompleksitas algoritma dari quick sort.

Contoh Program Array dengan C++ :

Hasil :