Disyorkan, 2019

Pilihan Editor

Perbezaan antara Jenis Penyisipan dan Pemilihan Susun

Pemilihan semakan dan pemilihan jenis adalah teknik yang digunakan untuk menyusun data. Susunan pemilihan jenis dan pilihan utama boleh dibezakan dengan kaedah yang mereka gunakan untuk menyusun data. Jenis pemasukan memasukkan nilai-nilai dalam fail yang diasingkan untuk menyusun satu set nilai. Sebaliknya, pilihan pemilihan mendapati nombor minimum dari senarai dan menyusunnya dalam beberapa pesanan.

Pengisihan adalah operasi asas di mana unsur-unsur array disusun dalam beberapa susunan tertentu untuk meningkatkan pencariannya. Dalam kata yang mudah, data diisih supaya mudah dicari.

Carta Perbandingan

Asas untuk perbandinganIsih masukkanSusun Pilihan
Asas
Data disusun dengan memasukkan data ke dalam fail yang disusun yang sedia ada.Data disusun dengan memilih dan meletakkan unsur-unsur berturut-turut di lokasi disusun.
Alam
StabilTidak stabil
Proses yang harus diikuti
Unsur-unsur yang diketahui terlebih dahulu semasa lokasi untuk menempatkannya dicari.Lokasi sebelum ini diketahui semasa elemen dicari.
Data segera
Jenis pemasukan adalah teknik penyortiran langsung yang boleh menangani data serta-merta.Ia tidak boleh menangani data serta-merta, ia perlu hadir pada mulanya.
Kerumitan kes terbaikO (n)O (n 2 )

Definisi Penyisipan Semula

Susun pemasukan berfungsi dengan memasukkan set nilai dalam fail yang disusun yang sedia ada. Ia membina pelbagai disusun dengan memasukkan elemen tunggal pada satu masa. Proses ini berterusan sehingga pelbagai keseluruhan disusun dalam beberapa pesanan. Konsep utama di sebalik jenis sisipan adalah untuk memasukkan setiap item ke tempat yang sesuai dalam senarai akhir. Kaedah penyisipan menyusun jumlah ingatan yang berkesan.

Bekerja dengan jenis Insertion

  • Ia menggunakan dua set array yang mana satu menyimpan data disusun dan lain-lain pada data yang tidak disortir.
  • Algoritma penyortiran berfungsi sehingga terdapat elemen dalam set unsorted.
  • Mari kita anggap ada unsur nombor 'n' dalam array. Pada mulanya, elemen dengan indeks 0 (LB = 0) wujud dalam set yang disusun. Elemen-elemen yang tersisa berada dalam senarai partisyen yang tidak disokong.
  • Unsur pertama bahagian unsorted mempunyai indeks array 1 (Jika LB = 0).
  • Selepas setiap lelaran, ia memilih elemen pertama partisyen unsorted dan memasukkannya ke tempat yang sepatutnya dalam set yang disusun.

Kelebihan jenis Penyisipan

  • Mudah dilaksanakan dan sangat cekap apabila digunakan dengan set data kecil.
  • Keperluan ruang ingatan tambahan untuk memasukkan sisipan adalah kurang (iaitu, O (1)).
  • Ia dianggap teknik penyortiran langsung kerana senarai itu boleh diisih sebagai elemen baru yang diterima.
  • Ia lebih cepat daripada algoritma sorting lain.

Contoh:

Takrifan Sort Seleksi

Susunan Pemilihan melakukan sort dengan mencari nombor nilai minima dan meletakkannya ke posisi pertama atau terakhir mengikut susunan (naik atau menurun). Proses mencari kunci minimum dan meletakkannya dalam kedudukan yang betul diteruskan sehingga semua elemen diletakkan pada kedudukan yang betul.

Kerja Sort Selection

  • Anggapkan array ARR dengan elemen N dalam ingatan.
  • Dalam pas pertama, kekunci terkecil dicari dengan kedudukannya maka ARR [POS] ditukar dengan ARR [0]. Oleh itu, ARR [0] diisih.
  • Dalam pas kedua, sekali lagi kedudukan nilai terkecil ditentukan dalam subarray elemen N-1. Pertukaran ARR [POS] dengan ARR [1].
  • Dalam lulus N-1, proses yang sama dilakukan untuk menyusun nombor N unsur.

Contoh:

Perbezaan Utama Antara Susun Semakan dan Seleksi Pemilihan

  1. Jenis penyisipan biasanya melakukan operasi memasukkan. Sebaliknya, jenis pemilihan melaksanakan pemilihan dan kedudukan unsur-unsur yang diperlukan.
  2. Susun pemasukan dikatakan stabil sementara sort pemilihan bukan algoritma yang stabil.
  3. Dalam algoritma jenis penyisipan unsur-unsur telah diketahui sebelum ini. Sebaliknya, jenis pilihan mengandungi lokasi sebelum ini.
  4. Isi penyisipan adalah teknik penyortiran langsung di mana unsur-unsur yang tiba segera disusun dalam senarai manakala jenis pemilihan tidak dapat berfungsi dengan baik dengan data segera.
  5. Jenis pemasukan mempunyai masa berjalan O (n) dalam kes terbaik. Sebaliknya, kerumitan masa yang paling kompleks untuk pemilihan jenis adalah O (n2).

Jenis kerumitan semakan

Kerumitan kes terbaik dalam memasukkan sisipan adalah O (n) kali, iaitu ketika array disusun sebelumnya. Dengan cara yang sama, apabila tatasusunan disusun dalam urutan terbalik, elemen pertama bagi unsorted array akan dibandingkan dengan setiap elemen dalam set yang disusun. Oleh itu, dalam kes yang paling teruk, masa menjalankan jenis Penyisipan adalah kuadrat, iaitu, O (n2) . Dalam kes purata juga ia perlu membuat perbandingan minimum (k-1) / 2. Oleh itu, kes purata juga mempunyai masa kuadratik O (n2).

Kerumitan Sort Selection

Sebagai kerja pemilihan, semakan tidak bergantung kepada susunan asal unsur-unsur dalam array, jadi tidak ada banyak perbezaan antara kes terbaik dan kes kerumitan paling teruk pemilihan jenis.

Jenis pemilihan memilih elemen nilai minimum, dalam proses pemilihan semua bilangan elemen 'n' diimbas; oleh itu perbandingan n-1 dibuat dalam pas pertama. Kemudian, unsur-unsur dipertukarkan. Begitu juga pada lulus kedua juga untuk mencari unsur terkecil kedua kita memerlukan pengimbasan rehat n-1 elemen dan prosesnya diteruskan sehingga keseluruhan array disusun.

Oleh itu, kerumitan masa pemilihan jenis pemilihan adalah O (n2) .
= (n-1) + (n-2) + ......... .. + 2 + 1
= n (n-1) / 2 = O (n2)

Kesimpulannya

Di antara kedua-dua algoritma sorting itu, jenis penyisipan adalah pantas, cekap, stabil manakala pemilihan jenis hanya berfungsi dengan cekap apabila set kecil elemen terlibat atau senarai sebahagiannya sebelum disusun. Bilangan perbandingan yang dibuat oleh jenis pemilihan adalah lebih besar daripada pergerakan yang dilakukan manakala dalam sisipan menyusun bilangan kali elemen yang dipindahkan atau bertukar adalah lebih besar daripada perbandingan yang dibuat.

Top