Boblesortering i JavaScript

Boblesortering er en sorteringsalgoritme, hvor vi sammenligner hvert element i arrayet med det andet element i arrayet. Vi bytter de to elementer, hvis det første element er større end det andet element.

Her er et diagram over, hvordan det ser ud

Sortering af et array med 8 elementer

Algoritme

Start ved det første indeks i arrayet og sammenlign værdien ved det første indeks med værdien ved det næste indeks. For eksempel starter array ved 0, så vi sammenligner værdien ved indeks 0 med værdien ved indeks 1. Hvis værdien ved indeks 0 er større end indeks 1, så bytter vi værdierne ved indeks 0 med indeks 1.

Når byttet er gennemført, sammenligner vi værdien ved indeks 0 med værdien ved indeks 2 og bytter værdierne, hvis værdien ved indeks 0 er større end værdien ved indeks 2.

Ovenstående proces gentages, indtil vi har nået slutningen af ​​arrayet. Når vi når slutningen af ​​arrayet, starter vi igen ved indeks 1 og sammenligner værdien ved indeks 1 med værdi ved indeks 2, og vi bliver ved med at gentage denne proces, indtil vi har nået slutningen af ​​arrayet.

Hvad vi har brug for

Fra ovenstående beskrivelse har vi brug for en måde at sløjfe gennem hele arrayet. Vi kan bruge en for-løkke til denne opgave.

Det ser også ud til, at vi har brug for en anden løkke oven på ovennævnte løkke, som starter ved indeks 0 og fortsætter med at stige, indtil vi har nået slutningen af ​​arrayet. Det lyder som om dette er et job for en anden for loop.

Vi har brug for en funktion til at bytte to elementer i et array, og vi vil gøre dette ved hjælp af en midlertidig variabel.

Implementering

const swap = (arr, indexOne, indexTwo) => {
  const tempValue = arr[indexOne];
  arr[indexOne] = arr[indexTwo];
  arr[indexTwo] = tempValue;
};

const bubbleSort = (arr) => {
  for (let index = 0; index < arr.length; index++) {
    for (let innerIndex = index + 1; innerIndex < arr.length; innerIndex++) {
      if (arr[index] > arr[innerIndex]) {
        swap(arr, index, innerIndex);
      }
    }
  }
};

Den ydre for loop starter ved indeks 0 og den indre for loop starter ved indeks 1 og den indre for loop går gennem hele arrayet fra indeks 1 til længden af ​​arrayet - 1.

Indekset ved den ydre sløjfe flytter sig nu til 1, og det indre indeks starter ved indeks 2, og den indre sløjfe går gennem hele arrayet fra indeks 2 til længden af ​​arrayet - 1.

Hele processen gentages, indtil den ydre løkke er gået gennem hele arrayet, og til sidst har vi et sorteret array.

Optimeret algoritme

Lad os se, hvordan vi kan optimere ovenstående algoritme med et diagram

Fra ovenstående diagram sammenligner vi de to første tilstødende elementer og flytter det større tal til højre.

Vi starter altid med indeks 0 og indeks 0 + 1, og hvis elementet ved indeks 0 er større end ved indeks 0 + 1, så bytter vi elementerne. Vi sammenligner derefter indeks 1 med indeks 2 og så videre... når vi når slutningen af ​​arrayet vil det største tal være i slutningen af ​​arrayet.

Hvis vi har gået over arrayet én gang, vil vi have det største tal i højre ende af arrayet. Hvilket også betyder, at vi nu skal sortere n - 1 elementer, hvis n er længden af ​​arrayet. For eksempel, hvis arrayet har 8 elementer, som vi ser ovenfor, har vi 7 elementer at sortere.

Hver gang vi går over arrayet har vi et element mindre at sortere. Så hvis vi er gået af arrayet én gang, så skal vi sortere n - 1 elementer. Hvis vi har gået over arrayet to gange, skal vi sortere n - 2 elementer. Hvis vi er gået over arrayet tre gange, skal vi sortere n - 3 elementer... og så videre. På et tidspunkt vil n være 0, og vi har ingen elementer at sortere.

Hvad har vi brug for?

Som vi så tidligere, har vi brug for en variabel for at holde styr på den stadigt skiftende længde, hvilket betyder, at vi ikke kan bruge længdeegenskaben for arrayet, da det vil være en konstant. Så vi har brug for en variabel for at holde styr på længden af ​​arrayet. Lad os kalde denne variabel, elementsToSort. Vi fortsætter med at sløjfe over arrayet, så længe elementsToSort er større end 0.

Det kan være, at arrayet er sorteret og elementsToSort endnu ikke er 0, derfor kaldes swap-funktionen ikke én gang, når vi går gennem arrayet. Så vi har brug for en variabel til at fortælle os, om vi skal fortsætte eller ej. Lad os kalde denne variabel for keepGoing.

Vi har brug for en for-løkke, fordi vi skal gennemgå hele arrayet.

Vores diagram viste os også, at vi er nødt til at gå over arrayet flere gange, og det gør vi kun, hvis keepGoing-variablen er sat til sand. Så vi har brug for en do...while loop, fordi vi ønsker at loope mindst én gang for at kontrollere, om elementerne skal byttes eller ej.

Variabler med gode navne er nyttige.

Vi kan genbruge den samme swap-funktion, som vi så tidligere

Implementering

Lad os se på koden i JavaScript

const swap = (arr, indexOne, indexTwo) => {
  const tempValue = arr[indexOne];
  arr[indexOne] = arr[indexTwo];
  arr[indexTwo] = tempValue;
};

const bubbleSort = (arr) => {
  let elementsToSort = arr.length;
  let keepGoing = false;

  do {
    keepGoing = false;

    for (let index = 0; index < elementsToSort; index++) {
      if (arr[index] > arr[index + 1]) {
        swap(arr, index, index + 1);
        keepGoing = true;
      }
    }

    elementsToSort--;
  } while (keepGoing === true);
};

Boblesortering er ikke en ideel sorteringsalgoritme og er ikke god, når det kommer til ydeevne. I fremtiden vil vi se på andre algoritmer, som er bedre til at sortere arrays.

Koden, der ses i denne artikel, kan findes her, og jeg skal arbejde på mine diagrammer.