Sortir Pilihan: Algoritma dijelaskan dengan Contoh Kode Python

Daftar Isi:

Anonim

Apa itu Sortir Pilihan?

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

Ini dikenal sebagai penyortiran di tempat . Jenis pilihan memiliki kompleksitas waktu O (n 2 ) di mana n adalah jumlah total item dalam daftar. Kompleksitas waktu mengukur jumlah iterasi yang diperlukan untuk mengurutkan daftar. Daftar ini 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 sampai semua nilai dibandingkan dan disortir.

Dalam tutorial Algoritma ini, Anda akan mempelajari:

  • Apa itu Sortir Pilihan?
  • Bagaimana cara kerja sortir seleksi?
  • Definisi masalah
  • Solusi (Algoritma)
  • Representasi Visual
  • Program Sortir Pilihan menggunakan Python 3
  • Penjelasan Kode
  • Kompleksitas Waktu Jenis Pilihan
  • Kapan menggunakan sortir pilihan?
  • Keuntungan dari Seleksi Sort
  • Kekurangan Jenis Seleksi

Bagaimana cara kerja sortir seleksi?

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

Contoh:

  • Misalnya jika indeks nilai minimum adalah 3, maka nilai elemen dengan indeks 3 ditempatkan pada indeks 0 sedangkan nilai yang 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 di sisi kiri, yaitu daftar yang diurutkan.
  • Sisi yang dipartisi sekarang memiliki satu elemen, sedangkan sisi yang tidak dipartisi memiliki (n - 1) elemen di mana n adalah jumlah total elemen dalam daftar. Proses ini diulangi berulang kali hingga semua item telah dibandingkan dan diurutkan berdasarkan nilainya.

Definisi masalah

Daftar elemen yang berada dalam urutan acak perlu diurutkan dalam urutan menaik. Pertimbangkan daftar berikut sebagai contoh.

[21,6,9,33,3]

Daftar di atas harus diurutkan untuk menghasilkan hasil sebagai berikut

[3,6,9,21,33]

Solusi (Algoritma)

Langkah 1) Dapatkan nilai n yang merupakan ukuran total array

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

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

Langkah 4) Ulangi proses (n - 1) kali sampai semua elemen dalam daftar telah diurutkan.

Representasi Visual

Diberikan daftar lima elemen, gambar berikut mengilustrasikan bagaimana algoritme pengurutan seleksi melakukan iterasi melalui nilai-nilai saat menyortirnya.

Gambar berikut menunjukkan daftar yang tidak diurutkan

Langkah 1)

Nilai pertama 21 dibandingkan dengan nilai lainnya untuk memeriksa apakah itu adalah nilai minimum.

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

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 adalah nilai minimum, sehingga posisinya tetap dipertahankan.

Langkah 3)

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

Nilai 9 adalah nilai minimum, sehingga mempertahankan posisinya di partisi yang diurutkan.

Langkah 4)

Nilai 33 dibandingkan dengan nilai lainnya.

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

Langkah 5)

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

Daftar terakhir seperti yang ditunjukkan pada gambar di atas.

Program Sortir Pilihan menggunakan Python 3

Kode berikut menunjukkan implementasi sortir seleksi menggunakan Python 3

def selectionSort( itemsList ):n = len( itemsList )for i in range( n - 1 ):minValueIndex = ifor j in range( i + 1, n ):if itemsList[j] < itemsList[minValueIndex] :minValueIndex = jif minValueIndex != i :temp = itemsList[i]itemsList[i] = itemsList[minValueIndex]itemsList[minValueIndex] = tempreturn itemsListel = [21,6,9,33,3]print(selectionSort(el))

Jalankan kode diatas menghasilkan hasil sebagai berikut

[3, 6, 9, 21, 33]

Penjelasan Kode

Penjelasan kode tersebut adalah sebagai berikut

Berikut adalah penjelasan Kode:

  1. Mendefinisikan fungsi bernama selectionSort
  2. Mendapat jumlah total elemen dalam daftar. Kami membutuhkan ini untuk menentukan jumlah lintasan yang harus dilakukan saat membandingkan nilai.
  3. Lingkaran luar. Menggunakan pengulangan untuk mengulangi nilai-nilai dari daftar. Jumlah iterasi adalah (n - 1). Nilai n adalah 5, jadi (5 - 1) menghasilkan 4. Ini berarti iterasi luar akan dilakukan 4 kali. Di setiap iterasi, nilai variabel i ditetapkan ke variabel minValueIndex
  4. Lingkaran dalam. Menggunakan perulangan untuk membandingkan nilai paling kiri dengan nilai lain di sisi kanan. Namun, nilai untuk j tidak dimulai pada indeks 0. Ini dimulai pada (i + 1). Ini mengecualikan nilai yang telah diurutkan sehingga kami 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 ketika kondisi pertukaran 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 mengambil posisi posisi pertama
  10. Nilai yang disimpan di nilai temporal disimpan di posisi yang sebelumnya dipegang oleh nilai minimum
  11. Mengembalikan daftar yang diurutkan sebagai hasil fungsi
  12. Membuat el daftar yang memiliki nomor acak
  13. Cetak daftar yang diurutkan setelah memanggil fungsi Sort pilihan dengan meneruskan el sebagai parameter.

Kompleksitas Waktu Jenis Pilihan

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

Perulangan luar yang mengambil nilai satu per satu dari daftar dijalankan n kali di mana n adalah jumlah total nilai dalam daftar.

Loop dalam, yang membandingkan nilai dari loop luar dengan nilai-nilai lainnya, juga dieksekusi sebanyak n kali di mana n adalah jumlah total elemen dalam daftar.

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

Jenis seleksi memiliki tiga kategori kompleksitas yaitu;

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

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

Kapan menggunakan sortir pilihan?

Jenis pilihan paling baik digunakan saat Anda ingin:

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

Keuntungan dari Seleksi Sort

Berikut ini adalah keuntungan dari pemilihan sort

  • Ini berkinerja sangat baik pada daftar kecil
  • Ini adalah algoritme di tempat. Tidak membutuhkan banyak ruang untuk penyortiran. Hanya satu spasi ekstra yang diperlukan untuk menyimpan variabel temporal.
  • Ini bekerja dengan baik pada item yang telah disortir.

Kekurangan Jenis Seleksi

Berikut ini adalah kerugian dari pemilihan sort.

  • Ini berkinerja buruk saat mengerjakan daftar besar.
  • Jumlah iterasi yang dilakukan selama pengurutan adalah n-kuadrat, di mana n adalah jumlah total elemen dalam daftar.
  • Algoritme lain, seperti quicksort, memiliki kinerja yang lebih baik dibandingkan dengan jenis pemilihan.

Ringkasan:

  • Sortir pilihan adalah algoritme perbandingan di tempat yang digunakan untuk mengurutkan daftar acak ke dalam daftar berurutan. Ini memiliki kompleksitas waktu O (n 2 )
  • Daftar ini dibagi menjadi dua bagian, diurutkan dan tidak diurutkan. Nilai minimum diambil dari bagian yang tidak diurutkan dan ditempatkan ke bagian yang diurutkan.
  • Hal ini diulangi sampai semua item telah disortir.
  • Menerapkan pseudocode di Python 3 melibatkan penggunaan dua for loop dan jika pernyataan untuk memeriksa apakah pertukaran diperlukan
  • Kompleksitas waktu mengukur jumlah langkah yang diperlukan untuk mengurutkan daftar.
  • Kompleksitas waktu kasus terburuk terjadi ketika daftar dalam urutan menurun. Ini memiliki kompleksitas waktu [Big-O] O (n 2 )
  • Kompleksitas waktu kasus terbaik terjadi ketika daftar sudah dalam urutan menaik. Ini memiliki kompleksitas waktu [Big-Omega] Ω (n 2 )
  • Kompleksitas waktu rata-rata terjadi ketika daftar dalam urutan acak. Ini memiliki kompleksitas waktu [Big-theta] ⊝ (n 2 )
  • Pengurutan pilihan paling baik digunakan saat Anda memiliki daftar kecil item untuk diurutkan, biaya pertukaran nilai tidak masalah, dan pemeriksaan semua nilai adalah wajib.
  • Jenis pilihan tidak bekerja dengan baik pada daftar besar
  • Algoritme pengurutan lainnya, seperti quicksort, memiliki kinerja yang lebih baik jika dibandingkan dengan pengurutan pilihan.