Pelayaran melalui Algoritma menggunakan Javascript - Isih Sisipan

Apakah Isihan Sisipan?

Isih Sisipan ialah satu lagi algoritma pengisihan asas dalam sains komputer. Ia membina tatasusunan diisih terakhir satu item pada satu masa. Ia sama seperti mengisih tangan bermain kad - anda mengambil satu demi satu kad dan memasukkan setiap kad ke dalam kedudukan yang betul antara kad yang telah anda isih.

Cara Isih Sisipan Berfungsi

Isih Sisipan berulang melalui tatasusunan, mengembangkan bahagian yang diisih dengan setiap lelaran. Untuk setiap elemen, ia membandingkannya dengan elemen yang telah diisih, menggerakkannya ke atas sehingga ia menemui kedudukan yang betul untuk memasukkan elemen semasa.

Berikut ialah pecahan langkah demi langkah:

1. Mulakan dengan elemen kedua (indeks 1) sebagai elemen "semasa".
2. Bandingkan elemen semasa dengan elemen sebelumnya.
3. Jika elemen semasa lebih kecil, bandingkan dengan elemen sebelumnya. Gerakkan elemen yang lebih besar ke atas untuk memberi ruang kepada elemen yang ditukar.
4. Ulang langkah 2-3 sehingga keseluruhan tatasusunan diisih.

Visualisasi Isih Sisipan:

Gif yang dirakam daripada https://visualgo.net/en/sorting

Melaksanakan Isih Sisipan dalam JavaScript

Mari kita lihat pelaksanaan Insertion Sort dalam JavaScript, dengan ulasan terperinci menerangkan setiap bahagian:

function insertionSort(arr) {
  // Start from the second element (index 1)
  // We assume the first element is already sorted
  for (let i = 1; i < arr.length; i++) {
    // Store the current element we're trying to insert into the sorted portion
    let currentElement = arr[i];
    // Define the starting index of lookup (this is the last index of sorted portion of array)
    let j = j - 1;
    // Move elements of arr[0..i-1] that are greater than currentElement
    // to one position ahead of their current position
    while (j >= 0 && arr[j] > currentElement) {
      // Shift element to the right
      arr[j + 1] = arr[j];
      j--;
    }
    // We've found the correct position for currentElement (at j + 1), insert it:
    arr[j + 1] = currentElement;
  }

  // The array is now sorted in-place:
  return arr;
}

Perkara Utama:

1. Proses Dua Arah: Isih Sisipan beroperasi melalui gelung luar yang bergerak ke hadapan dan gelung dalam yang memandang ke belakang, mewujudkan pergerakan ke belakang dan ke hadapan yang membentuk teras algoritma.
2. Imbasan Hadapan (Gelung Luar):

   for (let i = 1; i < arr.length; i++)

Bergerak ke hadapan melalui tatasusunan, memilih satu elemen yang tidak diisih (currentElement = arr[i]) pada satu masa.

1. Sisipan Ke Belakang (Gelung Dalam):

   while (j >= 0 && arr[j] > currentElement)

Melihat ke belakang ke bahagian yang diisih, mengalihkan elemen yang lebih besar ke kanan (arr[j 1] = arr[j]) untuk memberi ruang kepada elemen semasa.

1. Sisipan Elemen:

   arr[j + 1] = currentElement;

Memasukkan elemen semasa ke kedudukannya yang betul, mengembangkan bahagian yang diisih.

1. Isih Di Tempat dan Stabil: Mengubah suai tatasusunan asal secara langsung, mengekalkan susunan relatif unsur yang sama.

Isih Sisipan membina tatasusunan diisih terakhir satu item pada satu masa, meniru cara anda mengisih tangan kad. Ia berulang kali memilih kad (elemen) daripada bahagian yang tidak diisih dan memasukkannya ke dalam kedudukan yang betul di antara kad yang diisih, mengalihkan kad yang lebih besar mengikut keperluan. Proses intuitif ini menjadikan Isih Sisipan cekap untuk set data kecil atau hampir diisih.

Adakah Isih Sisipan Stabil?

Ya, Isih Sisipan ialah algoritma pengisihan yang stabil. Kestabilan dalam algoritma pengisihan bermakna susunan relatif unsur yang sama dikekalkan selepas pengisihan. Isih Sisipan mencapai ini secara semula jadi kerana kaedah pengendaliannya:

1. Memelihara Tertib: Apabila memasukkan elemen ke dalam bahagian yang diisih, Isih Sisipan hanya mengalihkan elemen yang lebih besar daripada elemen semasa. Ini bermakna jika terdapat berbilang elemen dengan nilai yang sama, susunan relatifnya akan dikekalkan.
2. Tiada Pertukaran Tidak Perlu: Tidak seperti beberapa algoritma pengisihan lain yang mungkin menukar elemen yang sama, Isih Sisipan hanya menggerakkan elemen apabila perlu. Ciri ini memastikan elemen yang sama kekal dalam kedudukan relatif asalnya.
3. Pemprosesan Kiri-ke-Kanan: Dengan memproses tatasusunan dari kiri ke kanan dan memasukkan setiap elemen ke kedudukannya yang betul antara elemen yang telah diisih, Isih Sisipan secara semula jadi mengekalkan susunan asal unsur yang sama.

Kestabilan Isih Sisipan boleh menjadi sangat berguna apabila mengisih struktur data kompleks yang mengekalkan susunan asal unsur yang sama adalah penting. Contohnya, apabila mengisih senarai pelajar dahulu mengikut gred dan kemudian mengikut nama, isihan yang stabil akan memastikan pelajar dengan gred yang sama kekal dalam susunan abjad mengikut nama.

Kestabilan ini ialah sifat sedia ada bagi algoritma Isih Sisipan asas dan tidak memerlukan sebarang pengubahsuaian atau overhed tambahan untuk dicapai, menjadikannya kaedah pengisihan yang stabil secara semula jadi.

Analisis Kerumitan Masa dan Ruang

Ciri prestasi Isih Sisipan adalah seperti berikut:

• Kerumitan Masa:

  • Kes Terbaik: O(n) - apabila tatasusunan sudah diisih
  • Kes Purata: O(n^2)
  • Kes Terburuk: O(n^2) - apabila tatasusunan disusun terbalik

• Kerumitan Ruang: O(1) - Isih Sisipan ialah algoritma pengisihan di tempat

Tidak seperti Isih Pilihan, Isih Sisipan boleh berprestasi baik pada tatasusunan yang hampir diisih, mencapai kerumitan masa yang hampir dengan linear dalam kes sedemikian.

Kelebihan dan Kelemahan Isih Sisipan

Kelebihan:

• Mudah untuk dilaksanakan dan difahami
• Cekap untuk set data kecil hingga sederhana
• Suai suai - berfungsi dengan baik pada tatasusunan yang hampir diisih
• Stabil - mengekalkan susunan relatif elemen yang sama
• Isih di tempat (ruang O(1))
• Sesuai untuk senario pengisihan dalam talian

Kelemahan:

• Tidak cekap untuk set data yang besar (O(n^2) dalam kes purata dan paling teruk)
• Prestasi merosot dengan cepat apabila saiz input meningkat

Bila hendak menggunakan Isihan Sisipan

• Set data bersaiz kecil hingga sederhana (biasanya sehingga beberapa ratus elemen)
• Data yang hampir diisih
• Senario pengisihan dalam talian di mana unsur diterima dan diisih secara berperingkat
• Sebagai subrutin dalam algoritma yang lebih kompleks (cth., Quicksort untuk partition kecil)

Aplikasi Praktikal dan Kes Penggunaan

1. Pelaksanaan perpustakaan standard: Selalunya digunakan untuk tatasusunan kecil atau sebagai sebahagian daripada algoritma pengisihan hibrid
2. Operasi pangkalan data: Mengisih set kecil rekod
3. Sistem terbenam: Sesuai untuk sistem dengan sumber terhad kerana kesederhanaan dan overhed memori yang rendah
4. Pemprosesan data masa nyata: Mengekalkan susunan yang diisih semasa data diterima

Kesimpulan

Isih Sisipan, walaupun terhad untuk set data yang besar, menawarkan kelebihan berharga dalam senario tertentu. Sifat intuitifnya, menyerupai cara kami boleh mengisih kad menggunakan tangan, menjadikannya alat pendidikan yang sangat baik untuk memahami algoritma pengisihan.

Pengambilan utama:

• Kerumitan masa kes terbaik O(n) untuk data hampir diisih
• Algoritma pengisihan stabil, di tempat dan penyesuaian
• Cekap untuk set data kecil dan pengisihan dalam talian
• Selalunya dimasukkan ke dalam strategi pengisihan hibrid

Walaupun tidak sesuai untuk tugas pengisihan berskala besar, prinsip Isih Sisipan sering digunakan dalam kaedah yang lebih canggih. Kesederhanaan dan kecekapannya dalam senario tertentu menjadikannya tambahan yang berharga kepada kit alat algoritma pengaturcara.

Pilihan algoritma pengisihan akhirnya bergantung pada kes penggunaan khusus anda, ciri data dan kekangan sistem. Memahami Isih Sisipan memberikan cerapan tentang pertukaran reka bentuk algoritma dan meletakkan asas untuk meneroka teknik pengisihan yang lebih maju.

Atas ialah kandungan terperinci Pelayaran melalui Algoritma menggunakan Javascript - Isih Sisipan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!