Isih Buih, Isih Pilihan, Isih Sisipan | Struktur Data & Algoritma dalam JavaScript

Algoritma pengisihan ialah tulang belakang kepada banyak tugas pengiraan, memainkan peranan penting dalam mengatur data untuk akses dan pemprosesan yang cekap. Sama ada anda seorang pemula yang baru mula meneroka dunia algoritma atau pembangun berpengalaman yang ingin menyegarkan pengetahuan anda, memahami teknik pengisihan asas ini adalah penting. Dalam siaran ini, kami akan meneroka beberapa algoritma pengisihan yang lebih asas - Isih Buih, Isih Pilihan dan Isih Sisipan.

Isih Buih

Isih Buih ialah algoritma pengisihan berasaskan perbandingan yang ringkas. Ia berulang kali melangkah melalui senarai, membandingkan elemen bersebelahan dan menukarnya jika ia berada dalam susunan yang salah. Proses ini berterusan sehingga tiada lagi pertukaran diperlukan, menunjukkan bahawa senarai itu diisih. Walaupun mudah difahami dan dilaksanakan, Bubble Sort tidak cekap untuk set data yang besar, menjadikannya sesuai terutamanya untuk tujuan pendidikan dan set data yang kecil.

Isih Buih mempunyai kerumitan masa O(n²).

// a random array of 20 numbers
const inputArray = [34, 100, 23, 45, 67, 89, 12, 56, 78, 90, 23, 45, 67, 89, 12, 56, 78, 90, 23, 45]

function bubbleSort (input) {
  const n = input.length
  const sortedArray = [...input]

  // loop n times
  for (let i = 0; i < n; i++) {
    // loop through all n-1 pairs
    for (let j = 0; j < n-1; j++) {
      // if a > b, swap; else do nothing
      if (sortedArray[j] > sortedArray[j+1]) {
        const temp = sortedArray[j]
        sortedArray[j] = sortedArray[j+1]
        sortedArray[j+1] = temp
      }
    }
  }

  return sortedArray
}

console.log("Input:", inputArray)
console.log("Ouput:", bubbleSort(inputArray))

Isih Pemilihan

Isih Pilihan ialah algoritma pengisihan berasaskan perbandingan yang mudah. Ia berfungsi dengan membahagikan senarai kepada kawasan yang diisih dan tidak diisih. Ia berulang kali memilih elemen terkecil (atau terbesar) daripada kawasan yang tidak diisih dan menukarnya dengan elemen tidak diisih pertama, secara beransur-ansur mengembangkan wilayah yang diisih. Isih Pemilihan bukanlah yang paling cekap untuk set data yang besar tetapi mudah difahami dan mempunyai kelebihan meminimumkan bilangan swap.

Isih Pilihan mempunyai kerumitan masa O(n²).

// a random array of 20 numbers
const inputArray = [34, 100, 23, 45, 67, 89, 12, 56, 78, 90, 23, 45, 67, 89, 12, 56, 78, 90, 23, 45]

function selectionSort (input) {
  const n = input.length
  const sortedArray = [...input]

  // loop n times
  for (let i = 0; i < n; i++) {
    // start from i'th position
    let lowestNumberIndex = i
    for (let j = i; j < n-1; j++) {
      // identify lowest number
      if (sortedArray[j] < sortedArray[lowestNumberIndex]) {
        lowestNumberIndex = j
      }
    }

    // swap the lowest number with that in i'th position
    const temp = sortedArray[i]
    sortedArray[i] = sortedArray[lowestNumberIndex]
    sortedArray[lowestNumberIndex] = temp
  }

  return sortedArray
}

console.log("Input:", inputArray)
console.log("Ouput:", selectionSort(inputArray))

Isih Sisipan

Isih Sisipan ialah algoritma pengisihan berasaskan perbandingan yang intuitif yang membina senarai isihan terakhir satu elemen pada satu masa. Ia berfungsi dengan mengambil elemen daripada bahagian senarai yang tidak diisih dan memasukkannya ke dalam kedudukan yang betul dalam bahagian yang diisih. Isih Sisipan cekap untuk set data kecil atau data yang hampir diisih dan sering digunakan dalam aplikasi praktikal sebagai alternatif yang lebih mudah kepada algoritma yang lebih kompleks.

Isih Sisipan mempunyai kerumitan masa O(n²).

function insertionSort (input) {
  const n = input.length
  const sortedArray = [...input]

  // loop n times, starting at index 1
  for (let i = 1; i < n; i++) {
    // start at index 1
    const comparedNumber = sortedArray[i]
    let tempIndex = i

    // compare with previous numbers (right to left)
    for (let j = i-1; j >= 0; j--) {
      // if number in current index is larger than compared number, swap
      if (sortedArray[j] > comparedNumber) {
        sortedArray[tempIndex] = sortedArray[j]
        sortedArray[j] = comparedNumber
        tempIndex = j
      } else {
        // OPTIONAL: else exit
        break
      }
    }
  }

  return sortedArray
}

console.log("Input:", inputArray)
console.log("Ouput:", insertionSort(inputArray))

Membungkus

Walaupun algoritma pengisihan asas seperti Isih Buih, Isih Pilihan dan Isih Sisipan mungkin bukan yang paling cekap untuk set data yang besar, ia menawarkan asas yang bagus untuk memahami reka bentuk algoritma. Jika anda mendapati siaran ini membantu, saya ingin mendengar pendapat anda. Letakkan ulasan di bawah, kongsi pandangan anda atau tanya apa-apa soalan yang anda ada - saya akan cuba sedaya upaya untuk menjawabnya.

Selamat mengekod!

Atas ialah kandungan terperinci Isih Buih, Isih Pilihan, Isih Sisipan | Struktur Data & Algoritma dalam JavaScript. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!