Sorting Algorithms in Java

Halo Arek Blodhil! hari ini kita akan belajar... yap you guessed it. SORTING!!! 

Sorting (Menyortir) data berarti mengaturnya dalam urutan tertentu, seringkali dalam struktur data seperti larik (array). Anda dapat menggunakan berbagai kriteria pengurutan, yang umum adalah pengurutan nomor dari paling kecil ke paling besar (ascending) atau sebaliknya (descending), atau mengurutkan string secara leksikografis.

Ada berbagai algoritme pengurutan, dan tidak semuanya sama efisiennya. Aku akan menganalisis kerumitan waktu mereka untuk membandingkannya dan melihat mana yang berkinerja terbaik ya Arek Blodhil!

Jadi tiga algoritme sorting yang akan aku bahas di sini adalah pertama Bubble Sort, kedua Insertion Sort, lalu yang terakhir adalah Selection Sort. Bear with me rek!

BUBBLE SORT

Bubble Sort bekerja dengan menukar elemen yang berdekatan jika tidak dalam urutan yang diinginkan. Proses ini berulang dari awal array hingga semua elemen tersusun rapi.

Perhatikan ya Arek Blodhil! Kita tahu bahwa semua elemen berurutan ketika kita berhasil melakukan iterasi keseluruhan tanpa menukar sama sekali - maka semua elemen yang kita bandingkan berada dalam urutan yang diinginkan dengan elemen yang berdekatan, dan dengan ekstensi, seluruh array.

Berikut adalah representasi visual tentang cara kerja Bubble Sort:

Seperti yang Anda lihat, nama itu sendiri berasal dari ilusi visual elemen yang "bubbling up" ke tempat yang diinginkan. Jika Anda mengikuti elemen tertentu, katakanlah, 8 - Anda dapat melihatnya "bubbling up" ke tempat yang benar dalam contoh ini.

Kita akan menerapkan Bubble Sort dengan cara yang sama. Fungsi kita memasuki while loop di mana ia melewati seluruh array yang bertukar sesuai kebutuhan.

maka akan menghasilkan output :

Untuk mengetahui kompleksitas waktu Bubble Sort, kita perlu melihat skenario terburuk yang mungkin terjadi. Berapa frekuensi maksimum yang kita perlukan untuk melewati seluruh array sebelum kita mengurutkannya? Perhatikan contoh berikut:

5 4 3 2 1

Pada iterasi pertama, 5 akan "menggelembung ke permukaan," tetapi elemen lainnya akan tetap dalam urutan menurun. Kami harus melakukan satu iterasi untuk setiap elemen kecuali 1, dan kemudian iterasi lain untuk memeriksa bahwa semuanya beres, jadi total 5 iterasi.

Perluas ini ke array apa pun yang terdiri dari n elemen, dan itu berarti Anda perlu melakukan n iterasi. Melihat kodenya, itu berarti while loop kita bisa berjalan maksimal n kali.

Masing-masing dari n kali itu kita melakukan iterasi melalui seluruh array (for-loop dalam kode), yang berarti kompleksitas waktu kasus terburuk adalah O (n ^ 2).

Catatan: Kompleksitas waktu akan selalu O (n ^ 2) jika bukan karena pemeriksaan boolean yang diurutkan, yang menghentikan algoritme jika tidak ada swap dalam loop dalam - yang berarti bahwa array diurutkan. Karena Bubble sort mampu mendeteksi kesalahan kecil dalam penyortiran, maka bubble sort digunakan dalam grafik komputer, dan polygon filling algorithm.

Bisa kita simpulkan untuk kelebihan dan kekurangan Bubble Sort adalah sebagai berikut :

• Kelebihan
• Proses penghitungan Bubble sort merupakan metode yang paling sederhana.
• Algoritma Bubble Sort mudah dipahami.
• Langkah atau tahapan dalam pengurutan data sangat sederhana.
• Kekurangan
• Proses penghitungan Bubble Sort menggunakan metode pengurutan termasuk paling tidak efisien walaupun dianggap sederhana. Karena proses pengurutan data dilakukan dengan tahapana satu - satu, mulai dari data paling awal sebelah kiri, sampai data terakhir.
• Ketika data yang kita punya banyak atau dalam jumlah yang besar, maka proses penghitungan akan semakin lama dan lambat. Karena proses pengurutan data secara tunggal (satu - satu).
• Jumlah pengulangan akan tetap sama sampai ke data yang terakhir, walaupun sebagian data yang ada telah terurut.

INSERTION SORT

Insertion Sort adalah salah satu algoritme pengurutan yang lebih sederhana, yang bekerja jauh lebih cepat pada koleksi yang lebih kecil daripada pengantar Bubble Sort dan bahkan Selection Sort meskipun semuanya algoritme kuadratik (O (n2) sederhana.

Ini bagus untuk koleksi yang hampir diurutkan dan kecil (~ 10 elemen) yang membuatnya sangat berguna saat digunakan dalam kombinasi dengan algoritme pengurutan lain yang lebih canggih seperti Quicksort atau Merge Sort. Implementasi sort () resmi Java dari Collections API menggunakan Dual Pivot Quicksort, meskipun menggunakan Insertion Sort untuk koleksi ukuran 7.

Ini umumnya diimplementasikan secara imperatif (meskipun bisa juga rekursif), dan mewakili algoritme stabil di tempat yang bekerja dengan sangat baik pada kumpulan data kecil.

Ini berarti bahwa ini mempertahankan urutan relatif elemen duplikat setelah pengurutan (di tempat) dan tidak memerlukan memori tambahan untuk pengurutan dengan kompleksitas ruang O (1) konstan (stabil).

Insertion Sort bekerja sangat mirip dengan manusia yang menyortir kartu di tangan mereka dengan membagi koleksi menjadi dua bagian - diurutkan dan tidak diurutkan.

Ini kemudian melintasi partisi yang tidak diurutkan dan menyisipkan setiap elemen di tempat yang relatif benar dalam array yang diurutkan.

Berikut adalah representasi visual dari cara kerjanya:

Implementasi Insertion Sort dapat Arek Blodhil liat di bawah ini. Aku memasukkan input {12, 11, 13, 5, 6}

Sehingga menghasilkan output berupa array yang sudah terurut

Sekali lagi, kita harus melihat skenario kasus terburuk untuk algoritme kita, dan ini akan menjadi contoh lagi di mana seluruh array menurun.

Ini karena di setiap iterasi, kita harus memindahkan seluruh daftar yang diurutkan satu per satu, yaitu O (n). Kita harus melakukan ini untuk setiap elemen di setiap array, yang berarti akan dibatasi oleh O (n ^ 2). Insertion Sort lebih baik tidak digunakan untuk menangani struktur data dengan lebih dari 2000 elemen. Maka dapat kita simpulkan kelebihan dan kekurangan Insertion Sort.

• Kelebihan
• Sederhana dalam penerapannya.
• Mangkus dalam data yang kecil.
• Jika list sudah terurut atau sebagian terurut maka Insertion Sort akan lebih cepat dibandingkan dengan Quicksort.
• Mangkus dalam data yang sebagian sudah terurut.
• Lebih mangkus dibanding Bubble Sort dan Selection Sort.
• Loop dalam pada Inserion Sort sangat cepat, sehingga membuatnya salah satu algoritma pengurutan tercepat pada jumlah elemen yang sedikit.
• Stabil.
• Kekurangan
• Banyaknya operasi yang diperlukan dalam mencari posisi yang tepat untuk elemen larik.
• Untuk larik yang jumlahnya besar ini tidak praktis.
• Jika list terurut terbalik sehingga setiap eksekusi dari perintah harus memindai dan mengganti seluruh bagian sebelum menyisipkan elemen berikutnya.
• Membutuhkan waktu O(n2) pada data yang tidak terurut, sehingga tidak cocok dalam pengurutan elemen dalam jumlah besar.

SELECTION SORT

Selection Sort adalah algoritme pengurutan perbandingan di tempat yang menggunakan brute force untuk mengurutkan array.

Di tempat berarti algoritme menggunakan sejumlah kecil ruang konstan untuk penyimpanan ekstra.

Ini disebut algoritma "brute force" karena menggunakan cara yang paling sederhana dan tidak efektif untuk menghitung solusi. Namun, itu menebusnya dengan penerapannya yang langsung.

Algoritme membagi array menjadi dua subarray:

• Sebuah subarray yang diurutkan
• Subarray yang tidak disortir

Subarray yang diurutkan kosong di awal. Dalam setiap iterasi, elemen terkecil dari array yang tidak disortir akan ditambahkan ke akhir array yang diurutkan dengan menukar. Dengan cara ini, array yang diurutkan pada akhirnya akan berisi semua elemen dari array asli.

Contoh larik yang ingin kita urutkan dalam urutan menaik:

Berikut adalah representasi visual dari cara kerjanya:

Implementasi Selection Sort dapat Arek Blodhil liat di bawah ini. Aku memasukkan input {16, 5, 30, 6, 2, 7}

Sehingga menghasilkan output berupa array yang sudah terurut

Kompleksitas waktu rata-rata dan kasus terburuk dari Selection Sort adalah O (n2). Hal ini membuat Sortir Pilihan jauh lebih lambat daripada banyak algoritma pengurutan perbandingan lainnya seperti Merge Sort atau Insertion Sort yang memiliki kompleksitas waktu kasus terburuk (O (nlogn)). Menariknya, O (nlogn) adalah yang terbaik yang dapat dicapai dengan algoritma penyortiran perbandingan apa pun. selection sort ini hanya akan efisien jika digunakan pada data yang berjumlah sedikit. Ketika data bertambah banyak, selection sort menjadi tidak efisien, bahkan ketika datanya sudah hampir terurut. Maka dapat kita simpulkan kelebihan dan kekurangan Selection Sort ini sebagai berikut.

• Kelebihan
• Algoritma ini sangat rapat dan mudah untuk diimplementasikan.
• Operasi pertukarannya hanya dilakukan sekali saja.
• Waktu pengurutan dapat lebih ditekan.
• Mudah menggabungkannya kembali.
• Kompleksitas selection sort relatif lebih kecil.
• Kekurangan
• Membutuhkan method tambahan.
• Sulit untuk membagi masalah.

Mantap jadi itu dia tiga sorting algorithms yang biasanya pertama kali dipelajarin Arek Blodhil! sampai ketemu di blog selanjutnya! semangat!