Algoritma Pengurutan Seleksi dengan Python Code Example

Apa itu Pengurutan Seleksi?

PILIHAN SELEKSI adalah algoritma pengurutan perbandingan yang digunakan untuk mengurutkan daftar item secara acak dalam urutan menaik. Perbandingannya tidak memerlukan banyak ruang ekstra. Ini hanya membutuhkan satu ruang memori tambahan untuk variabel temporal.

Ini dikenal sebagai di tempat sorting. Sortiran seleksi memiliki kompleksitas waktu O(n²) di mana n adalah jumlah total item dalam daftar. Kompleksitas waktu mengukur jumlah iterasi yang diperlukan untuk mengurutkan daftar. Daftar dibagi menjadi dua partisi: Daftar pertama berisi item yang diurutkan, sedangkan daftar kedua berisi item yang tidak diurutkan.

Secara default, daftar yang diurutkan kosong, dan daftar yang tidak diurutkan berisi semua elemen. Daftar yang tidak diurutkan kemudian dipindai untuk mendapatkan nilai minimum, yang kemudian ditempatkan dalam daftar yang diurutkan. Proses ini diulangi hingga semua nilai telah dibandingkan dan diurutkan.

Bagaimana cara kerja pengurutan seleksi?

Item pertama dalam partisi yang tidak disortir dibandingkan dengan semua nilai di sisi kanan untuk memeriksa apakah itu adalah nilai minimum. Jika bukan nilai minimum, maka posisinya ditukar dengan nilai minimum.

Example

• Misal indeks nilai minimumnya adalah 3, maka nilai elemen dengan indeks 3 ditempatkan pada indeks 0 sedangkan nilai yang berada pada indeks 0 ditempatkan pada indeks 3. Jika elemen pertama pada partisi yang tidak diurutkan adalah nilai minimum, lalu mengembalikan posisinya.
• Elemen yang telah ditentukan sebagai nilai minimum kemudian dipindahkan ke partisi sebelah kiri, yaitu daftar yang diurutkan.
• Sisi yang dipartisi sekarang memiliki satu elemen, sedangkan sisi yang tidak dipartisi memiliki (n – 1) elemen dengan n adalah jumlah total elemen dalam daftar. Proses ini diulang terus menerus hingga semua item telah dibandingkan dan diurutkan berdasarkan nilainya.

Definisi masalah

Daftar elemen yang disusun secara acak perlu diurutkan dalam urutan menaik. Perhatikan daftar berikut sebagai contoh.

[21,6,9,33,3]

Daftar di atas harus diurutkan untuk menghasilkan hasil berikut

[3,6,9,21,33]

Solusi (Algoritma)

Langkah 1) Dapatkan nilai n yang merupakan ukuran total array

Langkah 2) Partisi daftar menjadi beberapa bagian yang diurutkan dan tidak disortir. Bagian yang diurutkan awalnya kosong sedangkan bagian yang tidak disortir berisi seluruh daftar

Langkah 3) Pilih nilai minimum dari bagian yang tidak dipartisi dan letakkan di bagian yang diurutkan.

Langkah 4) Ulangi proses tersebut (n – 1) kali hingga semua elemen dalam daftar telah terurut.

Representasi Visual

Diberikan daftar yang berisi lima elemen, gambar berikut mengilustrasikan bagaimana algoritma pengurutan pilihan mengulangi nilai-nilai saat mengurutkannya.

Gambar berikut menunjukkan daftar yang tidak diurutkan

Langkah 1)

Nilai pertama (21) dibandingkan dengan nilai lainnya untuk memeriksa apakah nilai tersebut merupakan nilai minimum.

3 adalah nilai minimum, sehingga posisi 21 dan 3 ditukar. Nilai dengan latar belakang hijau mewakili partisi daftar yang diurutkan.

Langkah 2)

Nilai 6 yang merupakan elemen pertama dalam partisi yang tidak disortir dibandingkan dengan nilai lainnya untuk mengetahui apakah ada nilai yang lebih rendah

Nilai 6 merupakan nilai minimum sehingga mempertahankan posisinya.

Langkah 3)

Elemen pertama dari daftar yang tidak disortir dengan nilai 9 dibandingkan dengan nilai lainnya untuk memeriksa apakah itu adalah nilai minimum.

Nilai 9 merupakan nilai minimum sehingga mempertahankan posisinya pada partisi yang diurutkan.

Langkah 4)

Nilai 33 dibandingkan dengan nilai lainnya.

Nilai 21 lebih rendah dari 33, sehingga posisinya ditukar untuk menghasilkan daftar baru di atas.

Langkah 5)

Kami hanya memiliki satu nilai tersisa di daftar yang tidak dipartisi. Oleh karena itu, sudah diurutkan.

Daftar terakhir seperti yang ditunjukkan pada gambar di atas.

Program Sortir Seleksi menggunakan Python 3

Kode berikut menunjukkan implementasi sortir pilihan menggunakan Python 3

def selectionSort( itemsList ):
    n = len( itemsList )
    for i in range( n - 1 ):
        minValueIndex = i

        for j in range( i + 1, n ):
            if itemsList[j] < itemsList[minValueIndex] :
                minValueIndex = j

        if minValueIndex != i :
            temp = itemsList[i]
            itemsList[i] = itemsList[minValueIndex]
            itemsList[minValueIndex] = temp

    return itemsList


el = [21,6,9,33,3]

print(selectionSort(el))

Jalankan kode di atas menghasilkan hasil berikut

[3, 6, 9, 21, 33]

Code Penjelasan

Penjelasan kodenya adalah sebagai berikut

Berikut ini adalah Code penjelasan:

1. Mendefinisikan fungsi bernama choiceSort
2. Mendapatkan jumlah total elemen dalam daftar. Kita memerlukan ini untuk menentukan jumlah operan yang harus dilakukan saat membandingkan nilai.
3. Lingkaran luar. Menggunakan loop untuk mengulangi nilai-nilai daftar. Banyaknya iterasi adalah (n – 1). Nilai n adalah 5, jadi (5 – 1) menghasilkan 4. Artinya iterasi terluar akan dilakukan sebanyak 4 kali. Dalam setiap iterasi, nilai variabel i ditugaskan ke variabel minValueIndex
4. Lingkaran dalam. Menggunakan perulangan untuk membandingkan nilai paling kiri dengan nilai lain di sisi kanan. Namun, nilai j tidak dimulai pada indeks 0. Ia dimulai pada (i + 1). Ini mengecualikan nilai yang sudah diurutkan sehingga kita fokus pada item yang belum diurutkan.
5. Menemukan nilai minimum dalam daftar yang tidak diurutkan dan menempatkannya pada posisi yang tepat
6. Memperbarui nilai minValueIndex saat terjadi pertukaran.ping kondisi tersebut benar
7. Membandingkan nilai nomor indeks minValueIndex dan i untuk melihat apakah keduanya tidak sama
8. Nilai paling kiri disimpan dalam variabel temporal
9. Nilai yang lebih rendah dari sisi kanan menempati posisi pertama
10. Nilai yang disimpan pada nilai temporal disimpan pada posisi yang sebelumnya dipegang oleh nilai minimum
11. Mengembalikan daftar yang diurutkan sebagai hasil fungsi
12. Membuat daftar el yang memiliki nomor acak
13. Cetak daftar yang diurutkan setelah memanggil fungsi Sortir pilihan dengan meneruskan el sebagai parameter.

Kompleksitas Waktu Pemilihan Sortir

Kompleksitas sortir digunakan untuk menyatakan jumlah waktu eksekusi yang diperlukan untuk mengurutkan daftar. Implementasinya memiliki dua loop.

Loop luar yang mengambil nilai satu per satu dari daftar dieksekusi sebanyak n kali dimana n adalah jumlah total nilai dalam daftar.

Perulangan dalam, yang membandingkan nilai dari perulangan luar dengan nilai-nilai lainnya, juga dieksekusi n kali di mana n merupakan jumlah total elemen dalam daftar.

Oleh karena itu, jumlah eksekusinya adalah (n * n), yang juga dapat dinyatakan sebagai O(n²).

Sortiran seleksi memiliki tiga kategori kompleksitas yaitu;

• Kasus terburuk – di sinilah daftar yang disediakan dalam urutan menurun. Algoritme melakukan jumlah eksekusi maksimum yang dinyatakan sebagai [Big-O] O(n²)
• Kasus terbaik – ini terjadi ketika daftar yang diberikan sudah diurutkan. Algoritma melakukan jumlah eksekusi minimum yang dinyatakan sebagai [Big-Omega] Ω(n²)
• Kasus rata-rata – ini terjadi ketika daftar berada dalam urutan acak. Kompleksitas rata-rata dinyatakan sebagai [Big-theta] Θ(n²)

Algoritma selection sort memiliki kompleksitas ruang O(1) karena hanya membutuhkan satu variabel sementara yang digunakan untuk pertukaran.ping nilai-nilai.

Kapan menggunakan pengurutan pilihan?

Pengurutan pilihan paling baik digunakan ketika Anda ingin:

• Anda harus mengurutkan daftar kecil item dalam urutan menaik
• Ketika biaya swapping nilai tidak signifikan
• Ini juga digunakan ketika Anda perlu memastikan bahwa semua nilai dalam daftar telah dicentang.

Keuntungan Sortir Seleksi

Berikut ini adalah keuntungan dari pemilihan sortir:

• Ini berkinerja sangat baik pada daftar kecil
• Ini adalah algoritma yang ada. Tidak memerlukan banyak ruang untuk menyortirnya. Hanya satu ruang tambahan yang diperlukan untuk menampung variabel temporal.
• Ini bekerja dengan baik pada item yang sudah diurutkan.

Kekurangan Pengurutan Seleksi

Berikut ini adalah kerugian dari metode sortir seleksi.

• Performanya buruk saat mengerjakan daftar yang besar.
• Jumlah iterasi yang dilakukan selama pengurutan adalah n-kuadrat, dimana n adalah jumlah total elemen dalam daftar.
• Algoritma lain, seperti quicksort, memiliki kinerja yang lebih baik dibandingkan dengan seleksi sort.

Pertanyaan Umum Demo Slot