How to Visualize Quick Sort Algo while it is arranging the elements in HTML and JS

Spiderman 0
Viewed 23

I have been working on this project for a while now and I would appreciate it if you guys could help me out.

The quick sort algorithm works but since it uses recursion I don't know how or where I should rearrange the HTML divs created.

I have tried rearranging the divs after each swap function is called but that does not seem to work any ideas on how I might solve this problem?

class Element{
    constructor(value , id){
        this.value = value;
        this.id = id;
    }

}


function generateElemenets(){
    for(let i = 0 ; i < 10; i++ ){
        
        let randomValue = generateRandomValue();

        values[i] = new Element(randomValue , i);
        const newDiv = document.createElement("div");
        newDiv.classList.add("element");
        newDiv.setAttribute("id", i);
        container.appendChild(newDiv);
        document.getElementById(i).style.height = `${randomValue}px`;

    

    }
    
}

function generateRandomValue(){
    let x = Math.floor((Math.random() * 100) + 20);
    return x;
}


function quickSort(arr, start, end){
    
    if(start >= end){
        return;
    }

    let index = partition(arr,start, end);

    quickSort(arr, start, index-1);
    quickSort(arr, index + 1, end);
    return arr;

}

function partition(arr, start, end){

    let pivotIndex = start;

    let pivotValue = arr[end].value;

    for (let i = start; i < end ; i++){
        
            if(arr[i].value < pivotValue){
            swap(arr, i, pivotIndex);
            pivotIndex ++;

        }           
        
    }
        swap(arr,pivotIndex, end);

    

    return pivotIndex;

}




function swap(items, leftIndex, rightIndex){
    

    var temp = items[leftIndex];

    items[leftIndex] = items[rightIndex];

    items[rightIndex] = temp;
 

}
quicksort data-structures recursion algorithm javascript
1 Answers

You could:

  • give the div elements an absolute position style, and set a transition effect when their left-coordinate changes.
  • let the swap function return a promise that resolves when the transition effect is complete.
  • Make the quickSort, partition functions asynchronous so they can await the swap promises to resolve

Here is an implementation:

class Element{
    constructor(container, value, i) {
        this.value = value;
        
        const div = document.createElement("div");
        div.classList.add("element");
        div.textContent = value;
        container.appendChild(div);
        div.style.height = `${value}px`;
        div.style.left = `${30*i}px`;
        div.style.top = `${120-value}px`;
        this.div = div;
    }
    move(i) {
        // Return promise that resolves when move is complete
        return new Promise(resolve => {
            this.div.addEventListener('transitionend', (e) => {
                this.div.classList.toggle('highlight', false);
                resolve();
            }, { once: true });
            this.div.classList.toggle('highlight', true);
            this.div.style.left = `${30*i}px`; // trigger transition effect
        });
    }
}

const generateRandomValue = () => Math.floor((Math.random() * 100) + 20);

function generateElements(container, length=10) {
    container.innerHTML = "";
    return Array.from({length}, (_, i) =>
        new Element(container, generateRandomValue(), i)
    );
}

async function quickSort(arr, start, end){
    if (start >= end) {
        return;
    }
    const index = await partition(arr, start, end);
    await quickSort(arr, start, index-1);
    await quickSort(arr, index + 1, end);
    return arr;
}

async function partition(arr, start, end) {
    let pivotIndex = start;
    const pivotValue = arr[end].value;
    for (let i = start; i < end ; i++) {
        if (arr[i].value < pivotValue) {
            await swap(arr, i, pivotIndex);
            pivotIndex++;
        }
    }
    await swap(arr,pivotIndex, end);
    return pivotIndex;
}

function swap(items, leftIndex, rightIndex) {
    if (leftIndex === rightIndex) return; // Nothing to do
    var temp = items[leftIndex];
    items[leftIndex] = items[rightIndex];
    items[rightIndex] = temp;
    return Promise.all([items[leftIndex].move(leftIndex),
                        items[rightIndex].move(rightIndex)]);
}

const elements = generateElements(document.querySelector("#container"));
setTimeout(() => 
    quickSort(elements, 0, elements.length - 1), 
1000);
.element { 
    border: 1px solid;
    width: 25px;
    position: absolute; 
    transition: left 1s;
    background: white;
}

#container {
    margin: 10px;
    position: relative;
}

.highlight {
    background: yellow;
    z-index: 1;
}
<div id="container"></div>

trincot0
Related