Buborékrendezés vizualizáció

A rendezési algoritmusok egy tömb elemeit meghatározott sorrendbe állítják.
Használjuk a buborékrendezést a számok növekvő sorrendbe állításához, lényegében így változtatva meg a sorrendet:
[9, 1, 0, 4]
erre:
[0, 1, 4, 9].
A buborékrendezés algoritmusa rövid és egyszerű, de ennek ára az alacsony hatékonyság – ideális téma egy kezdő programozónak!
A kisebb értékek 'felbuborékolnak' a tetejére, ha a tömböt függőlegesen jelenítjük meg – innen ered az elnevezés. Esetünkben a tömb vízszintes, így inkább 'balra buborékolnak'.
Hogy izgalmasabbá tegyük a dolgokat, minden számhoz más színt rendelünk, és minden menet után megjelenítjük a tömböt.

Egydimenziós tömb verzió:

Kicsit furcsán néz ki, mert van benne néhány üres sor – ezeket később adjuk hozzá, amikor áttérünk a 2D verzióra.

<html>

<body>

const canvas = document.getElementById("myCanvas");

const context = canvas.getContext("2d");

const shuffleLength = 1000;

const rowLength = 360;

const array=[]

for (let n = 0; n < rowLength; n++)

array[n] = n;

for (let n = 0; n < shuffleLength; n++) {

let cell1 = Math.floor(Math.random() * rowLength);

let cell2 = Math.floor(Math.random() * rowLength);

let temp = array[cell1];

array[cell1] = array[cell2];

array[cell2] = temp;

}

function animate() {

let swapped = false;

for (let i = 1; i <= rowLength - 1; i++) {

if (array[i - 1] > array[i]) {

let temp = array[i - 1];

array[i - 1] = array[i];

array[i] = temp;

swapped = true;

}

for (let n = 0; n < rowLength; n++) {

context.fillStyle = `hsl(${array[n]},100%,50%)`;

context.fillRect(n * 2, 0, 2, 50);

}

if (swapped)

window.requestAnimationFrame(animate);

}

animate();

</script>

</body>

</html>

Az [1-6] sorok beállítják a HTML5 Vásznat (Canvas), amelyet a tömb megjelenítésére használunk.
[8] hányszor keverjük össze az elemeket a rendezés előtt – tetszőlegesen választva
[9] az elemek száma
[12] a rendezendő tömb – egyelőre üres
[13-14] a tömb feltöltése számokkal: [0, 1, 2, 3...]
[20-26] A tömb összekeverése. Mivel a [13-14] sorokban töltöttük fel a tömböt, az már rendezett. Ahhoz, hogy működés közben lássuk a buborékrendezést, meg kell szüntetnünk ezt a rendet. Ehhez (pszeudo-)véletlenszerűen kiválasztunk két elemet, és kicseréljük az értékeiket. Ezt a folyamatot a shuffleLength változóban megadott alkalommal ismételjük.
[29-48] Tényleges rendezés és vizualizáció:
[30] Feltételezzük, hogy egyetlen elemet sem kell kicserélni, ami azt jelenti, hogy az összes elem már rendezett. Ha az algoritmus rácáfol erre, tudjuk, hogy újabb iterációra van szükség.

[33-40] A Buborékrendezés Algoritmus
Most már tudod a szörnyű igazságot! Ez az algoritmus valójában mindössze 6 utasításból áll! A nagy felhajtás emiatt az egyetlen kis ciklus miatt! Valószínűleg megbántad, hogy erre az oldalra navigáltál, de ha már itt vagy, akár végig is olvashatod:
[33] Az 1-360. elemekre:
[34] Ha ennek az elemnek nagyobb az értéke, mint az előzőnek:
[35-38] elemek cseréje: [35] az első elem másolása a temp (ideiglenes) változóba
[36] a második elem másolása az első helyére
[37] az ideiglenes érték másolása a második elem helyére
[38] Mivel elemeket kellett cserélnünk, a [30]-as feltételezésünk már nem igaz.

[41-44] Vizualizáció:
[41] Minden elemre:
[42] A szín beállítása az érték alapján
A HSL (Hue-Saturation-Lightness / Árnyalat-Telítettség-Fényerő) egy színábrázolási módszer. Azért használjuk, mert a 0-tól 359-ig terjedő számsorozatra szivárványt hoz létre. Tehát ez csak egy módszer arra, hogy sok kód nélkül kapjunk egy képet (egy szivárványt).
[43] Egy 2x50 pixeles téglalap rajzolása.
[46-47] Ha cseréltünk elemeket, a rendezés lehet, hogy még nem teljes – ellenőrizzük egy újabb menet futtatásával.

Így néz ki:

Kattintson a képre az újraindításhoz.

Pár további sorral rendezhetünk egy kétdimenziós tömböt is, így több független sorunk lesz (amit az oldal tetején láthatott):

<html>

<body>

const canvas = document.getElementById("myCanvas");

const context = canvas.getContext("2d");

const mainArray = [];

const shuffleLength = 1000;

const rowLength = 360;

for (let row = 0; row < 90; row++) {

const array=[]

for (let n = 0; n < rowLength; n++)

array[n] = n;

mainArray[row] = array;

}

for (let row = 0; row < 90; row++) {

let array = mainArray[row];

for (let n = 0; n < shuffleLength; n++) {

let cell1 = Math.floor(Math.random() * rowLength);

let cell2 = Math.floor(Math.random() * rowLength);

let temp = array[cell1];

array[cell1] = array[cell2];

array[cell2] = temp;

}

function animate() {

let swapped = false;

for (let row = 0; row < 90; row++) {

let array = mainArray[row];

for (let i = 1; i <= rowLength - 1; i++) {

if (array[i - 1] > array[i]) {

let temp = array[i - 1];

array[i - 1] = array[i];

array[i] = temp;

swapped = true;

}

for (let n = 0; n < rowLength; n++) {

context.fillStyle = `hsl(${array[n]},100%,50%)`;

context.fillRect(n * 2, row * 2, 2, 2);

}

if (swapped)

window.requestAnimationFrame(animate);

}

animate();

</script>

</body>

</html>

Hozzáadtunk egy kétdimenziós mainArray-t [7]. Ami az előző verzióban a tömb volt, most a mainArray egy eleme: [15, 19, 32].
Most meg kell ismételnünk az összes műveletet minden sorra: [11, 18, 31].
A [42]-es sorban most 2x2 pixeles négyzeteket rajzolunk.

Jó szórakozást a buborékokhoz!