Sortir Seleksi: Algoritma dijelaskan dengan Python Contoh Kode

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]

Penjelasan Kode

Penjelasan kodenya adalah sebagai berikut

Berikut penjelasan Kode:

Mendefinisikan fungsi bernama choiceSort
Mendapatkan jumlah total elemen dalam daftar. Kita memerlukan ini untuk menentukan jumlah operan yang harus dilakukan saat membandingkan nilai.
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
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.
Menemukan nilai minimum dalam daftar yang tidak diurutkan dan menempatkannya pada posisi yang tepat
Memperbarui nilai minValueIndex ketika kondisi pertukaran benar
Membandingkan nilai nomor indeks minValueIndex dan i untuk melihat apakah keduanya tidak sama
Nilai paling kiri disimpan dalam variabel temporal
Nilai yang lebih rendah dari sisi kanan menempati posisi pertama
Nilai yang disimpan pada nilai temporal disimpan pada posisi yang sebelumnya dipegang oleh nilai minimum
Mengembalikan daftar yang diurutkan sebagai hasil fungsi
Membuat daftar el yang memiliki nomor acak
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 saat daftar yang diberikan sudah diurutkan. Algoritme melakukan jumlah eksekusi minimum yang dinyatakan sebagai [Big-Omega] ?(n²)
Kasus rata-rata – ini terjadi ketika daftar tersebut disusun secara acak. Kompleksitas rata-rata dinyatakan sebagai [Big-theta] ?(n²)

Urutan seleksi memiliki kompleksitas ruang O(1) karena memerlukan satu variabel temporal yang digunakan untuk menukar nilai.

Kapan menggunakan pengurutan pilihan?

Pengurutan pilihan paling baik digunakan ketika Anda ingin:

Anda harus mengurutkan daftar kecil item dalam urutan menaik
Ketika biaya pertukaran 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.

Ringkasan

Selection sort adalah algoritma perbandingan di tempat yang digunakan untuk mengurutkan daftar acak menjadi daftar terurut. Algoritma ini memiliki kompleksitas waktu O(n²)
Daftar ini dibagi menjadi dua bagian, diurutkan dan tidak diurutkan. Nilai minimum diambil dari bagian yang tidak disortir dan ditempatkan ke dalam bagian yang diurutkan.
Hal ini diulangi sampai semua barang telah tersortir.
Menerapkan pseudocode di Python 3 melibatkan penggunaan dua perulangan for dan pernyataan if untuk memeriksa apakah pertukaran diperlukan
Kompleksitas waktu mengukur jumlah langkah yang diperlukan untuk mengurutkan daftar.
Kompleksitas waktu terburuk terjadi ketika daftar tersebut dalam urutan menurun. Kompleksitas waktunya adalah [Big-O] O(n²)
Kompleksitas waktu terbaik terjadi saat daftar sudah dalam urutan menaik. Daftar ini memiliki kompleksitas waktu [Big-Omega] ?(n²)
Kompleksitas waktu kasus rata-rata terjadi saat daftar berada dalam urutan acak. Kompleksitas waktunya adalah [Big-theta] ?(n²)
Pengurutan pilihan paling baik digunakan ketika Anda memiliki daftar kecil item untuk diurutkan, biaya pertukaran nilai tidak menjadi masalah, dan pemeriksaan semua nilai adalah wajib.
Pengurutan pilihan tidak berfungsi dengan baik pada daftar yang besar
Algoritma pengurutan lainnya, seperti quicksort, memiliki kinerja yang lebih baik jika dibandingkan dengan pengurutan pilihan.