Skip to content

Commit 68d3524

Browse files
BKProgramsBKPrograms
committed
Finished Mergesort and Bubblesort visualisation
1 parent f1be744 commit 68d3524

File tree

4 files changed

+273
-17
lines changed

4 files changed

+273
-17
lines changed

‎src/App.js‎

Lines changed: 4 additions & 17 deletions
Original file line numberDiff line numberDiff line change
@@ -1,24 +1,11 @@
11
import logo from './logo.svg';
22
import './App.css';
3-
3+
import SortingVisualiser from "./components/SortingVisualiser";
44
function App() {
55
return (
6-
<div className="App">
7-
<header className="App-header">
8-
<img src={logo} className="App-logo" alt="logo" />
9-
<p>
10-
Edit <code>src/App.js</code> and save to reload.
11-
</p>
12-
<a
13-
className="App-link"
14-
href="https://reactjs.org"
15-
target="_blank"
16-
rel="noopener noreferrer"
17-
>
18-
Learn React
19-
</a>
20-
</header>
21-
</div>
6+
<div className="App">
7+
<SortingVisualiser></SortingVisualiser>
8+
</div>
229
);
2310
}
2411

‎src/components/SortingVisualiser.css‎

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
.array-container{
2+
position: fixed;
3+
left: 20px;
4+
margin: auto;
5+
6+
}
7+
8+
.array-bar{
9+
width: 2px;
10+
background-color: darkcyan;
11+
display: inline-block;
12+
margin: 2px;
13+
}

‎src/components/SortingVisualiser.js‎

Lines changed: 147 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,147 @@
1+
import React from "react";
2+
import "./SortingVisualiser.css";
3+
import {getMergeAnims, getBubbleAnims} from "../sortingAlgos";
4+
5+
export default class SortingVisualiser extends React.Component {
6+
7+
constructor(props) {
8+
super(props);
9+
10+
this.state = {array: [], value: 200};
11+
}
12+
13+
componentDidMount() {
14+
this.resetArray();
15+
}
16+
17+
getRandomInt(min, max) {
18+
min = Math.ceil(min);
19+
max = Math.floor(max);
20+
return Math.floor(Math.random() * (max - min + 1)) + min;
21+
}
22+
23+
resetArray() {
24+
const array = [];
25+
for (let i = 0; i < this.state.value; i++) {
26+
array.push(this.getRandomInt(1, 750))
27+
}
28+
29+
this.setState({array});
30+
}
31+
32+
mergeSort() {
33+
34+
const animations = getMergeAnims(this.state.array);
35+
36+
for (let i = 0; i < animations.length; i++) {
37+
const arrayBars = document.getElementsByClassName('array-bar');
38+
const isColorChange = i % 3 !== 2;
39+
40+
if (isColorChange) {
41+
const [barOneIdx, barTwoIdx] = animations[i];
42+
const barOneStyle = arrayBars[barOneIdx].style;
43+
const barTwoStyle = arrayBars[barTwoIdx].style;
44+
const color = i % 3 === 0 ? 'red' : 'green';
45+
setTimeout(() => {
46+
barOneStyle.backgroundColor = color;
47+
barTwoStyle.backgroundColor = color;
48+
}, i * 1);
49+
} else {
50+
setTimeout(() => {
51+
const [barOneIdx, newHeight] = animations[i];
52+
const barOneStyle = arrayBars[barOneIdx].style;
53+
barOneStyle.height = `${newHeight}px`;
54+
}, i * 1);
55+
}
56+
57+
58+
}
59+
}
60+
61+
62+
bubbleSort() {
63+
64+
const animations2 = getBubbleAnims(this.state.array);
65+
66+
for (let i = 0; i < animations2.length; i++) {
67+
const arrbar = document.getElementsByClassName('array-bar');
68+
const cChange = (i % 4 !== 2) && (i % 4 !== 3)
69+
70+
if (cChange) {
71+
72+
const [baronei, bartwoi] = animations2[i];
73+
const barOneStyle = arrbar[baronei].style;
74+
const barTwoStyle = arrbar[bartwoi].style;
75+
const color = i % 4 === 0 ? 'red' : 'green';
76+
77+
setTimeout(() => {
78+
barOneStyle.backgroundColor = color;
79+
barTwoStyle.backgroundColor = color;
80+
}, i * 1);
81+
82+
83+
} else {
84+
setTimeout(() => {
85+
const [barOneIdx, newHeight] = animations2[i];
86+
const barOneStyle = arrbar[barOneIdx].style;
87+
barOneStyle.height = `${newHeight}px`;
88+
}, i * 1);
89+
}
90+
}
91+
92+
93+
}
94+
95+
quickSort() {
96+
97+
}
98+
99+
heapSort() {
100+
101+
}
102+
103+
104+
render() {
105+
const arr2 = this.state.array;
106+
107+
return (
108+
<div className="array-container">
109+
{arr2.map((value, i) =>
110+
111+
(<div className="array-bar" key={i} style={{height: `${value}px`}}></div>)
112+
)}
113+
<div>
114+
<button onClick={() => this.resetArray()}>Generate new array</button>
115+
<button onClick={() => this.mergeSort()}>Mergesort</button>
116+
<button onClick={() => this.quickSort()}>Quicksort</button>
117+
<button onClick={() => this.heapSort()}>Heapsort</button>
118+
<button onClick={() => this.bubbleSort()}>Bubblesort</button>
119+
<div>
120+
<input type="range" min="1" max="300" value={this.state.value} className="slider" id="myRange"
121+
onChange={
122+
(event) => this.setState({value: event.target.value})
123+
} step="1"/>
124+
</div>
125+
<span id="output">{this.state.value}</span>
126+
</div>
127+
128+
129+
</div>
130+
)
131+
}
132+
133+
arrAreEq(arr1, arr2) {
134+
if (arr1.length !== arr2.length) {
135+
console.log("size diff");
136+
return false;
137+
}
138+
139+
for (let i = 0; i < arr2.length; i++) {
140+
if (arr1[i] !== arr2[i]) {
141+
console.log(i);
142+
return false;
143+
}
144+
}
145+
return true;
146+
}
147+
}

‎src/sortingAlgos.js‎

Lines changed: 109 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,109 @@
1+
export function getMergeAnims(array) {
2+
const animations = [];
3+
if (array.length <= 1) {
4+
return array;
5+
}
6+
7+
const helperArray = array.slice();
8+
9+
mergeSortHelper(array, 0, array.length - 1, helperArray, animations);
10+
console.log(animations)
11+
return animations;
12+
}
13+
14+
function mergeSortHelper(mainArray, startIdx, endIdx, auxiliaryArray, animations) {
15+
if (startIdx === endIdx) return;
16+
const middleIdx = Math.floor((startIdx + endIdx) / 2);
17+
mergeSortHelper(auxiliaryArray, startIdx, middleIdx, mainArray, animations);
18+
mergeSortHelper(auxiliaryArray, middleIdx + 1, endIdx, mainArray, animations);
19+
doMerge(mainArray, startIdx, middleIdx, endIdx, auxiliaryArray, animations);
20+
}
21+
22+
function doMerge(
23+
mainArray,
24+
startIdx,
25+
middleIdx,
26+
endIdx,
27+
auxiliaryArray,
28+
animations,
29+
) {
30+
let k = startIdx;
31+
let i = startIdx;
32+
let j = middleIdx + 1;
33+
while (i <= middleIdx && j <= endIdx) {
34+
// These are the values that we're comparing; we push them once
35+
// to change their color.
36+
animations.push([i, j]);
37+
// These are the values that we're comparing; we push them a second
38+
// time to revert their color.
39+
animations.push([i, j]);
40+
if (auxiliaryArray[i] <= auxiliaryArray[j]) {
41+
// We overwrite the value at index k in the original array with the
42+
// value at index i in the auxiliary array.
43+
animations.push([k, auxiliaryArray[i]]);
44+
mainArray[k++] = auxiliaryArray[i++];
45+
} else {
46+
// We overwrite the value at index k in the original array with the
47+
// value at index j in the auxiliary array.
48+
animations.push([k, auxiliaryArray[j]]);
49+
mainArray[k++] = auxiliaryArray[j++];
50+
}
51+
}
52+
while (i <= middleIdx) {
53+
// These are the values that we're comparing; we push them once
54+
// to change their color.
55+
animations.push([i, i]);
56+
// These are the values that we're comparing; we push them a second
57+
// time to revert their color.
58+
animations.push([i, i]);
59+
// We overwrite the value at index k in the original array with the
60+
// value at index i in the auxiliary array.
61+
animations.push([k, auxiliaryArray[i]]);
62+
mainArray[k++] = auxiliaryArray[i++];
63+
}
64+
while (j <= endIdx) {
65+
// These are the values that we're comparing; we push them once
66+
// to change their color.
67+
animations.push([j, j]);
68+
// These are the values that we're comparing; we push them a second
69+
// time to revert their color.
70+
animations.push([j, j]);
71+
// We overwrite the value at index k in the original array with the
72+
// value at index j in the auxiliary array.
73+
animations.push([k, auxiliaryArray[j]]);
74+
mainArray[k++] = auxiliaryArray[j++];
75+
}
76+
}
77+
78+
export function getBubbleAnims(array) {
79+
const animations = [];
80+
81+
if (array.length <= 1) {
82+
return array;
83+
}
84+
85+
const helperArray = array.slice();
86+
87+
for (let i = 0; i < array.length; i++) {
88+
for (let j = 0; j < array.length-i-1; j++) {
89+
90+
animations.push([j, j + 1]);
91+
animations.push([j, j + 1]);
92+
93+
if (helperArray[j] > helperArray[j + 1]) {
94+
95+
let temp = helperArray[j];
96+
helperArray[j] = helperArray[j + 1];
97+
helperArray[j + 1] = temp;
98+
99+
}
100+
animations.push([j, helperArray[j]]);
101+
animations.push([j+1, helperArray[j+1]]);
102+
103+
104+
}
105+
}
106+
107+
return animations;
108+
109+
}

0 commit comments

Comments
 (0)