Mempelajari Algoritma Isih Pantas

Isih Pantas ialah salah satu algoritma yang paling cekap dan ia menggunakan teknik bahagi-dan-takluk untuk mengisih tatasusunan.

Cara Isih Pantas Berfungsi

Idea utama Isih Pantas adalah untuk membantu satu elemen pada satu masa bergerak ke kedudukan yang betul dalam tatasusunan yang tidak diisih. Elemen ini dipanggil pangsi.

Elemen pangsi berada di kedudukan yang betul apabila:

1. Semua elemen di sebelah kirinya lebih kecil.
2. Semua elemen di sebelah kanannya lebih besar.

Tidak kira sama ada nombor di sebelah kiri atau kanan sudah diisih. Apa yang penting ialah pangsi berada pada kedudukan yang betul dalam tatasusunan.

// examples of the pivot 23 positioned correctly in the array:
[3, 5, 6, 12, 23, 25, 24, 30]
[6, 12, 5, 3, 23, 24, 30, 25]
[3, 6, 5, 12, 23, 30, 25, 24]

Semua ini adalah keluaran yang sah bagi tatasusunan dengan pangsinya ialah 23.

Mencari Kedudukan Pivot yang Betul

Isih Pantas membantu pangsi mencari kedudukannya yang betul dalam tatasusunan. Sebagai contoh, jika pangsi diposisikan pada permulaan tatasusunan tetapi bukan nombor terkecil, Isih Pantas menentukan bahawa ia perlu menggerakkan 5 langkah untuk memberi ruang kepada 5 elemen yang lebih kecil dalam tatasusunan -- dengan mengandaikan terdapat 5 seperti itu. nombor.

Katakan kita mempunyai tatasusunan: [10, 4, 15, 6, 23, 40, 1, 17, 7, 8] dan 10 ialah pangsi:

Pada ketika ini:

• Nombor 10 tidak tahu sama ada ia berada dalam kedudukan yang betul atau berapa banyak langkah yang perlu digerakkan untuk sampai ke sana. Isih Pantas bermula dengan membandingkan 10 dengan nilai pada indeks seterusnya.
• Apabila melihat 4 lebih kecil, Isih Pantas merekodkan bahawa pangsi perlu bergerak satu langkah ke hadapan untuk membolehkan 4 datang sebelum itu.
• Jadi numberOfStepsToMove meningkat sebanyak 1.

Seterusnya, pada indeks 2, nilainya ialah 15, iaitu lebih besar daripada 10. Memandangkan tiada pelarasan diperlukan, Isih Pantas mengekalkan kiraan langkah tidak berubah dan beralih ke elemen seterusnya dalam tatasusunan.

Pada indeks seterusnya, nilainya ialah 6, iaitu lebih kecil daripada 10. Isih Pantas meningkatkan kiraan langkah kepada 2, kerana pangsi kini perlu memberi ruang untuk dua nombor yang lebih kecil: 4 dan 6 .

Kini, 6 perlu bertukar dengan 15 untuk mengekalkan nombor yang lebih kecil bersebelahan antara satu sama lain di sebelah kiri tatasusunan. Kami menukar nombor berdasarkan indeks semasa dan nilai numberOfStepsToMove.

Isih Pantas terus menggelung melalui tatasusunan, meningkatkan bilanganOfStepsToMove berdasarkan bilangan nombor yang lebih kecil daripada pangsi. Ini membantu menentukan sejauh mana pangsi perlu bergerak ke kedudukan yang betul.

NumberOfStepsToMove tidak berubah untuk 23 atau 40 kerana kedua-dua nilai lebih besar daripada pangsi dan tidak sepatutnya muncul sebelum itu dalam tatasusunan:

Sekarang, apabila Isih Pantas gelung kepada nilai 1 pada indeks 6, numberOfStepsToMove meningkat kepada 3 dan menukarnya dengan nombor pada indeks 3:

Isih Pantas meneruskan proses ini sehingga ia mencapai penghujung tatasusunan:

Sekarang kita telah sampai ke penghujung tatasusunan, kita tahu bahawa terdapat 5 nombor yang lebih kecil daripada 10. Oleh itu, pangsi (10) mesti bergerak 5 langkah ke hadapan ke kedudukan yang betul, di mana ia lebih besar daripada semua nombor sebelum itu.

Mari kita lihat bagaimana ia kelihatan dalam kod:

// examples of the pivot 23 positioned correctly in the array:
[3, 5, 6, 12, 23, 25, 24, 30]
[6, 12, 5, 3, 23, 24, 30, 25]
[3, 6, 5, 12, 23, 30, 25, 24]

Sekarang kita mempunyai fungsi untuk membantu kita mencari tempat untuk meletakkan pangsi, mari lihat bagaimana Qucik Sort membahagikan tatasusunan kepada tatasusunan yang lebih kecil dan menggunakan fungsi getNumberOfStepsToMove untuk meletakkan semua elemen tatasusunan.

const getNumberOfStepsToMove = (arr, start = 0, end = arr.length - 1) => {
  let numberOfStepsToMove = start;
  // we're picking the first element in the array as the pivot
  const pivot = arr[start];

  // start checking the next elements to the pivot
  for (let i = start + 1; i <= end; i++) {
    // is the current number less than the pivot?
    if (arr[i] < pivot) {
      // yes - so w should increase numberOfStepsToMove
// or the new index of the pivot
      numberOfStepsToMove++;

      // now swap the number at the index of numberOfStepsToMove with the smaller one
      [arr[i], arr[numberOfStepsToMove]] = [arr[numberOfStepsToMove], arr[i]];
    } else {
      // what if it's greater?
      // do nothing -- we need to move on to the next number
      // to check if we have more numbers less that pivot to increase numberOfStepsToMove or not
    }
  }

  // now we know the pivot is at arr[start] and we know that it needs to move numberOfStepsToMove
  // so we swap the numbers to place the pivot number to its correct position
  [arr[start], arr[numberOfStepsToMove]] = [
    arr[numberOfStepsToMove],
    arr[start],
  ];

  return numberOfStepsToMove;
};

Isih Pantas memanfaatkan rekursi untuk membahagikan tatasusunan dengan cekap kepada subarray yang lebih kecil, memastikan elemen diisih dengan membandingkannya dengan pangsi.

function quickSort(arr, left = 0, right = arr.length - 1) {
  // pivotIndex the new index of the pivot in in the array
  // in our array example, at the first call this will be 5, because we are checking 10 as the pivot
  // on the whole array
  let pivotIndex = getNumberOfStepsToMove(arr, left, right);
}

• Algoritma secara rekursif mengisih subarray kiri yang mengandungi elemen yang lebih kecil daripada pangsi.
• Rekursi berhenti apabila subarray mempunyai satu atau sifar elemen, kerana ia telah diisih.

Sekarang kita perlu melakukan proses yang sama di sebelah kanan tatasusunan:

// examples of the pivot 23 positioned correctly in the array:
[3, 5, 6, 12, 23, 25, 24, 30]
[6, 12, 5, 3, 23, 24, 30, 25]
[3, 6, 5, 12, 23, 30, 25, 24]

Dalam contoh ini, bahagian kanan sudah diisih tetapi algoritma tidak mengetahuinya dan ia akan diisih jika tidak.

Atas ialah kandungan terperinci Mempelajari Algoritma Isih Pantas. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!