Memahami algoritma isihan gabungan: Panduan pemula untuk menguasai algoritma isihan

Dalam artikel kami sebelum ini, kami telah mempelajari tentang beberapa algoritma pengisihan seperti Isih Buih, Isih Pemilihan serta Isih Sisipan. Kami telah mengetahui bahawa walaupun algoritma pengisihan ini sangat mudah untuk dilaksanakan, ia tidak cekap untuk set data yang besar, yang bermaksud kami memerlukan algoritma yang lebih cekap untuk mengendalikan pengisihan set data yang besar, oleh itu pengisihan gabungan. Dalam siri ini, kita akan meneliti cara pengisihan gabungan berfungsi dan cara ia boleh dilaksanakan dalam JavaScript. Anda bersedia?

Jadual Kandungan

1. Apakah itu Algoritma Isih Gabung?
2. Cara Algoritma Isih Gabungan Berfungsi
   • Kerumitan Masa
   • Kerumitan Angkasa
3. Pelaksanaan dalam JavaScript
4. Kesimpulan

Apakah Algoritma Isih Gabung?

Algoritma Isih Gabung ialah algoritma pengisihan yang sangat baik yang mengikut prinsip bahagi-dan-takluk. Tidak seperti algoritma yang lebih mudah seperti Isih Pemilihan dan Isih Buih yang membuat beberapa hantaran melalui tatasusunan yang membandingkan elemen bersebelahan, Isih Gabungan mengambil pendekatan yang lebih strategik:

1. Bahagikan: pertama sekali, cantumkan isihan bahagikan tatasusunan kepada dua bahagian
2. Menakluk: kedua, ia menyusun setiap separuh secara rekursif
3. Gabungkan: akhir sekali, ia menggabungkan bahagian yang diisih kembali bersama

Pendekatan ini secara konsisten mengatasi prestasi algoritma O(n²) yang lebih mudah seperti Isih Pemilihan dan Isih Buih apabila berurusan dengan set data yang lebih besar.

Cara Algoritma Isih Gabungan Berfungsi

Kami telah melihat bahawa isihan gabungan berfungsi dengan menggunakan pendekatan divide-and-conquer yang popular. Di bawah ialah gambaran visual tentang cara ia berfungsi.

Sekarang kita telah melihat keajaiban, mari kita lihat cara algoritma isihan gabungan berfungsi dengan mengisih tatasusunan ini secara manual: [38, 27, 43, 3, 9, 82, 10] menggunakan pendekatan yang disebutkan di atas.

Langkah 1: Pembahagian

Langkah pertama dalam isihan cantuman ialah membahagikan tatasusunan kepada subarray, dan kemudian membahagikan setiap subarray kepada subarray dan subarray kepada subarray sehingga kita hanya mempunyai satu item dalam semua subarray.

Langkah 2: Menggabungkan Kembali (Menakluki)

Langkah kedua ialah mula menyusun subarray tersebut dari bawah ke atas.

Kerumitan Masa

Isih Gabung mencapai kerumitan masa O(n log n) dalam semua kes (terbaik, purata dan paling teruk), menjadikannya lebih cekap daripada algoritma O(n²) untuk set data yang lebih besar.

Ini sebabnya:

• Membahagi: Tatasusunan dibahagikan log n kali (setiap bahagian memotong saiz separuh)
• Penggabungan: Setiap peringkat penggabungan memerlukan n operasi
• Jumlah: n operasi × ​​log n aras = O(n log n)

Bandingkan ini dengan:

• Isih Buih: O(n²)
• Isih Pilihan: O(n²)
• Isih Gabung: O(n log n)

Untuk susunan 1,000 elemen:

• O(n²) ≈ 1,000,000 operasi
• O(n log n) ≈ 10,000 operasi

Kerumitan Ruang

Isih Gabungan memerlukan ruang tambahan O(n) untuk menyimpan tatasusunan sementara semasa penggabungan. Walaupun ini lebih daripada ruang O(1) yang diperlukan oleh Isih Buih atau Isih Pemilihan, kecekapan masa biasanya menjadikan pertukaran ini berbaloi dalam amalan.

Pelaksanaan dalam JavaScript

// The Merge Helper Function
function merge(left, right) {
  const result = [];
  let leftIndex = 0;
  let rightIndex = 0;

  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] <= right[rightIndex]) {
      result.push(left[leftIndex]);
      leftIndex++;
    } else {
      result.push(right[rightIndex]);
      rightIndex++;
    }
  }

  // Add remaining elements
  while (leftIndex < left.length) {
    result.push(left[leftIndex]);
    leftIndex++;
  }

  while (rightIndex < right.length) {
    result.push(right[rightIndex]);
    rightIndex++;
  }

  return result;
}

Memecahkan Fungsi Gabungan:

1. Persediaan Fungsi:

   const result = [];
   let leftIndex = 0;
   let rightIndex = 0;

• Mencipta tatasusunan kosong untuk menyimpan hasil gabungan
• Memulakan penunjuk untuk kedua-dua tatasusunan input
• Fikirkan penunjuk ini seperti jari yang menjejaki di mana kita berada dalam setiap tatasusunan

1. Logik Penggabungan Utama:

   while (leftIndex < left.length && rightIndex < right.length) {
     if (left[leftIndex] <= right[rightIndex]) {
       result.push(left[leftIndex]);
       leftIndex++;
     } else {
       result.push(right[rightIndex]);
       rightIndex++;
     }
   }

• Membandingkan elemen daripada kedua-dua tatasusunan
• Mengambil elemen yang lebih kecil dan menambahkannya pada hasil
• Menggerakkan penuding ke hadapan dalam tatasusunan yang kami ambil daripada
• Seperti memilih yang lebih kecil daripada dua kad semasa mengisih dek

1. Fasa Pembersihan:

   while (leftIndex < left.length) {
     result.push(left[leftIndex]);
     leftIndex++;
   }

• Menambah sebarang elemen yang tinggal
• Diperlukan kerana satu tatasusunan mungkin lebih panjang daripada yang lain
• Seperti mengumpul kad yang tinggal selepas membandingkan

Fungsi Isih Gabungan Utama

function mergeSort(arr) {
  // Base case
  if (arr.length <= 1) {
    return arr;
  }

  // Divide
  const middle = Math.floor(arr.length / 2);
  const left = arr.slice(0, middle);
  const right = arr.slice(middle);

  // Conquer and Combine
  return merge(mergeSort(left), mergeSort(right));
}

Memecahkan MergeSort:

1. Kes Asas:

   if (arr.length <= 1) {
     return arr;
   }

• Mengendalikan tatasusunan dengan panjang 0 atau 1
• Ini sudah diisih mengikut takrifan
• Bertindak sebagai titik perhentian rekursi kami

1. Fasa Pembahagian:

   const middle = Math.floor(arr.length / 2);
   const left = arr.slice(0, middle);
   const right = arr.slice(middle);

• Memisahkan tatasusunan kepada dua bahagian
• slice() mencipta tatasusunan baharu tanpa mengubah suai asal
• Seperti memotong dek kad separuh

1. Isih dan Penggabungan Rekursif:

   return merge(mergeSort(left), mergeSort(right));

• Isih setiap separuh secara rekursif
• Menggabungkan bahagian yang diisih menggunakan fungsi gabungan
• Seperti menyusun longgokan kad yang lebih kecil sebelum menggabungkannya

Contoh Panduan

Mari kita lihat bagaimana ia disusun [38, 27, 43, 3]:

1. Pecahan Pertama:

// The Merge Helper Function
function merge(left, right) {
  const result = [];
  let leftIndex = 0;
  let rightIndex = 0;

  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] <= right[rightIndex]) {
      result.push(left[leftIndex]);
      leftIndex++;
    } else {
      result.push(right[rightIndex]);
      rightIndex++;
    }
  }

  // Add remaining elements
  while (leftIndex < left.length) {
    result.push(left[leftIndex]);
    leftIndex++;
  }

  while (rightIndex < right.length) {
    result.push(right[rightIndex]);
    rightIndex++;
  }

  return result;
}

1. Pecahan Kedua:

   const result = [];
   let leftIndex = 0;
   let rightIndex = 0;

1. Gabung Kembali:

   while (leftIndex < left.length && rightIndex < right.length) {
     if (left[leftIndex] <= right[rightIndex]) {
       result.push(left[leftIndex]);
       leftIndex++;
     } else {
       result.push(right[rightIndex]);
       rightIndex++;
     }
   }

Kesimpulan

Merge Sort menonjol sebagai algoritma pengisihan yang sangat cekap yang konsisten berprestasi baik pada set data yang besar. Walaupun ia memerlukan ruang tambahan berbanding dengan algoritma pengisihan yang lebih mudah, kerumitan masa O(n log n) menjadikannya pilihan utama untuk banyak aplikasi dunia nyata yang prestasinya penting.

Pengambilan utama:

• Menggunakan strategi bahagi-dan-takluk
• O(n log n) kerumitan masa dalam semua kes
• Memerlukan O(n) ruang tambahan
• Algoritma pengisihan stabil
• Sangat baik untuk set data yang besar

Kekal Kemas Kini dan Terhubung

Untuk memastikan anda tidak terlepas mana-mana bahagian dalam siri ini dan berhubung dengan saya untuk lebih mendalam
perbincangan tentang Pembangunan Perisian (Web, Pelayan, Mudah Alih atau Mengikis / Automasi), data
struktur dan algoritma, dan topik teknologi menarik lain, ikuti saya di:

Emmanuel Ayinde Ikuti

Jurutera Perisian | Penulis Teknikal | Bahagian Belakang, Pembangun Web & Mudah Alih ? | Ghairah untuk mencipta penyelesaian perisian yang cekap dan berskala. #letsconnect ?

• GitHub
• Linkedin
• X (Twitter)

Nantikan dan selamat mengekod ?‍??

Atas ialah kandungan terperinci Memahami algoritma isihan gabungan: Panduan pemula untuk menguasai algoritma isihan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!