Apakah Pilihan Susun?
SELECTION SORT adalah algoritma penyortiran perbandingan yang digunakan untuk menyusun senarai item secara rawak dalam urutan menaik. Perbandingannya tidak memerlukan banyak ruang tambahan. Ia hanya memerlukan satu ruang memori tambahan untuk pemboleh ubah temporal.
Ini dikenali sebagai penyortiran di tempat . Jenis pemilihan mempunyai kerumitan masa O (n 2 ) di mana n adalah jumlah item dalam senarai. Kerumitan masa mengukur bilangan lelaran yang diperlukan untuk menyusun senarai. Senarai ini terbahagi kepada dua bahagian: Senarai pertama mengandungi item yang disusun, sementara senarai kedua mengandungi item yang tidak disusun.
Secara lalai, senarai yang disusun kosong, dan senarai yang tidak disusun mengandungi semua elemen. Senarai yang tidak disusun kemudian diimbas untuk nilai minimum, yang kemudian diletakkan dalam senarai yang disusun. Proses ini diulang sehingga semua nilai telah dibandingkan dan disusun.
Dalam tutorial Algoritma ini, anda akan belajar:
- Apakah Pilihan Susun?
- Bagaimana kaedah pemilihan berfungsi?
- Definisi masalah
- Penyelesaian (Algoritma)
- Perwakilan Visual
- Program Urut Pemilihan menggunakan Python 3
- Penjelasan Kod
- Kerumitan Masa Jenis Pilihan
- Bilakah menggunakan jenis pilihan?
- Kelebihan Urutan Pemilihan
- Kelemahan Urutan Pemilihan
Bagaimana kaedah pemilihan berfungsi?
Item pertama dalam partisi yang tidak disusun dibandingkan dengan semua nilai di sebelah kanan untuk memeriksa sama ada nilai minimum. Sekiranya bukan nilai minimum, maka kedudukannya ditukar dengan nilai minimum.
Contoh:
- Sebagai contoh, jika indeks nilai minimum adalah 3, maka nilai elemen dengan indeks 3 diletakkan pada indeks 0 sementara nilai yang berada pada indeks 0 diletakkan pada indeks 3. Sekiranya elemen pertama dalam partisi yang tidak disusun adalah nilai minimum, maka ia mengembalikan kedudukannya.
- Elemen yang telah ditentukan sebagai nilai minimum kemudian dipindahkan ke partisi di sebelah kiri, yang merupakan senarai yang disusun.
- Bahagian berpartisi kini mempunyai satu elemen, sementara sisi yang tidak dipartisi mempunyai elemen (n - 1) di mana n adalah jumlah keseluruhan elemen dalam senarai. Proses ini diulang berulang kali sehingga semua item telah dibandingkan dan disusun berdasarkan nilainya.
Definisi masalah
Senarai elemen yang berada dalam urutan rawak perlu disusun mengikut urutan menaik. Pertimbangkan senarai berikut sebagai contoh.
[21,6,9,33,3]
Senarai di atas harus disusun untuk menghasilkan hasil berikut
[3,6,9,21,33]
Penyelesaian (Algoritma)
Langkah 1) Dapatkan nilai n yang merupakan ukuran keseluruhan array
Langkah 2) Bahagikan senarai ke bahagian yang disusun dan tidak disusun. Bahagian yang disusun pada mulanya kosong sementara bahagian yang tidak disusun mengandungi keseluruhan senarai
Langkah 3) Pilih nilai minimum dari bahagian yang tidak dibahagi dan masukkan ke bahagian yang disusun.
Langkah 4) Ulangi proses (n - 1) kali sehingga semua elemen dalam senarai telah disusun.
Perwakilan Visual
Memandangkan senarai lima elemen, gambar berikut menggambarkan bagaimana algoritma urutan pemilihan berulang melalui nilai ketika menyusunnya.
Gambar berikut menunjukkan senarai yang tidak disusun
Langkah 1)
Nilai pertama 21 dibandingkan dengan nilai selebihnya untuk memeriksa sama ada nilai minimum.
3 adalah nilai minimum, jadi kedudukan 21 dan 3 ditukar. Nilai dengan latar hijau mewakili partisi senarai yang disusun.
Langkah 2)
Nilai 6 yang merupakan elemen pertama dalam partisi yang tidak disusun dibandingkan dengan nilai-nilai selebihnya untuk mengetahui sama ada terdapat nilai yang lebih rendah
Nilai 6 adalah nilai minimum, jadi ia tetap mempertahankan kedudukannya.
Langkah 3)
Elemen pertama senarai yang tidak disusun dengan nilai 9 dibandingkan dengan nilai selebihnya untuk memeriksa sama ada nilai minimum.
Nilai 9 adalah nilai minimum, jadi ia mengekalkan kedudukannya dalam partisi yang disusun.
Langkah 4)
Nilai 33 dibandingkan dengan nilai selebihnya.
Nilai 21 lebih rendah daripada 33, jadi kedudukan ditukar untuk menghasilkan senarai baru di atas.
Langkah 5)
Kami hanya tinggal satu nilai dalam senarai yang tidak dibahagi. Oleh itu, ia sudah disusun.
Senarai akhir adalah seperti yang ditunjukkan dalam gambar di atas.
Program Urut Pemilihan menggunakan Python 3
Kod berikut menunjukkan pelaksanaan jenis pemilihan 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 kod di atas menghasilkan hasil berikut
[3, 6, 9, 21, 33]
Penjelasan Kod
Penjelasan untuk kodnya adalah seperti berikut
Berikut adalah penjelasan Kod:
- Mentakrifkan fungsi yang bernama selectionSort
- Mendapat jumlah elemen dalam senarai. Kami memerlukan ini untuk menentukan jumlah hantaran yang harus dibuat ketika membandingkan nilai.
- Gelung luar. Menggunakan gelung untuk mengulangi nilai-nilai senarai. Bilangan lelaran adalah (n - 1). Nilai n adalah 5, jadi (5 - 1) memberi kita 4. Ini bermaksud lelaran luar akan dilakukan 4 kali. Dalam setiap lelaran, nilai pemboleh ubah i diberikan kepada pemboleh ubah minValueIndex
- Gelung dalaman. Menggunakan gelung untuk membandingkan nilai paling kiri dengan nilai lain di sebelah kanan. Walau bagaimanapun, nilai untuk j tidak bermula pada indeks 0. Ia bermula pada (i + 1). Ini tidak termasuk nilai yang telah disusun sehingga kita fokus pada item yang belum disusun.
- Mencari nilai minimum dalam senarai yang tidak disusun dan meletakkannya pada kedudukannya yang betul
- Mengemas kini nilai minValueIndex apabila keadaan pertukaran benar
- Membandingkan nilai nombor indeks minValueIndex dan i untuk melihat sama ada ia tidak sama
- Nilai paling kiri disimpan dalam pemboleh ubah temporal
- Nilai yang lebih rendah dari sebelah kanan mengambil kedudukan pertama
- Nilai yang disimpan dalam nilai temporal disimpan dalam kedudukan yang sebelumnya dipegang oleh nilai minimum
- Mengembalikan senarai yang disusun sebagai hasil fungsi
- Membuat senarai el yang mempunyai nombor rawak
- Cetak senarai yang diurutkan setelah memanggil pilihan Fungsi urutkan yang masuk sebagai parameter.
Kerumitan Masa Jenis Pilihan
Kerumitan urutan digunakan untuk menyatakan jumlah masa pelaksanaan yang diperlukan untuk menyusun senarai. Pelaksanaannya mempunyai dua gelung.
Gelung luar yang memilih nilai satu demi satu dari senarai dilaksanakan n kali di mana n adalah jumlah nilai dalam senarai.
Gelung dalaman, yang membandingkan nilai dari gelung luar dengan nilai selebihnya, juga dilaksanakan n kali di mana n adalah jumlah elemen dalam senarai.
Oleh itu, jumlah pelaksanaan adalah (n * n), yang juga boleh dinyatakan sebagai O (n 2 ).
Jenis pemilihan mempunyai tiga kategori kerumitan iaitu;
- Kes terburuk - di sinilah senarai yang disediakan berada dalam urutan menurun. Algoritma melakukan bilangan pelaksanaan maksimum yang dinyatakan sebagai [Big-O] O (n 2 )
- Kes terbaik - ini berlaku apabila senarai yang disediakan sudah disusun. Algoritma melakukan bilangan pelaksanaan minimum yang dinyatakan sebagai [Big-Omega] Ω (n 2 )
- Kes rata - ini berlaku apabila senarai berada dalam urutan rawak. Kerumitan purata dinyatakan sebagai [Big-theta] ⊝ (n 2 )
Jenis pemilihan mempunyai kerumitan ruang O (1) kerana memerlukan satu pemboleh ubah temporal yang digunakan untuk menukar nilai.
Bilakah menggunakan jenis pilihan?
Jenis pilihan paling sesuai digunakan apabila anda ingin:
- Anda harus menyusun senarai item kecil mengikut urutan menaik
- Apabila kos pertukaran nilai tidak signifikan
- Ini juga digunakan ketika anda perlu memastikan bahawa semua nilai dalam daftar telah diperiksa.
Kelebihan Urutan Pemilihan
Berikut adalah kelebihan jenis pemilihan
- Ia berfungsi dengan baik dalam senarai kecil
- Ini adalah algoritma di tempat. Ia tidak memerlukan banyak ruang untuk disusun. Hanya diperlukan satu ruang tambahan untuk menahan pemboleh ubah temporal.
- Ia berfungsi dengan baik pada item yang telah disusun.
Kelemahan Urutan Pemilihan
Berikut adalah kelemahan jenis pemilihan.
- Ia berprestasi buruk ketika mengerjakan senarai besar.
- Bilangan lelaran yang dibuat semasa penyortiran adalah n-kuadrat, di mana n adalah jumlah elemen dalam senarai.
- Algoritma lain, seperti quicksort, mempunyai prestasi yang lebih baik berbanding jenis pemilihan.
Ringkasan:
- Pemilihan pemilihan adalah algoritma perbandingan di tempat yang digunakan untuk menyusun senarai rawak ke dalam senarai yang disusun. Ia mempunyai kerumitan masa O (n 2 )
- Senarai ini dibahagikan kepada dua bahagian, disusun dan tidak disusun. Nilai minimum dipilih dari bahagian yang tidak disusun dan dimasukkan ke dalam bahagian yang disusun.
- Perkara ini diulang sehingga semua item telah disusun.
- Melaksanakan pseudocode dalam Python 3 melibatkan penggunaan dua untuk gelung dan jika pernyataan untuk memeriksa apakah pertukaran itu perlu
- Kerumitan masa mengukur bilangan langkah yang diperlukan untuk menyusun senarai.
- Kerumitan masa terburuk berlaku apabila senarai berada dalam urutan menurun. Ia mempunyai kerumitan masa [Big-O] O (n 2 )
- Kerumitan masa kes terbaik berlaku apabila senarai sudah berada dalam urutan menaik. Ia mempunyai kerumitan masa [Big-Omega] Ω (n 2 )
- Kerumitan masa kes biasa berlaku apabila senarai berada dalam urutan rawak. Ia mempunyai kerumitan masa [Big-theta] ⊝ (n 2 )
- Jenis pemilihan paling baik digunakan apabila anda mempunyai senarai item yang kecil untuk disusun, kos pertukaran nilai tidak menjadi masalah, dan pemeriksaan semua nilai adalah wajib.
- Jenis pemilihan tidak berfungsi dengan baik dalam senarai besar
- Algoritma penyortiran lain, seperti quicksort, mempunyai prestasi yang lebih baik jika dibandingkan dengan jenis pemilihan.