Menguasai Algoritma Isih seperti PRO

Memandangkan kita telah bercakap tentang algoritma pengisihan yang berbeza, hari ini kita akan belajar tentang algoritma isihan pemilihan. Algoritma pengisihan yang membenarkan jumlah swap minimum yang mungkin dalam persekitaran yang dikekang memori.

Jadual Kandungan

1. Pengenalan
2. Apakah itu Algoritma Isih Pemilihan?
3. Bagaimanakah isihan pemilihan berfungsi?
   • Kerumitan Masa
   • Kerumitan Angkasa
4. Pelaksanaan dalam JavaScript
5. Menyelesaikan Masalah LeetCode
6. Kesimpulan

pengenalan

Isih pilihan ialah algoritma pengisihan yang mudah tetapi berkesan yang berfungsi dengan berulang kali memilih elemen terkecil (atau terbesar) daripada bahagian senarai yang tidak diisih dan mengalihkannya ke permulaan (atau penghujung) bahagian yang diisih. Proses ini diulang sehingga keseluruhan senarai diisih. Dalam artikel ini, kami akan menyelidiki butiran algoritma isihan pemilihan, pelaksanaannya dalam JavaScript dan aplikasinya dalam menyelesaikan masalah dunia sebenar.

Apakah Algoritma Isih Pemilihan?

Algoritma Isih Pilihan ialah algoritma pengisihan perbandingan di tempat. Ia membahagikan senarai input kepada dua bahagian:

1. Bahagian yang diisih di hujung kiri
2. Bahagian yang tidak diisih di hujung kanan

Algoritma berulang kali memilih elemen terkecil daripada bahagian yang tidak diisih dan menukarnya dengan elemen yang tidak diisih paling kiri, mengalihkan sempadan antara bahagian yang diisih dan tidak diisih satu elemen ke kanan.

Bagaimanakah isihan pemilihan berfungsi?

Mari kita lihat contoh menggunakan tatasusunan [64, 25, 12, 22, 11]:

1. Tatasusunan awal: [64, 25, 12, 22, 11]

• Bahagian yang diisih: []
• Bahagian tidak diisih: [64, 25, 12, 22, 11]

1. Hasil pertama:

• Cari minimum dalam bahagian yang tidak diisih: 11
• Tukar 11 dengan elemen pertama yang tidak diisih (64)
• Keputusan: [11, 25, 12, 22, 64]
• Bahagian yang diisih: [11]
• Bahagian tidak diisih: [25, 12, 22, 64]

1. Pas kedua:

• Cari minimum dalam bahagian yang tidak diisih: 12
• Tukar 12 dengan elemen pertama yang tidak diisih (25)
• Keputusan: [11, 12, 25, 22, 64]
• Bahagian yang diisih: [11, 12]
• Bahagian tidak diisih: [25, 22, 64]

1. Hasil ketiga:

• Cari minimum dalam bahagian yang tidak diisih: 22
• Tukar 22 dengan elemen pertama yang tidak diisih (25)
• Keputusan: [11, 12, 22, 25, 64]
• Bahagian yang diisih: [11, 12, 22]
• Bahagian tidak diisih: [25, 64]

1. Hasil keempat:

• Cari minimum dalam bahagian yang tidak diisih: 25
• 25 sudah berada di kedudukan yang betul
• Keputusan: [11, 12, 22, 25, 64]
• Bahagian diisih: [11, 12, 22, 25]
• Bahagian yang tidak diisih: [64]

1. Pas akhir:
   • Hanya satu elemen lagi, ia secara automatik berada di kedudukan yang betul
   • Keputusan akhir: [11, 12, 22, 25, 64]

Tatasusunan kini diisih sepenuhnya.

Kerumitan Masa

Isih Pilihan mempunyai kerumitan masa O(n^2) dalam semua kes (terbaik, purata dan paling teruk), dengan n ialah bilangan elemen dalam tatasusunan. Ini kerana:

• Gelung luar berjalan n-1 kali
• Untuk setiap lelaran gelung luar, gelung dalam berjalan n-i-1 kali (di mana i ialah lelaran semasa gelung luar)

Ini menghasilkan lebih kurang (n^2)/2 perbandingan dan n swap, yang memudahkan kepada O(n^2).

Disebabkan kerumitan masa kuadratik ini, Isih Pemilihan tidak cekap untuk set data yang besar. Walau bagaimanapun, kesederhanaan dan fakta bahawa ia menjadikan bilangan pertukaran minimum yang mungkin boleh menjadikannya berguna dalam situasi tertentu, terutamanya apabila ingatan tambahan adalah terhad.

Kerumitan Ruang

Isih Pilihan mempunyai kerumitan ruang O(1) kerana ia mengisih tatasusunan di tempatnya. Ia hanya memerlukan jumlah ruang memori tambahan yang tetap tanpa mengira saiz input. Ini menjadikannya cekap ingatan, yang boleh berfaedah dalam persekitaran yang dikekang ingatan.

Pelaksanaan dalam JavaScript

Berikut ialah pelaksanaan JavaScript bagi Algoritma Isih Pemilihan:

function selectionSort(arr) {
  const n = arr.length;

  for (let i = 0; i < n - 1; i++) {
    let minIndex = i;

    // Find the minimum element in the unsorted portion
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }

    // Swap the found minimum element with the first unsorted element
    if (minIndex !== i) {
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
  }

  return arr;
}

// Example usage
const unsortedArray = [64, 25, 12, 22, 11];
console.log("Unsorted array:", unsortedArray);
console.log("Sorted array:", selectionSort(unsortedArray));

Jom pecahkan kod:

1. Kami mentakrifkan selectionSort yang mengambil tatasusunan sebagai input.
2. Kami mengulangi tatasusunan dengan gelung luar (i), yang mewakili sempadan antara bahagian yang diisih dan tidak diisih.
3. Untuk setiap lelaran, kami menganggap elemen pertama yang tidak diisih ialah minimum dan menyimpan indeksnya.
4. Kami kemudian menggunakan gelung dalam (j) untuk mencari elemen minimum sebenar dalam bahagian yang tidak diisih.
5. Jika kami menemui elemen yang lebih kecil, kami mengemas kini minIndex.
6. Selepas mencari minimum, kami menukarnya dengan elemen pertama yang tidak diisih jika perlu.
7. Kami mengulangi proses ini sehingga keseluruhan tatasusunan diisih.

Menyelesaikan Masalah LeetCode

Mari selesaikan satu masalah algoritma leetcode menggunakan algoritma isihan pemilihan. Boleh?

Masalah: Isih Tatasusunan [Sederhana]

Masalah: Memandangkan tatasusunan nombor integer, susun tatasusunan dalam tertib menaik dan kembalikannya. Anda mesti menyelesaikan masalah tanpa menggunakan sebarang fungsi terbina dalam dalam kerumitan masa O(nlog(n)) dan dengan kerumitan ruang terkecil yang mungkin.

Pendekatan:: Untuk menyelesaikan masalah ini, kami boleh terus menggunakan algoritma Isih Pemilihan. Ini melibatkan lelaran melalui tatasusunan, mencari elemen terkecil dalam bahagian yang tidak diisih, dan menukarnya dengan elemen yang tidak diisih pertama. Kami mengulangi proses ini sehingga keseluruhan tatasusunan diisih.

Penyelesaian:

function selectionSort(arr) {
  const n = arr.length;

  for (let i = 0; i < n - 1; i++) {
    let minIndex = i;

    // Find the minimum element in the unsorted portion
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }

    // Swap the found minimum element with the first unsorted element
    if (minIndex !== i) {
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
  }

  return arr;
}

// Example usage
const unsortedArray = [64, 25, 12, 22, 11];
console.log("Unsorted array:", unsortedArray);
console.log("Sorted array:", selectionSort(unsortedArray));

Penyelesaian ini secara langsung menggunakan algoritma Isih Pemilihan yang kami laksanakan sebelum ini. Walaupun ia menyelesaikan masalah dengan betul, perlu diperhatikan bahawa penyelesaian ini mungkin melebihi had masa untuk input besar pada LeetCode disebabkan oleh kerumitan masa O(n^2) bagi Isih Pemilihan. Imej di bawah menunjukkan bahawa penyelesaiannya betul tetapi tidak cekap.

Kesimpulan

Kesimpulannya, Isih Pemilihan ialah algoritma pengisihan yang mudah dan intuitif yang berfungsi sebagai pengenalan yang sangat baik kepada dunia teknik isihan. Kesederhanaannya menjadikannya mudah untuk difahami dan dilaksanakan, menjadikannya alat pembelajaran yang berharga untuk pemula. Walau bagaimanapun, disebabkan kerumitan masa kuadratiknya O(n^2), ia tidak cekap untuk set data yang besar. Untuk set data yang lebih besar atau aplikasi kritikal prestasi, algoritma yang lebih cekap seperti QuickSort, MergeSort atau fungsi pengisihan terbina dalam lebih disukai.

---

---

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:

Penyelesaian Hebat ?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 Menguasai Algoritma Isih seperti PRO. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!