preface

Hello, I’m Lin Sanxin. There is a reason for writing this article. By chance, I saw a visual video of Java’s 50 sorting algorithms, but the video did not give a specific implementation tutorial, so I thought that I could use JavaScript + Canvas to achieve this cool effect. The animation effect of each sorting algorithm is basically different. For example, bubble sort looks like this

Implementation approach

The effect you want to achieve

As you can see from the cover, each algorithm starts with the first image and ends up looking like the second

Polar coordinates

Before talking about the realization of ideas, I will review a high school knowledge for you — polar coordinates. Haha, I wonder how many people still remember him?

  • O: The pole, the origin
  • Rho: diameter
  • θ : Angle between the polar diameter and the X-axis
  • X = ρ * cos thetaBecause theX / ρ = cosθ
  • Y = ρ * sinθBecause theY / ρ = sinθ

What does the result that we want to achieve have to do with polar coordinates? Well, it does matter, let’s say I have a sorted array, and it has 37 elements, and we can convert those 37 elements into 37 points in polar coordinates. How do we do that?

const arr = [
    0.1.2.3.4.5.6.7.8.9.10.11.12.13.14.15.16.17.18.19.20.21.22.23.24.25.26.27.28.29.30.31.32.33.34.35.36
]
Copy the code

We can go like this:

  • Element index * 10 -> Angle θ(Why do I multiply by 10, because I want to make 360 degrees?)
  • The value arr[index] -> polar diameter ρ

If we follow the above rules, we can get 37 points in polar coordinates (on canvas the Y axis is from top to bottom, and the following graph is also on canvas, but I still draw the Y axis in the normal direction, so the graph is actually inverted, but there is a reason for that) :

(0- > theta =00°, rho =0) (1- > theta =10°, rho =1) (2- > theta =20°, rho =2) (3- > theta =30°, rho =3)
(4- > theta =40°, rho =4) (5- > theta =50°, rho =5) (6- > theta =60°, rho =6) (7- > theta =70°, rho =7)
(8- > theta =80°, rho =8) (9- > theta =90°, rho =9) (10- > theta =100°, rho =10) (11- > theta =110°, rho =11)
(12- > theta =120°, rho =12) (13- > theta =130°, rho =13) (14- > theta =140°, rho =14) (15- > theta =150°, rho =15) 
(16- > theta =160°, rho =16) (17- > theta =170°, rho =17) (18- > theta =180°, rho =18) (19- > theta =190°, rho =19)
(20- > theta =200°, rho =20) (21- > theta =210°, rho =21) (22- > theta =220°, rho =22) (23- > theta =230°, rho =23) 
(24- > theta =240°, rho =24) (25- > theta =250°, rho =25) (26- > theta =260°, rho =26) (27- > theta =270°, rho =27)
(28- > theta =280°, rho =28) (29- > theta =290°, rho =29) (30- > theta =300°, rho =30) (31- > theta =310°, rho =31)
(32- > theta =320°, rho =32) (33- > theta =330°, rho =33) (34- > theta =340°, rho =34) (35- > theta =350°, rho =35) 
(36- > theta =360°, rho =36)
Copy the code

Do you see any similarities to the trajectory of what we want to achieve in the end?

Randomly scattered

So with that out of the way, let’s think about how do we start by breaking up the elements of the array in polar coordinates? Well, it’s really easy. We can generate an out-of-order array, like

const arr = [
    25.8.32.1.19.14.0.29.17.6.7.26.3.30.31.16.28.15.24.10.21.2.9.4.35.5.36.33.11.27.34.22.13.18.23.12.20
]
Copy the code

And then, using the same rule, convert polar coordinates

  • Element index * 10 -> Angle θ(Why do I multiply by 10, because I want to make 360 degrees?)
  • The value arr[index] -> polar diameter ρ

So we can get to these 37 points, and we can naturally achieve the effect of fragmentation

(25- > theta =00°, rho =25) (8- > theta =10°, rho =8) (32- > theta =20°, rho =32) (1- > theta =30°, rho =1)
(19- > theta =40°, rho =19) (14- > theta =50°, rho =14) (0- > theta =60°, rho =0) (29- > theta =70°, rho =29)
(17- > theta =80°, rho =17) (6- > theta =90°, rho =6) (7- > theta =100°, rho =7) (26- > theta =110°, rho =26)
(3- > theta =120°, rho =3) (30- > theta =130°, rho =30) (31- > theta =140°, rho =31) (16- > theta =150°, rho =16)
(28- > theta =160°, rho =28) (15- > theta =170°, rho =15) (24- > theta =180°, rho =24) (10- > theta =190°, rho =10)
(21- > theta =200°, rho =21) (2- > theta =210°, rho =2) (9- > theta =220°, rho =9) (4- > theta =230°, rho =4)
(35- > theta =240°, rho =35) (5- > theta =250°, rho =5) (36- > theta =260°, rho =36) (33- > theta =270°, rho =33)
(11- > theta =280°, rho =11) (27- > theta =290°, rho =27) (34- > theta =300°, rho =34) (22- > theta =310°, rho =22)
(13- > theta =320°, rho =13) (18- > theta =330°, rho =18) (23- > theta =340°, rho =23) (12- > theta =350°, rho =12)
(20- > theta =360°, rho =20)
Copy the code

Implementation effect

To sum up, we want to achieve the effect, there is a train of thought

  • 1, Mr. OneDisorderly ordinal group
  • 2. Use canvas to draw thisDisorderly ordinal groupFor all the elementsThe polar point
  • 3,Disorderly ordinal groupforThe sorting
  • 4. Sorting processKeep emptying the canvasAnd,redrawThe points corresponding to the polar coordinates of all the elements of the array
  • 5. Terminate the canvas operation until the sorting is complete

Do it!!

We must do things in order, remember the steps above?

  • 1, Mr. OneDisorderly ordinal group
  • 2. Use canvas to draw thisDisorderly ordinal groupFor all the elementsThe polar point
  • 3,Disorderly ordinal groupforThe sorting
  • 4. Sorting processKeep emptying the canvasAnd,redrawThe points corresponding to the polar coordinates of all the elements of the array
  • 5. Terminate the canvas operation until the sorting is complete

Let’s follow this step, step by step to achieve the effect, brothers, go!!

Generate random ordinal groups

My nums is an ordered array from 0 to 179, then I scramble it and stuff it into the array NUMs. I do this 4 times. Why is it 0 minus 179, because 0 minus 179 has exactly 180 numbers

As a programmer, THERE is no way I can type so many elements by hand. To.. In the code

let nums = []
for (let i = 0; i < 4; i++) {
    // Generate an ordered array from 0 to 179
    const arr = [...Array(180).keys()] // array.keys (
    const res = []
    while (arr.length) {
        / / upset
        const randomIndex = Math.random() * arr.length - 1
        res.push(arr.splice(randomIndex, 1) [0])
    }
    nums = [...nums, ...res]
}
Copy the code

After the above operation, I have 4 * 180 = 720 elements in numS, and the elements in NUMS are in the range 0 to 179

Canvas draws scrambled Ordinal Numbers

Before drawing canvas, you must write a canvas node on the HTML page. Here, I set the width to 1000, the height to 1000, and the background color to black

<canvas id="canvas" width="1000" height="1000" style="background: #000;"></canvas>
Copy the code

As seen above, the pole (origin) is in the middle of the coordinate, but the original origin of canvas is in the upper left corner of the canvas. We need to move the origin of canvas to the center of the canvas. What is the coordinate of the center? Remember when we were 1,000 by 1,000? If the canvas center is (500, 500), we can use the canvas ctx.translate(500, 500) to move the center. Since the dots we draw are all white, let’s incidentally set ctx.fillStyle to white

One thing to notice is that the Y axis in the canvas goes from top to bottom, as opposed to the normal Y axis.

const canvas = document.getElementById('canvas')
const ctx = canvas.getContext('2d')
ctx.fillStyle = 'white' // Set the color of the drawing
ctx.translate(500.500) // Move center point to (500, 500)
Copy the code

So how do I draw the dots? It’s not enough to calculate the Angle θ and the polar diameter ρ, because the Canvas doesn’t recognize these two things. What does Canvas know? He only knows (x, y), so we just need to calculate (x, y) by Angle θ and polar diameter ρ. Remember the formula of polar coordinates

  • X = ρ * cos thetaBecause theX / ρ = cosθ
  • Y = ρ * sinθBecause theY / ρ = sinθ

Since we’re laying out a scatter point, we’re laying out a circle, so the Angle of a circle is 0 degrees minus 360 degrees, but we don’t want 360 degrees, we just want 0 degrees minus 359 degrees, because 0 degrees and 360 degrees are the same line. One degree on a line is enough for us. So let’s figure out the cosine theta and the sine theta for each Angle of 0 minus 359 degrees.

const CosandSin = []
for (let i = 0; i < 360; i++) {
    const jiaodu = i / 180 * Math.PI
    CosandSin.push({ cos: Math.cos(jiaodu), sin: Math.sin(jiaodu) })
}
Copy the code

There are only 360 integer angles between 0° and 359° on a circle, but numS has 720 elements. How to allocate canvas? That’s easy. If I put 2 elements on one Angle, that’s exactly 2 times 360 is 720

All right, let’s cut to the chase and draw the initial scatter. We also know that we need to draw 720 points, and we’re going to have to use a lot of object-oriented programming for this kind of multiple identical things

// a single rectangle constructor
function Rect(x, y, width, height) {
    this.x = x / / coordinates x
    this.y = y / / y coordinate
    this.width = width // The width of the rectangle
    this.height = height // Rectangle height
}

// Render a single rectangle
Rect.prototype.draw = function () {
    ctx.beginPath() // Start drawing one
    ctx.fillRect(this.x, this.y, this.width, this.height) / / draw a
    ctx.closePath() // Finish drawing one
}

const CosandSin = []
for (let i = 0; i < 360; i++) {
    const jiaodu = i / 180 * Math.PI
    CosandSin.push({ cos: Math.cos(jiaodu), sin: Math.sin(jiaodu) })
}

function drawAll(arr) {
    const rects = [] // Store 720 rectangles
    for (let i = 0; i < arr.length; i++) {
        const num = arr[i]
        const { cos, sin } = CosandSin[Math.floor(i / 2)] // Draw two in each corner
        const x = num * cos // x = ρ * cosθ
        const y = num * sin // y = ρ * sinθ
        rects.push(new Rect(x, y, 5.3)) // Collect all rectangles
    }
    rects.forEach(rect= > rect.draw()) // iterate over the render
}
drawAll(nums) // Execute the render function
Copy the code

Check it out on the page. The initial scatter rendering is now complete

I’m redrawing as I sort

In fact, it is very simple, just sort once, empty the canvas, and then re-execute the above rendering function drawAll. For performance reasons, I wrapped drawAll as a Promise function

function drawAll(arr) {
    return new Promise((resolve) = > {
        setTimeout(() = > {
            ctx.clearRect(-500, -500.1000.1000) // Empty the canvas
            const rects = [] // Store 720 rectangles
            for (let i = 0; i < arr.length; i++) {
                const num = arr[i]
                const { cos, sin } = CosandSin[Math.floor(i / 2)] // Draw two in each corner
                const x = num * cos // x = ρ * cosθ
                const y = num * sin // y = ρ * sinθ
                rects.push(new Rect(x, y, 5.3)) // Collect all rectangles
            }
            rects.forEach(rect= > rect.draw()) // iterate over the render
            resolve('draw success')},10)})}Copy the code

And then let’s do an example of a sort algorithm, let’s do a bubble sort

async function bubbleSort(arr) {
    var len = arr.length;
    for (var i = 0; i < len; i++) {
        for (var j = 0; j < len - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {        // Compare adjacent elements in pairs
                var temp = arr[j + 1];        // Element swap
                arr[j + 1] = arr[j]; arr[j] = temp; }}await drawAll(arr) // Redraw while sorting
    }
    return arr;
}
Copy the code

Then place a button on the page that performs the start sort

<button id="btn"</button>document.getElementById('btn').onclick = function () {
    bubbleSort(nums)
}
Copy the code

The effect is as follows, is not very happy ha ha ha!!

The complete code

This is the complete code

<canvas id="canvas" width="1000" height="1000" style="background: #000;"></canvas>
<button id="btn">Start sorting</button>
Copy the code
const canvas = document.getElementById('canvas')
const ctx = canvas.getContext('2d')
ctx.fillStyle = 'white' // Set the color of the drawing
ctx.translate(500.500) // Move center point to (500, 500)

let nums = []
for (let i = 0; i < 4; i++) {
    // Generate an ordered array from 0 to 180
    const arr = [...Array(180).keys()]
    const res = []
    while (arr.length) {
        / / upset
        const randomIndex = Math.random() * arr.length - 1
        res.push(arr.splice(randomIndex, 1) [0])
    }
    nums = [...nums, ...res]
}

// a single rectangle constructor
function Rect(x, y, width, height) {
    this.x = x / / coordinates x
    this.y = y / / y coordinate
    this.width = width // The width of the rectangle
    this.height = height // Rectangle height
}

// Render a single rectangle
Rect.prototype.draw = function () {
    ctx.beginPath() // Start drawing one
    ctx.fillRect(this.x, this.y, this.width, this.height) / / draw a
    ctx.closePath() // Finish drawing one
}

const CosandSin = []
for (let i = 0; i < 360; i++) {
    const jiaodu = i / 180 * Math.PI
    CosandSin.push({ cos: Math.cos(jiaodu), sin: Math.sin(jiaodu) })
}

function drawAll(arr) {
    return new Promise((resolve) = > {
        setTimeout(() = > {
            ctx.clearRect(-500, -500.1000.1000) // Empty the canvas
            const rects = [] // Store 720 rectangles
            for (let i = 0; i < arr.length; i++) {
                const num = arr[i]
                const { cos, sin } = CosandSin[Math.floor(i / 2)] // Draw two in each corner
                const x = num * cos // x = ρ * cosθ
                const y = num * sin // y = ρ * sinθ
                rects.push(new Rect(x, y, 5.3)) // Collect all rectangles
            }
            rects.forEach(rect= > rect.draw()) // iterate over the render
            resolve('draw success')},10)
    })
}
drawAll(nums) // Execute the render function

async function bubbleSort(arr) {
    var len = arr.length;
    for (var i = 0; i < len; i++) {
        for (var j = 0; j < len - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {        // Compare adjacent elements in pairs
                var temp = arr[j + 1];        // Element swap
                arr[j + 1] = arr[j]; arr[j] = temp; }}await drawAll(arr) // Redraw while sorting
    }
    return arr;
}

document.getElementById('btn').onclick = function () {
    bubbleSort(nums) // Click Execute
}
Copy the code

Here we go!!

First of all, haha

  • I’m algorithmic scum
  • Each algorithm sort, the animation is different
  • DrawAll can also have different effects depending on where it is placed

Bubble sort

async function bubbleSort(arr) {
    var len = arr.length;
    for (var i = 0; i < len; i++) {
        for (var j = 0; j < len - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {        // Compare adjacent elements in pairs
                var temp = arr[j + 1];        // Element swap
                arr[j + 1] = arr[j]; arr[j] = temp; }}await drawAll(arr) // Redraw while sorting
    }
    return arr;
}

document.getElementById('btn').onclick = function () {
    bubbleSort(nums) // Click Execute
}
Copy the code

Selection sort

async function selectionSort(arr) {
    var len = arr.length;
    var minIndex, temp;
    for (var i = 0; i < len - 1; i++) {
        minIndex = i;
        for (var j = i + 1; j < len; j++) {
            if (arr[j] < arr[minIndex]) {     // Find the smallest number
                minIndex = j;                 // Save the smallest index
            }
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
        await drawAll(arr)
    }
    return arr;
}
document.getElementById('btn').onclick = function () {
    selectionSort(nums)
}
Copy the code

Insertion sort

async function insertionSort(arr) {
    if (Object.prototype.toString.call(arr).slice(8, -1) = = ='Array') {
        for (var i = 1; i < arr.length; i++) {
            var key = arr[i];
            var j = i - 1;
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
            await drawAll(arr)
        }
        return arr;
    } else {
        return 'arr is not an Array! '; }}document.getElementById('btn').onclick = function () {
    insertionSort(nums)
}
Copy the code

Heap sort

async function heapSort(array) {
    if (Object.prototype.toString.call(array).slice(8, -1) = = ='Array') {
        / / build the heap
        var heapSize = array.length, temp;
        for (var i = Math.floor(heapSize / 2) - 1; i >= 0; i--) {
            heapify(array, i, heapSize);
            await drawAll(array)
        }

        / / heap sort
        for (var j = heapSize - 1; j >= 1; j--) {
            temp = array[0];
            array[0] = array[j];
            array[j] = temp;
            heapify(array, 0, --heapSize);
            await drawAll(array)
        }
        return array;
    } else {
        return 'array is not an Array! '; }}function heapify(arr, x, len) {
    if (Object.prototype.toString.call(arr).slice(8, -1) = = ='Array' && typeof x === 'number') {
        var l = 2 * x + 1, r = 2 * x + 2, largest = x, temp;
        if (l < len && arr[l] > arr[largest]) {
            largest = l;
        }
        if (r < len && arr[r] > arr[largest]) {
            largest = r;
        }
        if (largest != x) {
            temp = arr[x];
            arr[x] = arr[largest];
            arr[largest] = temp;
            heapify(arr, largest, len);
        }
    } else {
        return 'arr is not an Array or x is not a number! '; }}document.getElementById('btn').onclick = function () {
    heapSort(nums)
}
Copy the code

Quick sort

async function quickSort(array, left, right) {
    drawAll(nums)
    if (Object.prototype.toString.call(array).slice(8, -1) = = ='Array' && typeof left === 'number' && typeof right === 'number') {
        if (left < right) {
            var x = array[right], i = left - 1, temp;
            for (var j = left; j <= right; j++) {
                if(array[j] <= x) { i++; temp = array[i]; array[i] = array[j]; array[j] = temp; }}await drawAll(nums)
            await quickSort(array, left, i - 1);
            await quickSort(array, i + 1, right);
            await drawAll(nums)
        }
        return array;
    } else {
        return 'array is not an Array or left or right is not a number! '; }}document.getElementById('btn').onclick = function () {
    quickSort(nums, 0, nums.length - 1)}Copy the code

Radix sort

async function radixSort(arr, maxDigit) {
    var mod = 10;
    var dev = 1;
    var counter = [];
    for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
        for (var j = 0; j < arr.length; j++) {
            var bucket = parseInt((arr[j] % mod) / dev);
            if (counter[bucket] == null) {
                counter[bucket] = [];
            }
            counter[bucket].push(arr[j]);
        }
        var pos = 0;
        for (var j = 0; j < counter.length; j++) {
            var value = null;
            if(counter[j] ! =null) {
                while((value = counter[j].shift()) ! =null) {
                    arr[pos++] = value;
                    await drawAll(arr)
                }
            }
        }
    }
    return arr;
}
document.getElementById('btn').onclick = function () {
    radixSort(nums, 3)}Copy the code

Hill sorting

async function shellSort(arr) {
    var len = arr.length,
        temp,
        gap = 1;
    while (gap < len / 5) {          // Dynamically define interval sequences
        gap = gap * 5 + 1;
    }
    for (gap; gap > 0; gap = Math.floor(gap / 5)) {
        for (var i = gap; i < len; i++) {
            temp = arr[i];
            for (var j = i - gap; j >= 0 && arr[j] > temp; j -= gap) {
                arr[j + gap] = arr[j];
            }
            arr[j + gap] = temp;
            await drawAll(arr)
        }
    }
    return arr;
}
document.getElementById('btn').onclick = function () {
    shellSort(nums)
}

Copy the code

reference

  • Sorting algorithm Reference: Ten classic sorting algorithm summary (JavaScript description)

conclusion

If you think this article is a little bit helpful to you, click a like and encourage Lin Sanxin haha. Or you can join my shoal of fish to get into the learning group, shoal of fish, click here to fish