Skip to content

Commit d519643

Browse files
https-samhttps-sam
committed
Faster random array generation algorithm
1 parent 82d67db commit d519643

8 files changed

Lines changed: 66 additions & 54 deletions

File tree

‎src/App.js‎

Lines changed: 15 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -1,19 +1,18 @@
1-
import './App.css';
21
import React, {Component} from 'react';
3-
import {Canvas, useFrame} from '@react-three/fiber';
4-
5-
import {Strategy /*changeRed*/} from './components/Strategy/Strategy';
6-
import {InputField} from './components/Canvas/InputField.js';
7-
import MainCanvas from './components/Canvas/MainSortingCanvas';
8-
import SelectionSort from './components/Strategy/Algorithms/SelectionSort';
9-
10-
import Header from './components/Page/partial/Header';
11-
import Selection from './components/Page/partial/Selection';
12-
import Footer from './components/Page/partial/Footer';
13-
import SplashScreen from './components/Page/Splash/SplashScreen';
14-
import Box from './modals/cube/Box';
2+
// import {Canvas, useFrame} from '@react-three/fiber';
3+
4+
// import {Strategy /*changeRed*/} from './components/Strategy/Strategy';
5+
// import {InputField} from './components/Canvas/InputField.js';
6+
// import MainCanvas from './components/Canvas/MainSortingCanvas';
7+
// import SelectionSort from './components/Strategy/Algorithms/SelectionSort';
8+
9+
// import Header from './components/Page/partial/Header';
10+
// import Selection from './components/Page/partial/Selection';
11+
// import Footer from './components/Page/partial/Footer';
12+
// import SplashScreen from './components/Page/Splash/SplashScreen';
13+
// import Box from './modals/cube/Box';
14+
// import Cell from './components/Board/Cell';
1515
import AppRouter from './AppRouter';
16-
import Cell from './components/Board/Cell';
1716

1817

1918

@@ -30,6 +29,8 @@ class App extends Component {
3029

3130
render() {
3231

32+
33+
3334
return (
3435
<div className = "App">
3536

‎src/AppRouter.js‎

Lines changed: 0 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -3,7 +3,6 @@ import {
33
BrowserRouter as Router,
44
Routes,
55
Route,
6-
Link, BrowserRouter,
76
} from 'react-router-dom';
87
import SplashScreen from './components/Page/Splash/SplashScreen';
98
import MainSortingCanvas from './components/Canvas/MainSortingCanvas';

‎src/Utility/config.js‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -13,6 +13,7 @@ const CONSTANTS = {
1313
PROCESSING: [DARK_BLUE, RED, LIGHT_GREEN, PURPLE, BLACK],
1414
CURRENT_MIN: [RED, YELLOW, DARK_BLUE, LIGHT_GREEN, BLACK],
1515
DELAY: 4, // SG 07/09/2022 13:54 4ms
16+
OFFSET: 280 // SG 07/11/2022 11:18 unit: px, defining the offset of the canvas
1617
}
1718

1819
export { CONSTANTS }

‎src/components/Animation/Animation.js‎

Lines changed: 10 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -22,6 +22,7 @@ class Animation {
2222
for (const timeout of Animation.threads) {
2323
await this.clearTimeout(timeout);
2424
}
25+
Animation.myAudioContext = new AudioContext();
2526
}
2627

2728

@@ -32,13 +33,13 @@ class Animation {
3233
*/
3334
static swap(i, k) {
3435
let unSortedBars = document.querySelectorAll('.array-bars');
35-
var temp1 = unSortedBars[k].style.height;
36+
var oldHeight = unSortedBars[k].style.height;
3637
unSortedBars[k].style.height = unSortedBars[i].style.height;
37-
unSortedBars[i].style.height = temp1;
38+
unSortedBars[i].style.height = oldHeight;
3839

39-
var temp2 = unSortedBars[k].id;
40+
var oldID = unSortedBars[k].id;
4041
unSortedBars[k].id = unSortedBars[i].id;
41-
unSortedBars[i].id = temp1;
42+
unSortedBars[i].id = oldID; // SG 07/11/2022 09:27 temp1
4243
}
4344

4445

@@ -51,6 +52,11 @@ class Animation {
5152
}
5253
}
5354

55+
static async makeBeep(vol, freq, duration){
56+
57+
}
58+
59+
5460
static animateMerge(options, animation) {
5561
const delay = options.delay;
5662
const processingColor = options.processingColor;

‎src/components/Canvas/Canvas.js‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -15,7 +15,7 @@ class Canvas extends Component {
1515
const MARGIN = CONSTANTS.margin;
1616
const SCREEN_WIDTH = window.innerWidth;
1717
const BAR_WIDTH = Math.floor((SCREEN_WIDTH - (MARGIN*arrayLength)) / arrayLength);
18-
const CANVAS_HEIGHT = window.innerHeight - 280+"px";
18+
const CANVAS_HEIGHT = window.innerHeight - CONSTANTS.OFFSET+"px";
1919

2020

2121
return (

‎src/components/Canvas/options/Options.js‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -101,7 +101,7 @@ class Options extends Component {
101101
</div>
102102

103103

104-
<div className={`${algorithm === 'Merge' ? 'hidden' : 'block'} flex flex-col items-center relative space-y-2 cursor-pointer`}>
104+
<div className={`${algorithm === 'Selection' ? 'block' : 'hidden'} flex flex-col items-center relative space-y-2 cursor-pointer`}>
105105
<div className="p-2 hover:bg-gray-200 peer rounded-md" onClick={() => this.setState({showMinBarColor: !showMinBarColor})}>
106106
<Key className="scale-[1.2]"/>
107107
</div>
@@ -139,7 +139,7 @@ class Options extends Component {
139139

140140

141141

142-
<div className={`${algorithm === 'Merge' ? 'hidden' : 'block'} flex flex-col items-center relative space-y-2 cursor-pointer`}>
142+
<div className={`${(algorithm === 'Selection' || algorithm === 'Radix') ? 'block' : 'hidden'} flex flex-col items-center relative space-y-2 cursor-pointer`}>
143143
<div className={`p-2 hover:bg-gray-200 peer rounded-md ${this.props.options.state.options.skipJ && "bg-gray-200"}`} onClick={() => {
144144
this.props.options.setState(prev => ({options: {...prev.options, skipJ: !this.props.options.state.options.skipJ}}))
145145

‎src/components/InputHandler/InputHandler.js‎

Lines changed: 28 additions & 30 deletions
Original file line numberDiff line numberDiff line change
@@ -22,27 +22,38 @@ class InputHandler {
2222
}
2323

2424

25-
/**
26-
*
27-
* @param min
28-
* @param max
29-
* @returns {number}
30-
*/
31-
static randomIntFromInterval = (min, max) => {
32-
// https://gist.github.com/spyesx/485e4584aae767201f41
33-
return Math.floor(Math.random() * (max - min + 1) + min);
34-
};
35-
36-
3725
/**
3826
*
3927
* @returns {number}
4028
*/
4129
static getAllowedMaxInputSize() {
30+
const MAX_BAR_HEIGHT = window.innerHeight - CONSTANTS.OFFSET;
4231
const MARGIN = CONSTANTS.margin;
4332
const BAR_MIN_WIDTH = 1;
4433
const SCREEN_WIDTH = window.innerWidth;
45-
return Math.floor(SCREEN_WIDTH / (BAR_MIN_WIDTH + MARGIN));
34+
const potentialNum = Math.floor(SCREEN_WIDTH / (BAR_MIN_WIDTH + MARGIN));
35+
36+
return potentialNum <= MAX_BAR_HEIGHT ? potentialNum : MAX_BAR_HEIGHT;
37+
}
38+
39+
40+
// https://stackoverflow.com/questions/2450954/how-to-randomize-shuffle-a-javascript-array
41+
static shuffle(array) {
42+
let currentIndex = array.length, randomIndex;
43+
44+
// While there remain elements to shuffle.
45+
while (currentIndex != 0) {
46+
47+
// Pick a remaining element.
48+
randomIndex = Math.floor(Math.random() * currentIndex);
49+
currentIndex--;
50+
51+
// And swap it with the current element.
52+
[array[currentIndex], array[randomIndex]] = [
53+
array[randomIndex], array[currentIndex]];
54+
}
55+
56+
return array;
4657
}
4758

4859

@@ -51,23 +62,10 @@ class InputHandler {
5162
* @param inputSize
5263
*/
5364
static generateRandomIntArray(inputSize) {
54-
let arr = [];
55-
const MAX_BAR_HEIGHT = window.innerHeight - 280;
56-
57-
for (var i = 0; i < inputSize; i++) {
58-
let duplicate = false;
59-
while(!duplicate) { // SG 07/10/2022 22:04 not allowing duplicates
60-
let potentialN = InputHandler.randomIntFromInterval(5, MAX_BAR_HEIGHT);
61-
for(const num of arr) {
62-
if(potentialN === num) duplicate = true;
63-
}
64-
if(duplicate) duplicate = false;
65-
else {
66-
arr.push(potentialN);
67-
break;
68-
}
69-
}
70-
}
65+
const MAX_BAR_HEIGHT = window.innerHeight - CONSTANTS.OFFSET;
66+
let arr = Array.from(new Array(MAX_BAR_HEIGHT), (x, i) => i + 5);
67+
arr = InputHandler.shuffle(arr);
68+
arr = arr.slice(0, inputSize);
7169
InputHandler.setInputArray = arr;
7270
console.log(InputHandler.getGeneratedArray)
7371
Strategy.setTargetArray = arr;

‎src/components/Strategy/Algorithms/RadixSortLSD.js‎

Lines changed: 9 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -23,6 +23,7 @@ class RadixSortLSD {
2323
const DEAULT_COLOR = options.defaultBarColor;
2424
const DELAY = options.delay;
2525
const SORTED_COLOR = options.sortedBarColor;
26+
const PROCESSING_COLOR = options.processingColor;
2627
console.log("================================================================");
2728
let k = array.length;
2829
let sortedArray = new Array(k);
@@ -34,8 +35,14 @@ class RadixSortLSD {
3435
counts[i] = 0;
3536
}
3637

37-
for(let i = 0; i < k; i++) {
38+
for(let i = 0; i < k; i++) { // SG 07/11/2022 09:37 animating iterator
3839
counts[Math.floor(array[i] / exp) % 100]++;
40+
if(!options.skipJ) {
41+
await Animation.getAnimation(DELAY);
42+
DOM[i].style.backgroundColor = PROCESSING_COLOR;
43+
await Animation.getAnimation(DELAY);
44+
DOM[i].style.backgroundColor = DEAULT_COLOR;
45+
}
3946
}
4047

4148
for (i = 1; i < 100; i++) {
@@ -62,6 +69,7 @@ class RadixSortLSD {
6269

6370

6471
for (i = 0; i < k; i++) { // SG 07/10/2022 22:35 copying sorted values
72+
6573
array[i] = sortedArray[i];
6674
}
6775
}
@@ -71,7 +79,6 @@ class RadixSortLSD {
7179
let DOM = Array.from(document.querySelectorAll('.array-bars'));
7280

7381
for(let i = 1; Math.floor(max / i) > 0; i*=100) {
74-
// if((Math.floor(max / i*100) > 0) && i !== 1)
7582
await this.sort(array, i, DOM, options, ((Math.floor(max / i*100) > 0) && i !== 1));
7683
}
7784
}

0 commit comments

Comments
 (0)