πŸ”

Π‘ΠΎΡ€Ρ‚ΠΈΡ€ΠΎΠ²ΠΊΠ° ΠΏΡƒΠ·Ρ‹Ρ€ΡŒΠΊΠΎΠΌ (bubble sort) Π½Π° javascript

Π‘ΠΎΡ€Ρ‚ΠΈΡ€ΠΎΠ²ΠΊΠ° ΠΏΡƒΠ·Ρ‹Ρ€ΡŒΠΊΠΎΠΌ (bubble sort) Π½Π° javascript

Bubble Sort являСтся ΠΎΠ΄Π½ΠΈΠΌ ΠΈΠ· Π½Π°ΠΈΠ±ΠΎΠ»Π΅Π΅ ΡˆΠΈΡ€ΠΎΠΊΠΎ обсуТдаСмых Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ², просто ΠΈΠ·-Π·Π° нСдостаточной эффСктивности сортировки массивов. Если массив ΡƒΠΆΠ΅ отсортирован, Bubble Sort Π±ΡƒΠ΄Π΅Ρ‚ ΠΏΡ€ΠΎΡ…ΠΎΠ΄ΠΈΡ‚ΡŒ Ρ‡Π΅Ρ€Π΅Π· массив Ρ‚ΠΎΠ»ΡŒΠΊΠΎ ΠΎΠ΄ΠΈΠ½ Ρ€Π°Π· (с использованиСм ΠΊΠΎΠ½Ρ†Π΅ΠΏΡ†ΠΈΠΈ Π΄Π²Π° Π½ΠΈΠΆΠ΅), ΠΎΠ΄Π½Π°ΠΊΠΎ Π² Ρ…ΡƒΠ΄ΡˆΠ΅ΠΌ случаС это врСмя выполнСния O(nΒ²), ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠ΅ ΠΊΡ€Π°ΠΉΠ½Π΅ нСэффСктивно.

Когда ΠΌΡ‹ рисуСм ΡΠΊΠΎΡ€ΠΎΡΡ‚ΡŒ роста O(nΒ²), ΠΌΡ‹ Π²ΠΈΠ΄ΠΈΠΌ, Ρ‡Ρ‚ΠΎ ΠΏΠΎ ΡΡ€Π°Π²Π½Π΅Π½ΠΈΡŽ с Π΄Ρ€ΡƒΠ³ΠΈΠΌΠΈ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ°ΠΌΠΈ сортировки, Ρ‚Π°ΠΊΠΈΠΌΠΈ ΠΊΠ°ΠΊ сортировка слияниСм, Ρ‚ΠΎ Π΅ΡΡ‚ΡŒ O(n log n), ΠΎΠ½ растСт Π³ΠΎΡ€Π°Π·Π΄ΠΎ быстрСС.

Π‘Ρ€Π°Π²Π½Π΅Π½ΠΈΠ΅ скорости сортировок

НС смотря Π½Π° Π½Π΅ΡΡ„Ρ„Π΅ΠΊΡ‚ΠΈΠ²Π½ΠΎΡΡ‚ΡŒ Bubble Sort, всС Π΅Ρ‰Π΅ Π²Π°ΠΆΠ½ΠΎ ΠΏΠΎΠ½ΡΡ‚ΡŒ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ ΠΈ ΠΏΠΎΠ½ΡΡ‚ΡŒ, ΠΏΠΎΡ‡Π΅ΠΌΡƒ ΠΎΠ½ Ρ‚Π°ΠΊ ΠΏΠ»ΠΎΡ….

Π”Π°Π²Π°ΠΉΡ‚Π΅ углубимся Π² Π΄Π²Π΅ ΠΊΠΎΠ½Ρ†Π΅ΠΏΡ†ΠΈΠΈ кодирования Bubble Sort.

ΠšΠΎΠ½Ρ†Π΅ΠΏΡ†ΠΈΡ 1

  • Π˜Ρ‚Π΅Ρ€Π°Ρ†ΠΈΡ ΠΏΠΎ массиву ΠΈ ΠΏΡ€ΠΎΠ²Π΅Ρ€ΠΊΠ° ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ элСмСнта ΠΏΠΎ ΡΠ»Π΅Π΄ΡƒΡŽΡ‰Π΅ΠΌΡƒ элСмСнту Π² массивС.
  • Если Ρ‚Π΅ΠΊΡƒΡ‰ΠΈΠΉ элСмСнт большС, Ρ‡Π΅ΠΌ ΡΠ»Π΅Π΄ΡƒΡŽΡ‰ΠΈΠΉ элСмСнт, мСняйтС ΠΈΡ… мСстами.
  • Если ΠΎΠ½ Π½Π΅ большС, пСрСмСститС ΡƒΠΊΠ°Π·Π°Ρ‚Π΅Π»ΠΈ Π²Π²Π΅Ρ€Ρ… ΠΈ сравнитС ΡΠ»Π΅Π΄ΡƒΡŽΡ‰ΠΈΠ΅ Π΄Π²Π° элСмСнта.
  • Как Ρ‚ΠΎΠ»ΡŒΠΊΠΎ ΠΌΡ‹ достигаСм ΠΊΠΎΠ½Ρ†Π° массива, ΠΌΡ‹ Π·Π½Π°Π΅ΠΌ, Ρ‡Ρ‚ΠΎ самый большой элСмСнт находится Π² послСднСй ΠΏΠΎΠ·ΠΈΡ†ΠΈΠΈ.
  • ΠŸΠΎΠ²Ρ‚ΠΎΡ€ΠΈΡ‚Π΅ этот процСсс N Ρ€Π°Π·, Π³Π΄Π΅ N - Π΄Π»ΠΈΠ½Π° массива, ΠΈ ΠΊΠ°ΠΆΠ΄Ρ‹ΠΉ Ρ€Π°Π· повторяйтС Π΄ΠΎ послСднСго отсортированного элСмСнта.

Визуализация ΠΊΠΎΠ½Ρ†Π΅ΠΏΡ†ΠΈΠΈ 1

Нам Π½ΡƒΠΆΠ½ΠΎ ΠΈΠΌΠ΅Ρ‚ΡŒ Π΄Π²Π° указатСля (Π΄Π²Π° Π²Π»ΠΎΠΆΠ΅Π½Π½Ρ‹Ρ… Ρ†ΠΈΠΊΠ»Π°) для ΠΊΠΎΠ½Ρ†Π΅ΠΏΡ†ΠΈΠΈ ΠΎΠ΄ΠΈΠ½. ΠšΠ°ΠΆΠ΄Ρ‹ΠΉ Ρ€Π°Π·, ΠΊΠΎΠ³Π΄Π° ΠΌΡ‹ выполняСм ΠΈΡ‚Π΅Ρ€Π°Ρ†ΠΈΡŽ, вСрхняя Π³Ρ€Π°Π½ΠΈΡ†Π° ΡƒΠΌΠ΅Π½ΡŒΡˆΠ°Π΅Ρ‚ΡΡ Π½Π° Π΅Π΄ΠΈΠ½ΠΈΡ†Ρƒ, ΠΏΠΎΡΠΊΠΎΠ»ΡŒΠΊΡƒ ΠΌΡ‹ Π·Π½Π°Π΅ΠΌ, Ρ‡Ρ‚ΠΎ этот индСкс содСрТит отсортированноС Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅.

function bubbleSortConcept1(arr) {
  for (let j = arr.length - 1; j > 0; j--) {
    for (let i = 0; i < j; i++) {
      if (arr[i] > arr[i + 1]) {
        let temp = arr[i];
        arr[i] = arr[i + 1];
        arr[i + 1] = temp;
      }
    }
  }
  
  return arr;
}

ΠšΠΎΠ½Ρ†Π΅ΠΏΡ†ΠΈΡ 2

  • Π˜Ρ‚Π΅Ρ€Π°Ρ†ΠΈΡ ΠΏΠΎ массиву ΠΈ ΠΏΡ€ΠΎΠ²Π΅Ρ€ΠΊΠ° ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ элСмСнта ΠΏΠΎ ΡΠ»Π΅Π΄ΡƒΡŽΡ‰Π΅ΠΌΡƒ элСмСнту Π² массивС.
  • Если Ρ‚Π΅ΠΊΡƒΡ‰ΠΈΠΉ элСмСнт большС, Ρ‡Π΅ΠΌ ΡΠ»Π΅Π΄ΡƒΡŽΡ‰ΠΈΠΉ элСмСнт, мСняйтС ΠΈΡ… мСстами. Π£ΠΊΠ°ΠΆΠΈΡ‚Π΅, Ρ‡Ρ‚ΠΎ ΠΏΡ€ΠΎΠΈΠ·ΠΎΡˆΠ΅Π» ΠΎΠ±ΠΌΠ΅Π½.
  • Если ΠΏΡ€ΠΎΠΈΠ·ΠΎΡˆΠ΅Π» ΠΎΠ±ΠΌΠ΅Π½, снова ΠΏΠ΅Ρ€Π΅Π±Π΅Ρ€ΠΈΡ‚Π΅ массив.
  • ΠœΡ‹ Π·Π½Π°Π΅ΠΌ, Ρ‡Ρ‚ΠΎ массив сортируСтся, ΠΊΠΎΠ³Π΄Π° Π½Π΅ ΠΏΡ€ΠΎΠΈΠ·ΠΎΡˆΠ»ΠΎ Π½ΠΈΠΊΠ°ΠΊΠΈΡ… пСрСстановок.

Визуализация ΠΊΠΎΠ½Ρ†Π΅ΠΏΡ†ΠΈΠΈ 2

Нам Π½ΡƒΠΆΠ΅Π½ Ρ‚ΠΎΠ»ΡŒΠΊΠΎ ΠΎΠ΄ΠΈΠ½ ΡƒΠΊΠ°Π·Π°Ρ‚Π΅Π»ΡŒ с этим ΠΌΠ΅Ρ‚ΠΎΠ΄ΠΎΠΌ, Ρ‚Π°ΠΊ ΠΊΠ°ΠΊ ΠΌΡ‹ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅ΠΌ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½ΡƒΡŽ для хранСния логичСского значСния, ΡƒΠΊΠ°Π·Ρ‹Π²Π°ΡŽΡ‰Π΅Π³ΠΎ, ΠΏΡ€ΠΎΠΈΠ·ΠΎΡˆΠ΅Π» Π»ΠΈ ΠΎΠ±ΠΌΠ΅Π½. Π’ ΠΎΡ‚Π»ΠΈΡ‡ΠΈΠ΅ ΠΎΡ‚ ΠΏΠ΅Ρ€Π²ΠΎΠΉ ΠΊΠΎΠ½Ρ†Π΅ΠΏΡ†ΠΈΠΈ, эта концСпция Ρ‚Ρ€Π΅Π±ΡƒΠ΅Ρ‚ ΠΎΡ‚ нас повторСния ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ элСмСнта Π² массивС ΠΊΠ°ΠΆΠ΄Ρ‹ΠΉ Ρ€Π°Π·, ΠΊΠΎΠ³Π΄Π° ΠΌΡ‹ ΠΏΡ€ΠΎΡ…ΠΎΠ΄ΠΈΠΌ Ρ‡Π΅Ρ€Π΅Π· Π½Π΅Π³ΠΎ.

function bubbleSortConcept2(arr) {
  let swapped;

  do {
    swapped = false;
    arr.forEach((item, index) => {
      if (item > arr[index + 1]) {
        // Save the value to a variable so we don't lose it
        let temp = item;
        arr[index] = arr[index + 1];
        arr[index + 1] = temp;
        swapped = true;
      }
    })
  } while (swapped);
  
  return arr;
}

Π—Π°ΠΊΠ»ΡŽΡ‡Π΅Π½ΠΈΠ΅

Bubble Sort - это ΠΎΠ΄ΠΈΠ½ ΠΈΠ· самых нСэффСктивных Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² сортировки. Π’ Ρ…ΡƒΠ΄ΡˆΠ΅ΠΌ случаС Π½Π°ΠΌ придСтся ΡΡ€Π°Π²Π½ΠΈΠ²Π°Ρ‚ΡŒ ΠΊΠ°ΠΆΠ΄Ρ‹ΠΉ элСмСнт с ΠΊΠ°ΠΆΠ΄Ρ‹ΠΌ Π΄Ρ€ΡƒΠ³ΠΈΠΌ элСмСнтом Π² массивС, ΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎ, ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° Π±ΡƒΠ΄Π΅Ρ‚ O(nΒ²).

Π§ΠΈΡ‚Π°Ρ‚ΡŒ Π΅Ρ‰Ρ‘:

← Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ event loop?

Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ event loop?

ΠŸΠΎΠ΄Π±ΠΎΡ€ΠΊΠ° подкастов ΠΎ Ρ„Ρ€ΠΎΠ½Ρ‚Π΅Π½Π΄Π΅ ΠΈ Π½Π΅ Ρ‚ΠΎΠ»ΡŒΠΊΠΎ β†’

ΠŸΠΎΠ΄Π±ΠΎΡ€ΠΊΠ° подкастов ΠΎ Ρ„Ρ€ΠΎΠ½Ρ‚Π΅Π½Π΄Π΅ ΠΈ Π½Π΅ Ρ‚ΠΎΠ»ΡŒΠΊΠΎ