Memecahkan algoritma Isih Pantas: Dari Teori kepada Amalan dalam Minit

Quicksort ialah salah satu algoritma pengisihan terpantas. Ia memerlukan tatasusunan nilai, memilih salah satu nilai sebagai elemen 'pangsi' dan menggerakkan nilai lain supaya nilai yang lebih rendah berada di sebelah kiri elemen pangsi dan nilai yang lebih tinggi berada di sebelah kanannya.

Isih Pantas berdiri sebagai salah satu algoritma pengisihan yang paling elegan dan cekap dalam dunia algoritma. Tidak seperti algoritma yang lebih mudah seperti Bubble Sort atau Selection Sort, Quick Sort menggunakan strategi bahagi-dan-takluk yang canggih yang menjadikannya lebih pantas dalam amalan. Walaupun Merge Sort juga menggunakan divide-and-conquer, pendekatan pembahagian unik Quick Sort selalunya membawa kepada prestasi dan penggunaan memori yang lebih baik.

Purata Kerumitan Masa: O(n log n)

Kerumitan Masa Kes Terburuk: O(n²)

Kerumitan Ruang: O(log n)

Jadual Kandungan

1. Apakah algoritma isihan pantas
2. Cara pengisihan pantas berfungsi
   • Kerumitan Masa
   • Kerumitan Angkasa
3. Pelaksanaan JavaScript
4. Kesimpulan

Apakah itu Algoritma Isih Pantas

Isih Pantas ialah algoritma pengisihan yang sangat cekap yang berfungsi dengan memilih elemen 'pivot' daripada tatasusunan dan membahagikan elemen lain kepada dua sub-tatasusunan mengikut sama ada ia kurang daripada atau lebih besar daripada pangsi. Tidak seperti Merge Sort, yang membahagikan dahulu dan bergabung kemudian, Quick Sort melakukan pengisihannya semasa proses pembahagian.

Pertimbangkan perbandingan ini dengan algoritma pengisihan lain:

Algorithm	Time Complexity (Average)	Space Complexity	In-Place?
Quick Sort	O(n log n)	O(log n)	Yes
Merge Sort	O(n log n)	O(n)	No
Bubble Sort	O(n²)	O(1)	Yes
Selection Sort	O(n²)	O(1)	Yes
Heap Sort	O(n log n)	O(1)	Yes

Bagaimanakah pengisihan pantas berfungsi?

Sebelum kita menyelami pelaksanaan JavaScript bagi algoritma isihan pantas, mari kita ambil pendekatan langkah demi langkah untuk memahami cara algoritma berfungsi dengan mengisih susunan nombor ringkas secara manual dengan hanya empat langkah mudah.

Isih pantas boleh dipecahkan kepada empat langkah mudah:

1. Pilih elemen pangsi daripada tatasusunan. Elemen ini boleh jadi elemen pertama, terakhir, tengah atau malah unsur rawak daripada senarai/tatasusunan.
2. Susun semula tatasusunan supaya semua elemen yang kurang daripada pangsi berada di sebelah kiri dan semua elemen yang lebih besar berada di sebelah kanan.
3. Tukar elemen pangsi dengan elemen pertama nilai yang lebih besar, supaya pangsi berada di tengah.
4. Gunakan operasi yang sama secara rekursif pada sub-tatasusunan di sebelah kiri dan kanan pangsi.

Mari kita gunakan langkah ini pada tatasusunan sebenar. Boleh?

Susun Awal: [3, 6, 2, 7, 1]

Langkah 1: Pilih Pivot

• Kami memilih elemen terakhir sebagai pangsi untuk kesederhanaan.
• Pivot = 1

Langkah 2: Susun Semula Tatasusunan Sekitar Pivot

• Susun semula supaya semua elemen yang kurang daripada pangsi (1) berada di sebelah kiri dan semua elemen yang lebih besar berada di sebelah kanan.
• Semasa kita melalui setiap elemen:
  • 3 (lebih daripada 1) → kekal di sebelah kanan.
  • 6 (lebih daripada 1) → kekal di sebelah kanan.
  • 2 (lebih daripada 1) → kekal di sebelah kanan.
  • 7 (lebih daripada 1) → kekal di sebelah kanan.
• Susun Semula Tatasusunan: [1, 6, 2, 7, 3]

Langkah 3: Tukar Pivot kepada Kedudukan Betulnya

• Tukar pangsi (1) dengan elemen pertama yang lebih besar daripadanya, iaitu 6.
• Susun atur selepas bertukar: [1, 3, 2, 7, 6]
• Kini, 1 berada pada kedudukan yang betul (indeks 0).

Langkah 4: Isih Pantas Rekursif pada Sub-tatasusunan

• Sub-tatasusunan Kiri: [] (tiada unsur tinggal 1, jadi tiada apa-apa untuk diisih di sini)
• Sub-array Kanan: [3, 2, 7, 6]

---

Menyusun Sub-array Kanan [3, 2, 7, 6] secara rekursif

Langkah 1: Pilih Pivot

• Pivot = 6 (elemen terakhir)

Langkah 2: Susun Semula Tatasusunan Sekitar Pivot

• Susun elemen kurang daripada 6 ke kiri dan elemen lebih besar ke kanan:
  • 3 (kurang daripada 6) → kekal di sebelah kiri.
  • 2 (kurang daripada 6) → kekal di sebelah kiri.
  • 7 (lebih daripada 6) → kekal di sebelah kanan.
• Susun Semula Tatasusunan: [3, 2, 6, 7]

Langkah 3: Tukar Pivot kepada Kedudukannya yang Betul

• 6 sudah berada di kedudukan yang betul (indeks 2).
• Susun atur: [1, 3, 2, 6, 7]

Langkah 4: Isih Pantas Rekursif pada Sub-tatasusunan

• Sub-array Kiri: [3, 2]
• Sub-array Kanan: [7] (elemen tunggal, tiada pengisihan diperlukan)

---

Menyusun Sub-array Kiri [3, 2]

Langkah 1: Pilih Pivot

• Pivot = 2 (elemen terakhir)

Langkah 2: Susun Semula Tatasusunan Sekitar Pivot

• Susun semula supaya elemen kurang daripada 2 berada di sebelah kiri:
  • 3 (lebih daripada 2) → kekal di sebelah kanan.
• Susun Semula Tatasusunan: [2, 3]

Langkah 3: Tukar Pivot kepada Kedudukannya yang Betul

• 2 sudah berada di kedudukan yang betul (indeks 1).
• Susunatur: [1, 2, 3, 6, 7]

Langkah 4: Isih Pantas Rekursif pada Sub-tatasusunan

• Sub-array Kiri: [] (tiada unsur)
• Sub-array Kanan: [3] (elemen tunggal, tiada pengisihan diperlukan)

---

Tatasusunan Isih Akhir

Selepas mengisih semua sub-tatasusunan, kami mendapat tatasusunan diisih terakhir:

Susun Isih: [1, 2, 3, 6, 7]

Di bawah ialah ilustrasi terbaik tentang cara ini berfungsi dalam kehidupan sebenar:

Kerumitan Masa

Kerumitan masa Isih Pantas berbeza-beza berdasarkan pemilihan pangsi:

• Kes Terbaik (O(n log n)):

  • Berlaku apabila pangsi sentiasa membahagikan tatasusunan kepada bahagian yang sama
  • Serupa dengan prestasi Merge Sort

• Kes Purata (O(n log n)):

  • Kebanyakan senario praktikal
  • Lebih baik daripada Isih Gabung kerana penggunaan cache yang lebih baik

• Kes Terburuk (O(n²)):

  • Berlaku dengan tatasusunan yang telah diisih dan pemilihan pangsi yang lemah
  • Boleh dielakkan dengan strategi pemilihan pangsi yang baik

Kerumitan Ruang

Kerumitan ruang Isih Cepat ialah O(log n) disebabkan oleh:

• Kedalaman tindanan panggilan rekursif
• Pembahagian di tempat (tidak seperti ruang tambahan O(n) Merge Sort)
• Kecekapan memori yang lebih baik berbanding dengan Merge Sort

Pelaksanaan JavaScript

function quickSort(arr) {
  // Base case: arrays with length 0 or 1 are already sorted
  if (arr.length <= 1) return arr;

  // Helper function to swap elements
  const swap = (i, j) => {
    [arr[i], arr[j]] = [arr[j], arr[i]];
  };

  // Partition function using Lomuto's partition scheme
  function partition(low, high) {
    const pivot = arr[high];
    let i = low - 1;

    for (let j = low; j < high; j++) {
      if (arr[j] <= pivot) {
        i++;
        swap(i, j);
      }
    }
    swap(i + 1, high);
    return i + 1;
  }

  // Main quickSort function implementation
  function quickSortHelper(low, high) {
    if (low < high) {
      const pivotIndex = partition(low, high);
      quickSortHelper(low, pivotIndex - 1); // Sort left side
      quickSortHelper(pivotIndex + 1, high); // Sort right side
    }
  }

  quickSortHelper(0, arr.length - 1);
  return arr;
}

Kesimpulan

Isih Pantas ialah pilihan yang popular kerana kecekapannya dan pengisihan di tempatnya. Ia mengatasi prestasi algoritma yang lebih mudah seperti Isih Buih dan Isih Pemilihan dengan prestasi kes purata O(n log n) dan kerumitan ruang yang rendah.

Pengambilan utama:

1. Pilih strategi pemilihan pangsi dengan berhati-hati
2. Pertimbangkan ciri input apabila membuat keputusan antara Isih Pantas dan algoritma lain
3. Gunakan pemilihan pangsi rawak untuk prestasi purata kes yang lebih baik

---

---

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 Memecahkan algoritma Isih Pantas: Dari Teori kepada Amalan dalam Minit. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!