Introduction
We all have implemented some sorting algorithm in school or maybe at work. We all have also learned the differences between these algorithms in terms of their time complexity, but most of us have never visualized the working of these algorithms. In this post will try to visualize the working to two sorting algorithms using react.
Lets get coding
First we will implement the 2 algorithms. We will use in place sorting.
- Bubble sort O(n^2)
- Merge sort O(log n)
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
// Inplace buble sort
function bublesort(arr) {
setsortButton(true);
for (let i = 1; i < arr.length; i++) {
let oneSwap = false;
for (let j = 0; j < arr.length - i; j++) {
if (arr[j] > arr[j + 1]) {
oneSwap = true;
let tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
if (oneSwap === false) break;
}
return;
}
// Inplace Implementation merge sort
function merge(arr, start, mid, end) {
let start2 = parseInt(mid + 1);
// If the direct merge is already sorted
if (arr[mid] <= arr[start2]) {
return;
}
// Two pointers to maintain start
// of both arrays to merge
while (start <= mid && start2 <= end) {
// If element 1 is in right place
if (arr[start] <= arr[start2]) {
start++;
} else {
let value = arr[start2];
let index = start2;
// Shift all the elements between element 1
// element 2, right by 1.
while (index > start) {
arr[index] = arr[index - 1];
index--;
}
arr[start] = value;
// Update all the pointers
start++;
mid++;
start2++;
}
}
}
/* l is for left index and r is right index of the
sub-array of arr to be sorted */
function mergeSort(arr, l, r) {
if (l < r) {
// Same as (l + r) / 2, but avoids overflow
// for large l and r
let m = parseInt(l + (r - l) / 2);
// Sort first and second halves
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
Next we will setup out react app with states and ref.
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
export default function App() {
// to store our array
const [randArr, setRandArr] = useState(null);
// which indices we are comparing
const [compIdx, setCompIdx] = useState([]);
// to disable sort button
const [sortButton, setsortButton] = useState(false);
// to store Raf object
const rafRef = useRef();
return (
<div className="App">
<div className="num-container">
{randArr &&
randArr.map((n, i) => (
<div
className="num"
style=
key={i}
>
{n}
</div>
))}
</div>
<button
disabled={sortButton}
onClick={(e) => mergeSort(randArr, 0, randArr.length - 1)}
>
Sort
</button>
</div>
);
}
When our component mounts we want to initialize it with random array. To accompolish this task we will introduce useEffect hook.
1
2
3
4
5
6
7
useEffect(() => {
setRandArr(
Array.from({ length: getRandomInt(5, 50) }, (_) => getRandomInt(3, 100))
);
}, []);//Empty dependency makes sure that is runs only on mount
Next the animate the comparisons we will use requestAnimationFrame api. we will set our compIdx when we are comparing two indices and to make sure that our browser gets chance to paint the indices we will wait for some time after that. We will use settimeout to wait.
Below are the following code snippets
1
2
3
4
5
6
7
8
9
10
11
12
13
14
//wait function
function wait(ms) {
return new Promise((resolve) => setTimeout(resolve, ms));
}
// setting cmpIdx
rafRef.current = window.requestAnimationFrame(() => {
setCompIdx([j, j + 1]);
});
await wait(50);
}
Using above two snippets we implement out merge sort and bubble sort. We need to implement async version because we do not want it to be blocking and want out viewer to see the changes.
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
async function bublesort(arr) {
setsortButton(true);
for (let i = 1; i < arr.length; i++) {
let oneSwap = false;
for (let j = 0; j < arr.length - i; j++) {
if (arr[j] > arr[j + 1]) {
oneSwap = true;
let tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
rafRef.current = window.requestAnimationFrame(() => {
setCompIdx([j, j + 1]);
});
await wait(50);
}
}
if (oneSwap === false) break;
}
return;
}
// Inplace Implementation
async function merge(arr, start, mid, end) {
let start2 = Math.floor(mid + 1);
// If the direct merge is already sorted
rafRef.current = window.requestAnimationFrame(() => {
setCompIdx([mid, start2]);
});
await wait(50);
if (arr[mid] <= arr[start2]) {
return;
}
// Two pointers to maintain start
// of both arrays to merge
while (start <= mid && start2 <= end) {
// If element 1 is in right place
rafRef.current = window.requestAnimationFrame(() => {
setCompIdx([start, start2]);
});
await wait(50);
if (arr[start] <= arr[start2]) {
start++;
} else {
let value = arr[start2];
let index = start2;
// Shift all the elements between element 1
// element 2, right by 1.
while (index > start) {
rafRef.current = window.requestAnimationFrame(() => {
setCompIdx([index, start]);
});
await wait(50);
arr[index] = arr[index - 1];
index--;
}
arr[start] = value;
// Update all the pointers
start++;
mid++;
start2++;
}
}
}
/* l is for left index and r is right index of the
sub-array of arr to be sorted */
async function mergeSort(arr, l, r) {
if (l < r) {
// Same as (l + r) / 2, but avoids overflow
// for large l and r
let m = Math.floor(l + (r - l) / 2);
// Sort first and second halves
await mergeSort(arr, l, m);
await mergeSort(arr, m + 1, r);
await merge(arr, l, m, r);
}
}
Finally we need to clear the animation frame on component unmount. Again we will need useEffect hook
1
2
3
4
5
6
7
useEffect(() => {
return () => {
if (rafRef.current) window.cancelAnimationFrame(rafRef.current);
};
}, []);
Final Code
Here is our final code
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
import React, { useEffect, useState, useRef } from "react";
import "./styles.css";
function getRandomInt(min, max) {
min = Math.ceil(min);
max = Math.floor(max);
return Math.floor(Math.random() * (max - min + 1)) + min;
}
function wait(ms) {
return new Promise((resolve) => setTimeout(resolve, ms));
}
export default function App() {
const [randArr, setRandArr] = useState(null);
const [compIdx, setCompIdx] = useState([]);
const [sortButton, setsortButton] = useState(false);
const rafRef = useRef();
useEffect(() => {
console.log("running once");
setRandArr(
Array.from({ length: getRandomInt(5, 50) }, (_) => getRandomInt(3, 100))
);
}, []);
useEffect(() => {
return () => {
if (rafRef.current) window.cancelAnimationFrame(rafRef.current);
};
}, []);
async function bublesort(arr) {
setsortButton(true);
for (let i = 1; i < arr.length; i++) {
let oneSwap = false;
for (let j = 0; j < arr.length - i; j++) {
if (arr[j] > arr[j + 1]) {
oneSwap = true;
let tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
rafRef.current = window.requestAnimationFrame(() => {
setCompIdx([j, j + 1]);
});
await wait(50);
}
}
if (oneSwap === false) break;
}
return;
}
// Inplace Implementation
async function merge(arr, start, mid, end) {
let start2 = Math.floor(mid + 1);
// If the direct merge is already sorted
rafRef.current = window.requestAnimationFrame(() => {
setCompIdx([mid, start2]);
});
await wait(50);
if (arr[mid] <= arr[start2]) {
return;
}
// Two pointers to maintain start
// of both arrays to merge
while (start <= mid && start2 <= end) {
// If element 1 is in right place
rafRef.current = window.requestAnimationFrame(() => {
setCompIdx([start, start2]);
});
await wait(50);
if (arr[start] <= arr[start2]) {
start++;
} else {
let value = arr[start2];
let index = start2;
// Shift all the elements between element 1
// element 2, right by 1.
while (index > start) {
rafRef.current = window.requestAnimationFrame(() => {
setCompIdx([index, start]);
});
await wait(50);
arr[index] = arr[index - 1];
index--;
}
arr[start] = value;
// Update all the pointers
start++;
mid++;
start2++;
}
}
}
/* l is for left index and r is right index of the
sub-array of arr to be sorted */
async function mergeSort(arr, l, r) {
if (l < r) {
// Same as (l + r) / 2, but avoids overflow
// for large l and r
let m = Math.floor(l + (r - l) / 2);
// Sort first and second halves
await mergeSort(arr, l, m);
await mergeSort(arr, m + 1, r);
await merge(arr, l, m, r);
}
}
return (
<div className="App">
<div className="num-container">
{randArr &&
randArr.map((n, i) => (
<div
className="num"
style=
key={i}
>
{n}
</div>
))}
</div>
<button
disabled={sortButton}
onClick={(e) => mergeSort(randArr, 0, randArr.length - 1)}
>
Merge Sort
</button>
<button disabled={sortButton} onClick={(e) => bublesort(randArr)}>
Bubble Sort
</button>
</div>
);
}
link to sandbox: Sandbox Thank you!