Sorting Array (JAVA)

Sorting
Salah satu bagian penting dari struktur data adalah proses pengurutan data-data  itu sendiri. Data akan terkadang akan berada dalam bentuk yang tidak berpola ataupun dengan pola tertentu yang tidak kita inginkan, namun dalam penggunaanya, kita akan selalu ingin menggunakan data-data tersebut dalam bentuk yang rapi atau berpola sesuai dengan yang kita inginkan. Maka dari itu proses sorting adalah proses yang sangat penting dalam struktur data, terlebih untuk pengurutan data yang bertipe numerik ataupun karakter.

Sorting adalah proses menyusun kembali data yang sebelumnya telah disusun dengan suatu pola tertentu ataupun secara acak, sehingga menjadi tersusun secara teratur menurut aturan tertentu.


Pada umumnya ada 2 macam pengurutan, yaitu:

• Pengurutan secara ascending (urut naik).
• Pengurutan secara descending (urut turun).

Algoritma untuk melakukan sorting juga ada berbagai macam, antara lain:

1. Teoretis : Computational complexity theory, Big O notation, Total order, Stability, Comparison sort.
2. Exchange sorts : Exchange sort, Bubble sort, Cocktail sort, Comb sort, Gnome sort, Quick sort.
3. Selection sorts  : Selection sort, Heap sort, Smooth sort.
4. Insertion sorts   : Insertion sort, Shell sort, Tree sort, Library sort, Patience sorting.
5. Merge sorts     : Merge sort.
6. Non-comparison : Radix sort, Bucket sort, Counting sort, Pigeonhole sort.
7. Others  : Topological sorting, Sorting network.

Algoritma-algoritma ini tentu saja akan mempunyai efek yang berbeda dalam setiap prosesnya, ada yang mudah digunakan, ada yang mempunyai proses yang sangat cepat, dan sebagainya.
Pemilihan algoritma untuk sorting ini tidak hanya asal saja dipilih. Pemilihian ini semestinya berdasarkan kebutuhan yang diperlukan. Tidak semua algortima yang pendek itu buruk dan tidak semua algoritma yang super cepat juga akan baik dalam semua kondisi. Misal: algoritma Quick Sort adalah algoritma sorting yang tercepat dalam proses pencariannya, namun jika data yang akan diurutkan ternyata sudah hampir terurut atau tidak terlalu banyak, maka algoritma ini malah akan memperlama proses pengurutan itu sendiri, karena akan banyak perulangan tidak perlu yang dilakukan dalam proses sorting ini.
Hal yang umum dilakukan dalam proses sorting adalah proses pertukaran antara 2 elemen atau lebih (analogi memindah air dalam gelas). Untuk melakukan proses pertukaran akan diperlukan adanya variable baru yang digunakan sebagai variable penampung.

Sebagai contoh saya akan buat satu deklarasi sebagai berikut ;


Buble Sort
Berikut adalah deklarasi dari Sorting jenis ini :

• Metode sorting paling mudah, namun paling lambat dibandingkan dengan yang lain.
• Bisa dilakukan baik dari kepala array maupun ekor array.
• Bubble sort mengurutkan data dengan cara membandingkan elemen sekarang dengan elemen berikutnya.
• Proses yang berlangsung, jika: Ascending: jika elemen sekarang lebih besar daripada elemen berikutnya, maka kedua elemen tersebut ditukar. Descending: jika elemen sekarang lebih kecil daripada elemen berikutnya, maka kedua elemen tersebut ditukar.
•  Hal ini akan terlihat seperti penggeseran angka, perbandingan, kemudian jika memenuhi syarat kemudian tukar.
•  Proses penukaran ini akan terus dilakukan hingga seluruh array telah diperiksa.

Contoh fungsi nya :

Exchange Sort
Berikut adalah deklarasi dari Sorting jenis ini :

• Mirip dengan bubble sort.
• Perbedaannya: dalam exchange sort ada elemen yang berfungsi sebagai pusat (pivot), pertukaran hanya akan dilakukan jika diperlukan saja dari pivot tersebut.
• Sedangkan bubble sort akan membandingkan elemen pertama/terakhir dengan elemen sebelumnya/sesudahnya, kemudian elemen sebelum/sesudahnya itu akan menjadi pusat (pivot) untuk dibandingkan dengan elemen sebelumnya/sesudahnya lagi, begitu seterusnya.

Contoh fungsi nya :

Selection Sort
Berikut adalah deklarasi dari Sorting jenis ini :

• Kombinasi sorting dan searching.
• Untuk setiap proses, akan dilakukan dengan mencari elemen dari posisi yang belum diurutkan dan kemudian memilih elemen yang memiliki nilai terkecil atau terbesar yang akan ditukarkan ke posisi yang tepat di dalam array.
• Misalnya untuk putaran pertama, akan dicari data dengan nilai terkecil dan data ini akan ditempatkan pada indeks terkecil, pada putaran kedua akan dicari data kedua terkecil, dan akan ditempatkan di indeks kedua, negitu seterusnya hingga tidak ada data yang dicari lagi.
• Selama proses, pembandingan dan pengubahan hanya dilakukan pada indeks pembanding saja, pertukaran data secara fisik terjadi pada akhir proses.

Contoh fungsi nya :

Insertion Sort
Berikut adalah deklarasi dari Sorting jenis ini :

• Analogi pengurutan kartu.
• Proses dilakukan dengan membandingkan data ke-I dengan data yang sebelum-sebelumnya.
• Misal ascending: pengurutan dimulai dari data ke-2 sampai dengan data terakhir, jika ditemukan data yang lebih kecil, maka akan dimasukkan di posisi yang seharusnya.
• Pada penyisipan elemen, maka elemen-elemen lain akan bergeser ke belakang.

Contoh fungsi nya :
Quick Sort
Berikut adalah deklarasi dari Sorting jenis ini :

• Bersifat divide&conquer.
• Merupakan metode pencarian yang sangat cepat (saat ini tercepat).
• Pertama-tama deret dibagi menjadi dua bagian, misal, semua elemen pada bagian b (bagian pertama) mempunyai kurang dari atau sama dengan semua elemen pada bagaian c (bagian kedua -- membagi). Kemudian kedua bagian tersebut dilakukan proses sorting dengan rekursif secara terpisah dengan prosedur yang sama(coquer). Kemudian gabungkan lagi kedua bagian terpisah tersebut.

Langkah-langkahnya :

• Memilih sebuah elemen pembanding (pivot), misal x.
• Semua elemen dari deret tersebut yang kurang dari x diletakkan pada bagian pertama.
• Kemudian semua elemen dari yang lebih besar dari x diletakkan pada bagian kedua.
• Untuk elemen yang sama dengan x bias diletakkan di mana saja bahkan bisa juga di antara kedua bagian tersebut.

Algoritma Partisi :

• setelah mempartisi, prosedur sorting akan dilakukan secara rekursif. Hingga proses rekursif tersebut akan berhenti saat sebuah bagian hanya tinggal terdapat satu elemen saja.
• Tidak baik digunakan jika elemen-elemen yang akan diurutkan hanya ada sedikit atau sudah hamper terurut, karena jika menggunakan metode ini justru akan melakukan perulangan yang tidak berguna dan lama.
• Mempunyai algoritma dan program yang cukup kompleks.

Contoh fungsi nya :

Sekian, Selamat Belajar :D