Hey i want to create sorting alogrithms visualisation for user.I m using typescript to do it first algorithm i start implmenting is bubble sort it do well when the number amount is about 50 but is have a choose box and user can choose from 50,100,250,500.Every thing after 50 is lagging my browser.I m using d3.js to visualise the proccess. Oh and the data is generated using Fisher-Yates shuffle ( 0(n) complexity) .
That the code to add animations for bars to change places
function updateBars(counter: number) {
// Select all the bars and bind them to the data
const bars = svg.selectAll<SVGRectElement, number>("rect").data(data);
bars.style("fill", (_d, i) =>
i === counter || i === counter 1 ? "red" : "blue"
);
// Handle any new data elements by appending new bars
bars
.enter()
.append("rect")
.attr("x", (_d, i) => (i counter) * (barWidth barPadding))
.attr("y", height)
.attr("width", barWidth)
.attr("height", 0)
.merge(bars) // Merge the new bars with the existing ones
.transition() // Animate the transition of the bars
.duration(50)
.attr("y", (d) => height - d)
.attr("x", (_d, i) => i * (barWidth barPadding))
.attr("height", (d) => d);
// Handle any removed data elements by removing the corresponding bars
bars.exit().remove();
}
here is function i use to sort values i with setTimeout it menaged to work somehow with 50 numbers but further it doesnt work.Without set timeout it works even worse.
const bubbleSort = (data: number[], updateBars: Function) => {
let sorted = false;
const sort = () => {
let swapsMade = false;
for (let i = 0; i < data.length - 1; i ) {
if (data[i] > data[i 1]) {
const temp = data[i];
data[i] = data[i 1];
data[i 1] = temp;
swapsMade = true;
updateBars(i);
}
}
if (!swapsMade) {
sorted = true;
}
// Call with delay to avoid performance issues
if (!sorted) {
setTimeout(sort, 50);
}
if (sorted) {
svg.selectAll<SVGRectElement, number>("rect").style("fill", "black");
}
};
sort();
};
I use the start the function when user clicks start button :
startButton.addEventListener("click", () => {
bubbleSort(data, updateBars);
});
Edit : here is link to code that reproducts my issue : https://stackblitz.com/edit/vitejs-vite-v4oidb?file=src/main.ts
CodePudding user response：
The issue is that you will have multiple calls of updateBars before a next setTimeout is called, and this number of calls can represent too much work for one time slice created with the 50ms setTimeout.
This kind of animations is more easily managed with async functions.
All you need to do is define a delay function that promisifies setTimeout, and turn bubbleSort into an async function that awaits a delay after each call of updateBars:
const delay = ms => new Promise(resolve => setTimeout(resolve, ms));
const bubbleSort = async (data, updateBars) => {
let swapsMade = true;
while (swapsMade) {
swapsMade = false;
for (let i = 0; i < data.length - 1; i ) {
if (data[i] > data[i 1]) {
const temp = data[i];
data[i] = data[i 1];
data[i 1] = temp;
swapsMade = true;
updateBars(i);
await delay(10); // <--- adjust number of milliseconds as needed
}
}
}
svg.selectAll('rect').style('fill', 'black');
}
Here is a snippet with your code, and where only the above code was inserted for your bubbleSort function:
const delay = ms => new Promise(resolve => setTimeout(resolve, ms)); // <-- added
const drawVisualization = (data) => {
const margin = { top: 10, right: 10, bottom: 30, left: 10 };
const width = 1200 - margin.left - margin.right;
const height = 400 - margin.top - margin.bottom;
// If it is .visualization del it first
d3.select('.visualization').selectAll('rect').remove();
d3.select('.visualization').select('svg').remove();
const svg = d3
.select('.visualization')
.append('svg')
.attr('width', width)
.attr('height', height)
.attr('transform', 'translate(' margin.left ',' margin.top ')');
// Create a bar chart using the data
const barPadding = 1;
const barWidth = width / data.length - 1;
svg
.selectAll('rect')
.data(data)
.enter()
.append('rect')
.attr('x', (_d, i) => i * (barWidth barPadding))
.attr('y', (d) => height - d)
.attr('width', barWidth)
.attr('height', (d) => d)
.on('mouseover', function (_d, i) {
d3.select(this.parentElement)
.append('text')
.text(i)
.attr(
'x',
() => data.indexOf(i) * (barWidth barPadding) barWidth / 2
)
.attr('y', height - i - 20)
.attr('font-size', '14px')
.attr('fill', 'blue')
.attr('text-anchor', 'middle');
d3.select(this).style('opacity', 0.85);
})
.on('mouseleave', function () {
d3.select(this.parentElement).select('text').remove();
d3.select(this).style('opacity', 1);
});
const startButton = document.querySelector(
'.run-sorting-btn'
);
function updateBars(counter) {
// Select all the bars and bind them to the data
const bars = svg.selectAll('rect').data(data);
bars.style('fill', (_d, i) =>
i === counter || i === counter 1 ? 'red' : 'blue'
);
// Handle any new data elements by appending new bars
bars
.enter()
.append('rect')
.attr('x', (_d, i) => (i counter) * (barWidth barPadding))
.attr('y', height)
.attr('width', barWidth)
.attr('height', 0)
.merge(bars) // Merge the new bars with the existing ones
.transition() // Animate the transition of the bars
.duration(50)
.attr('y', (d) => height - d)
.attr('x', (_d, i) => i * (barWidth barPadding))
.attr('height', (d) => d);
// Handle any removed data elements by removing the corresponding bars
bars.exit().remove();
}
// Replaced this function with async version that calls delay(10);
const bubbleSort = async (data, updateBars) => {
let swapsMade = true;
while (swapsMade) {
swapsMade = false;
for (let i = 0; i < data.length - 1; i ) {
if (data[i] > data[i 1]) {
const temp = data[i];
data[i] = data[i 1];
data[i 1] = temp;
swapsMade = true;
updateBars(i);
await delay(10); //<---
}
}
}
svg.selectAll('rect').style('fill', 'black');
}
startButton.addEventListener('click', () => {
bubbleSort(data, updateBars);
});
};
const generateData = (numPoints) => {
const data = [...Array(numPoints).keys()];
for (let i = data.length - 1; i > 0; i--) {
const j = Math.floor(Math.random() * (i 1));
[data[i], data[j]] = [data[j], data[i]];
}
return data;
};
const dataSizeSelect = d3.select('#data-size');
// let isRunning = false;
// const startButton = document.querySelector(
// ".run-sorting-btn"
// ) as HTMLButtonElement;
const drawVisualizationOnLoad = () => {
const dataSize = dataSizeSelect.property('value');
const data = generateData(dataSize);
drawVisualization(data);
};
// draw on first load
drawVisualizationOnLoad();
// change if values are changed
dataSizeSelect.on('change', drawVisualizationOnLoad);body {
font-family: 'Lato', sans-serif;
overflow-x: hidden;
height: 100vh;
}
main {
margin-top: 50px;
display: flex;
justify-content: flex-start;
align-items: center;
flex-direction: column;
height: 100%;
}
.header {
margin-top: 20px;
font-size: 32px;
font-weight: bold;
}
.visualization {
margin-top: 15px;
width: 100%;
display: flex;
justify-content: center;
align-items: center;
}
/* Sorting wrapper */
.selects-wrapper {
display: flex;
margin-top: 50px;
}
/* Select styles */
.select-outer-container {
display: flex;
flex-direction: column;
justify-content: center;
align-items: center;
}
.select-outer-container p {
font-size: 18px;
}
.select-inner-container {
position: relative;
min-width: 200px;
}
select {
cursor: pointer;
}
select::-ms-expand {
display: none;
}
.select-inner-container:after {
content: '<>';
font: 17px 'Consolas', monospace;
color: #333;
-webkit-transform: rotate(90deg);
-moz-transform: rotate(90deg);
-ms-transform: rotate(90deg);
transform: rotate(90deg);
right: 11px;
/*Adjust for position however you want*/
top: 18px;
padding: 0 0 2px;
border-bottom: 1px solid #999;
/*left line */
position: absolute;
pointer-events: none;
}
.select-inner-container select {
-webkit-appearance: none;
-moz-appearance: none;
appearance: none;
/* Add some styling */
display: block;
width: 100%;
max-width: 320px;
height: 50px;
margin: 5px 0px;
padding: 0px 24px;
font-size: 16px;
line-height: 1.75;
color: #333;
background-color: #ffffff;
background-image: none;
border: 1px solid #cccccc;
-ms-word-break: normal;
word-break: normal;
}
/* Button */
.run-sorting-btn {
margin-top: 10px;
border: none;
border-radius: 5px;
font-size: 22px;
font-weight: bold;
width: 400px;
padding: 10px 15px;
background-color: green;
color: white;
cursor: pointer;
transition: transform 0.3s ease-in;
}
.run-sorting-btn:hover {
transform: translateY(-2px);
}
.run-sorting-btn:active {
transform: translateY(3px);
transition: 0.1s;
}
:root {
font-family: Inter, Avenir, Helvetica, Arial, sans-serif;
font-size: 16px;
line-height: 24px;
font-weight: 400;
color-scheme: light dark;
color: rgba(255, 255, 255, 0.87);
background-color: #242424;
font-synthesis: none;
text-rendering: optimizeLegibility;
-webkit-font-smoothing: antialiased;
-moz-osx-font-smoothing: grayscale;
-webkit-text-size-adjust: 100%;
}
a {
font-weight: 500;
color: #646cff;
text-decoration: inherit;
}
a:hover {
color: #535bf2;
}
body {
margin: 0;
display: flex;
place-items: center;
min-width: 320px;
min-height: 100vh;
}
h1 {
font-size: 3.2em;
line-height: 1.1;
}
#app {
max-width: 1280px;
margin: 0 auto;
padding: 2rem;
text-align: center;
}
.logo {
height: 6em;
padding: 1.5em;
will-change: filter;
transition: filter 300ms;
}
.logo:hover {
filter: drop-shadow(0 0 2em #646cffaa);
}
.logo.vanilla:hover {
filter: drop-shadow(0 0 2em #3178c6aa);
}
.card {
padding: 2em;
}
.read-the-docs {
color: #888;
}
button {
border-radius: 8px;
border: 1px solid transparent;
padding: 0.6em 1.2em;
font-size: 1em;
font-weight: 500;
font-family: inherit;
background-color: #1a1a1a;
cursor: pointer;
transition: border-color 0.25s;
}
button:hover {
border-color: #646cff;
}
button:focus,
button:focus-visible {
outline: 4px auto -webkit-focus-ring-color;
}
@media (prefers-color-scheme: light) {
:root {
color: #213547;
background-color: #ffffff;
}
a:hover {
color: #747bff;
}
button {
background-color: #f9f9f9;
}
}<script src="https://cdnjs.cloudflare.com/ajax/libs/d3/7.8.0/d3.min.js"></script>
<main>
<h1 >Sorting algorithms visualisation</h1>
<div >
<div >
<p>Choose the data size:</p>
<div >
<select id="data-size">
<option value="50" selected>50</option>
<option value="100">100</option>
<option value="250">250</option>
<option value="500">500</option>
</select>
</div>
</div>
<div >
<p>Choose sorting alogorithm:</p>
<div >
<select id="sort-algorithm">
<option value="bubble-sort" selected>Bubble Sort</option>
<option value="selection-sort">Selection Sort</option>
<option value="insertion-sort">Insertion Sort</option>
<option value="merge-sort">Merge Sort</option>
<option value="quick-sort">Quick Sort</option>
</select>
</div>
</div>
</div>
<button >Start</button>
<div ></div>
</main>