Sortir Pilihan di Jawa

1. Perkenalan

Dalam tutorial ini, kita akan mempelajari Selection Sort , melihat implementasinya di Java, dan menganalisis performanya.

2. Gambaran Algoritma

Sortir Pilihan dimulai dengan elemen di posisi pertama dari larik yang tidak diurutkan dan memindai elemen berikutnya untuk menemukan elemen terkecil . Setelah ditemukan, elemen terkecil ditukar dengan elemen di posisi pertama.

Algoritme kemudian beralih ke elemen di posisi ke-2 dan memindai elemen-elemen berikutnya untuk menemukan indeks dari elemen terkecil ke-2. Setelah ditemukan, elemen terkecil kedua ditukar dengan elemen di posisi ke-2.

Proses ini berlanjut hingga kita mencapai elemen ke-1 dari array, yang menempatkan elemen terkecil ke-1 di posisi ke-1. Elemen terakhir secara otomatis berada di tempatnya, dalam iterasi ke-1, sehingga mengurutkan array.

Kami menemukan elemen terbesar dan bukan elemen terkecil untuk mengurutkan array dalam urutan menurun.

Mari kita lihat contoh larik yang tidak diurutkan dan urutkan dalam urutan menaik untuk memahami algoritme secara visual.

2.1. Sebuah contoh

Pertimbangkan array yang tidak disortir berikut ini:

int [] arr = {5, 4, 1, 6, 2}

Iterasi 1

Mempertimbangkan kerja algoritma di atas, kita mulai dengan elemen di posisi pertama - 5 - dan memindai semua elemen berikutnya untuk menemukan elemen terkecil - 1. Kami kemudian menukar elemen terkecil dengan elemen di posisi pertama.

Array yang dimodifikasi sekarang terlihat seperti:

{1, 4, 5, 6, 2}

Total perbandingan yang dibuat: 4

Iterasi 2

Pada iterasi kedua, kami beralih ke elemen ke-2 - 4 - dan memindai elemen berikutnya untuk menemukan elemen terkecil kedua - 2. Kami kemudian menukar elemen terkecil kedua dengan elemen di posisi ke-2.

Array yang dimodifikasi sekarang terlihat seperti:

{1, 2, 5, 6, 4}

Total perbandingan yang dibuat: 3

Melanjutkan serupa, kami memiliki iterasi berikut:

Iterasi 3

{1, 2, 4, 6, 5}

Total perbandingan yang dibuat: 2

Iterasi 4

{1, 2, 4, 5, 6}

Total perbandingan yang dibuat: 1

3. Implementasi

Mari menerapkan Sortir Seleksi menggunakan beberapa for loop:

public static void sortAscending(final int[] arr) { for (int i = 0; i < arr.length - 1; i++) { int minElementIndex = i; for (int j = i + 1; j  arr[j]) { minElementIndex = j; } } if (minElementIndex != i) { int temp = arr[i]; arr[i] = arr[minElementIndex]; arr[minElementIndex] = temp; } } }

Tentu saja, untuk membalikkannya kita bisa melakukan sesuatu yang sangat mirip:

public static void sortDescending(final int[] arr) { for (int i = 0; i < arr.length - 1; i++) { int maxElementIndex = i; for (int j = i + 1; j < arr.length; j++) { if (arr[maxElementIndex] < arr[j]) { maxElementIndex = j; } } if (maxElementIndex != i) { int temp = arr[i]; arr[i] = arr[maxElementIndex]; arr[maxElementIndex] = temp; } } }

Dan dengan sedikit lebih banyak minyak siku, kita bisa menggabungkan ini menggunakan Comparator s.

4. Ikhtisar Kinerja

4.1. Waktu

Dalam contoh yang kita lihat sebelumnya, memilih elemen terkecil membutuhkan total (n-1) perbandingan diikuti dengan menukar ke posisi pertama. Demikian pula, memilih elemen terkecil berikutnya memerlukan perbandingan total (n-2) yang diikuti dengan penukaran di posisi ke-2, dan seterusnya.

Jadi, mulai dari indeks 0, kami melakukan n-1, n-2, n-3, n-4…. 1 perbandingan. Elemen terakhir secara otomatis berada di tempatnya karena iterasi dan pertukaran sebelumnya.

Secara matematis, jumlah dari n-1 bilangan asli akan memberi tahu kita berapa banyak perbandingan yang kita perlukan untuk mengurutkan array berukuran n menggunakan Selection Sort.

Rumus penjumlahan n bilangan asli adalah n (n + 1) / 2 .

Dalam kasus kita, kita membutuhkan jumlah n-1 bilangan asli. Oleh karena itu, kami mengganti n dengan n-1 pada rumus di atas untuk mendapatkan:

(n-1) (n-1 + 1) / 2 = (n-1) n / 2 = (n ^ 2-n) / 2

Ketika n ^ 2 tumbuh secara mencolok seiring n tumbuh, kami menganggap kekuatan n yang lebih tinggi sebagai tolok ukur kinerja, membuat algoritme ini memiliki kompleksitas waktu O (n ^ 2).

4.2. Ruang

Dalam hal kompleksitas ruang tambahan, Sortir Pilihan memerlukan satu variabel tambahan untuk menampung nilai sementara untuk bertukar. Oleh karena itu, kompleksitas ruang Selection Sort adalah O (1) .

5. Kesimpulan

Sortir Seleksi adalah algoritme pengurutan yang sangat sederhana untuk dipahami dan diterapkan. Sayangnya, kompleksitas waktu kuadrat membuatnya menjadi teknik penyortiran yang mahal . Selain itu, karena algoritme harus memindai setiap elemen, kompleksitas kasus terbaik, kasus rata-rata, dan kasus terburuk adalah sama .

Teknik penyortiran lain seperti Insertion Sort dan Shell Sort juga memiliki kompleksitas waktu kasus terburuk kuadrat, tetapi mereka bekerja lebih baik dalam kasus terbaik dan rata-rata.

Lihat kode lengkap untuk Sortir Seleksi di GitHub.