December 4, 2022

Robotic Notes

All technology News

A preview of a bubble sort in 41 lines of pure JavaScript

4 min read





Sorting algorithms put the elements of an array in a specific order.
Let’s use bubble sort to sort the numbers from lowest to highest by basically changing something like this:
[9, 1, 0, 4]

to this:
[0, 1, 4, 9].
The bubble sort algorithm is short and simple, but this comes at the cost of low efficiency – a perfect theme for a beginner coder!
Lower values ​​”rise” to the top if the array is displayed vertically – hence the name. In our case, the array is horizontal, so they “balloon to the left” instead.
To make things a little more exciting, we’ll assign a different color to each number and display the array after each pass.

One dimensional array version:

It looks weird because there are empty lines – we will add them later when we move to 2d version.


<html>
<body>
<canvas ID=”myCanvaswidth=”720height=”200“>canvas>
<scenario>
const canvas = document.getElementById(“myCanvas“);
const context = canvas.getContext(“2d”);
const shuffleLength = 1000;
const rowLength = 360;
const array=[]
for (I allow n = 0; n < rowLength; n++)
array[n] = n;
for (I allow n = 0; n < shuffleLength; n++)
I allow cell1 = mathematics.floor(mathematics.random() * rowLength);
I allow cell2 = mathematics.floor(mathematics.random() * rowLength);
I allow temp = array[cell1];
array[cell1] = array[cell2];
array[cell2] = temp;
function i come alive()
I allow exchanged = false;
for (I allow I = 1; I <= rowLength1; I++)
if (array[i – 1] > array[i])
I allow temp = array[i – 1];
array[i – 1] = array[i];
array[i] = temp;
exchanged = true;
for (I allow n = 0; n < rowLength; n++)
context.fillStyle = `hsl($array[n],100%,50%)`;
context.fillRect(n * 2, 0, 2, 50);
if (exchanged)
window.requestAnimationFrame(i come alive);
i come alive();
scenario>
body>
html>

Lines [1-6] set the HTML5 canvas we will use to display the array.

[8] number of times to shuffle items before sorting – randomly chosen

[9] the number of elements

[12] the sort array – empty for now

[13-14] fill the array with numbers: [0, 1, 2, 3…]

[20-26] Stir the array. Because of the way we populated the array [13-14], is already sorted. To see bubble sort in action, we need to destroy this row. To do this, we (pseudo) randomly select two elements and exchange their values. We repeat this process shuffleLength times.

[29-48] Actual sorting and visualization:

[30] We assume that no elements will need to be exchanged, which means that all elements are already sorted. If the algorithm proves us wrong on this point, we know another iteration is needed.

[33-40] The bubble sort algorithm
Now you know the terrible truth! This algorithm really only consists of 6 instructions! All this fuss about this little cycle! You probably regret getting to this page, but since you’re already here, you can finish reading:

[33] For items 1-360:

[34] If this element has a higher value than the previous one:

[35-38] swap items:
[35] copy the first element into the temp variable

[36] copy the second element into the first

[37] copy the temporary value into the second element

[38] Since we had to swap elements, our guess from [30] is no longer true.

[41-44] Visualization:

[41] For each element:

[42] Set the color to the value of
HSL (Hue-Saturation-Lightness) is a color representation method. We use it because for a sequence of numbers from 0 to 359 it creates a rainbow. So this is just a method to get an image (rainbow) without much code.

[43] Draw a 2x50px rectangle.

[46-47] If we’ve swapped the elements, the sort might be incomplete – let’s check by doing another pass.

Here’s what it looks like:


Click on the image to restart.

With just a few extra rows, we can sort a two-dimensional array so that we have multiple independent rows (which you saw at the top of this page):


<html>
<body>
<canvas ID=”myCanvaswidth=”720height=”200“>canvas>
<scenario>
const canvas = document.getElementById(“myCanvas“);
const context = canvas.getContext(“2d”);
const main array = [];
const shuffleLength = 1000;
const rowLength = 360;
for (I allow row = 0; row < 90; row++)
const array=[]
for (I allow n = 0; n < rowLength; n++)
array[n] = n;
main array[row] = array;
for (I allow row = 0; row < 90; row++)
I allow array = main array[row];
for (I allow n = 0; n < shuffleLength; n++)
I allow cell1 = mathematics.floor(mathematics.random() * rowLength);
I allow cell2 = mathematics.floor(mathematics.random() * rowLength);
I allow temp = array[cell1];
array[cell1] = array[cell2];
array[cell2] = temp;
function i come alive()
I allow exchanged = false;
for (I allow row = 0; row < 90; row++)
I allow array = main array[row];
for (I allow I = 1; I <= rowLength1; I++)
if (array[i – 1] > array[i])
I allow temp = array[i – 1];
array[i – 1] = array[i];
array[i] = temp;
exchanged = true;
for (I allow n = 0; n < rowLength; n++)
context.fillStyle = `hsl($array[n],100%,50%)`;
context.fillRect(n * 2, row * 2, 2, 2);
if (exchanged)
window.requestAnimationFrame(i come alive);
i come alive();
scenario>
body>
html>

We added a two-dimensional mainArray [7]. What was the array in the previous version is now an element in mainArray: [15, 19, 32].
Now we need to repeat all the actions for each row: [11, 18, 31].
Now we draw 2×2 pixel squares [42].

Enjoy the bubbles!

Check out these programming tutorials:

JavaScript:

Goldmine – inactive game (~200 lines)

Tunnel running game (~170 lines)

Game “Tower” (84 lines)

Optical Illusion (18 lines)

Rotating Squares – Visual Effect (25 rows)

Oldschool fire effect (20 lines)

Fireworks (60 lines)

Animated Fractal (32 rows)

Physics engine for beginners

Physics engine – interactive sandbox

Physical engine – stupid contraption

Starfield (21 lines)

Yin Yang with a twist (4 circles and 20 lines)

Tiled Map Editor (70 rows)

Sinusoidal scroller (30 lines)

Interactive animated sprites

Image transition effect (16 rows)

Your first JavaScript program: you need 5 minutes and a notebook

Fractals in Excel

Python in Blender 3d:

Domino effect (10 rows)

Wrecking Ball Effect (14 rows)

3d fractal in Blender Python



Source link