La GUI (interfaz gráfica de usuario) ayuda a comprender mejor que los programas. En este artículo, visualizaremos Quick Sort usando JavaScript. Veremos cómo se particiona la array usando la partición Lomuto y luego cómo obtenemos la array ordenada final. También visualizaremos la complejidad temporal de Quick Sort.
Referencia:
Acercarse:
- Primero, generaremos una array aleatoria usando la función Math.random() .
- Se utilizan diferentes colores para indicar qué elemento se compara , la partición izquierda , la partición derecha y el elemento pivote.
- Dado que el algoritmo realiza la operación muy rápido, se ha utilizado la función setTimeout() para ralentizar el proceso.
- Se puede generar una nueva array presionando la tecla «Ctrl + R» .
- La clasificación se realiza usando la función QuickSort() usando la función lometo_partition ()
Ejemplo:
Antes de ordenar
Después de ordenar
A continuación se muestra el programa para visualizar el algoritmo Quick Sort .
index.html
<!DOCTYPE html> <html lang="en"> <head> <link rel="stylesheet" href="style.css" /> </head> <body> <br /> <p class="header"> Quick Sort (Lometo Partition) </p> <div id="array"></div> <div id="count"></div> <br /> <h2 class="range" style="text-align: center"></h2> <script src="script.js"></script> </body> </html>
style.css
* {
margin: 0px;
padding: 0px;
box-sizing: border-box;
}
.header {
font-size: 20px;
text-align: center;
}
#array {
background-color: white;
height: 278px;
width: 598px;
margin: auto;
position: relative;
margin-top: 64px;
}
.block {
width: 28px;
background-color: #6b5b95;
position: absolute;
bottom: 0px;
transition: 0.2s all ease;
}
.block_id {
position: absolute;
color: black;
margin-top: -20px;
width: 100%;
text-align: center;
}
.block_id2 {
position: absolute;
color: black;
margin-top: 22px;
width: 100%;
text-align: center;
}
.block2 {
width: 28px;
background-color: darkgray;
position: absolute;
transition: 0.2s all ease;
}
.block_id3 {
position: absolute;
color: black;
margin-top: 1px;
width: 100%;
text-align: center;
}
#count {
height: 20px;
width: 598px;
margin: auto;
}
script.js
var container = document.getElementById("array");
// Function to generate the array of blocks
function generatearray() {
for (var i = 0; i < 20; i++) {
// Return a value from 1 to 100 (both inclusive)
var value = Math.ceil(Math.random() * 100);
// Creating element div
var array_ele = document.createElement("div");
// Adding class 'block' to div
array_ele.classList.add("block");
// Adding style to div
array_ele.style.height = `${value * 3}px`;
array_ele.style.transform = `translate(${i * 30}px)`;
// Creating label element for displaying
// size of particular block
var array_ele_label =
document.createElement("label");
array_ele_label.classList.add("block_id");
array_ele_label.innerText = value;
// Appending created elements to index.html
array_ele.appendChild(array_ele_label);
container.appendChild(array_ele);
}
}
// Function to generate indexes
var count_container =
document.getElementById("count");
function generate_idx() {
for (var i = 0; i < 20; i++) {
// Creating element div
var array_ele2 = document.createElement("div");
// Adding class 'block2' to div
array_ele2.classList.add("block2");
// Adding style to div
array_ele2.style.height = `${20}px`;
array_ele2.style.transform = `translate(${i * 30}px)`;
// Adding indexes
var array_ele_label2 =
document.createElement("label");
array_ele_label2.classList.add("block_id3");
array_ele_label2.innerText = i;
// Appending created elements to index.html
array_ele2.appendChild(array_ele_label2);
count_container.appendChild(array_ele2);
}
}
async function lometo_partition(l, r, delay = 700) {
var blocks = document.querySelectorAll(".block");
// Storing the value of pivot element
var pivot =
Number(blocks[r].childNodes[0].innerHTML);
var i = l - 1;
blocks[r].style.backgroundColor = "red";
document.
getElementsByClassName("range")[0].innerText = `[${l},${r}]`;
for (var j = l; j <= r - 1; j++) {
// To change background-color of the
// blocks to be compared
blocks[j].style.backgroundColor = "yellow";
// To wait for 700 milliseconds
await new Promise((resolve) =>
setTimeout(() => {
resolve();
}, delay)
);
var value =
Number(blocks[j].childNodes[0].innerHTML);
// To compare value of two blocks
if (value < pivot) {
i++;
var temp1 = blocks[i].style.height;
var temp2 = blocks[i].childNodes[0].innerText;
blocks[i].style.height = blocks[j].style.height;
blocks[j].style.height = temp1;
blocks[i].childNodes[0].innerText =
blocks[j].childNodes[0].innerText;
blocks[j].childNodes[0].innerText = temp2;
blocks[i].style.backgroundColor = "orange";
if (i != j) blocks[j].style.backgroundColor = "pink";
//To wait for 700 milliseconds
await new Promise((resolve) =>
setTimeout(() => {
resolve();
}, delay)
);
} else blocks[j].style.backgroundColor = "pink";
}
// Swapping the ith with pivot element
i++;
var temp1 = blocks[i].style.height;
var temp2 = blocks[i].childNodes[0].innerText;
blocks[i].style.height = blocks[r].style.height;
blocks[r].style.height = temp1;
blocks[i].childNodes[0].innerText =
blocks[r].childNodes[0].innerText;
blocks[r].childNodes[0].innerText = temp2;
blocks[r].style.backgroundColor = "pink";
blocks[i].style.backgroundColor = "green";
// To wait for 2100 milliseconds
await new Promise((resolve) =>
setTimeout(() => {
resolve();
}, delay * 3)
);
document.getElementsByClassName("range")[0].innerText = "";
for (var k = 0; k < 20; k++)
blocks[k].style.backgroundColor = "#6b5b95";
return i;
}
// Asynchronous QuickSort function
async function QuickSort(l, r, delay = 100) {
if (l < r) {
// Storing the index of pivot element after partition
var pivot_idx = await lometo_partition(l, r);
// Recursively calling quicksort for left partition
await QuickSort(l, pivot_idx - 1);
// Recursively calling quicksort for right partition
await QuickSort(pivot_idx + 1, r);
}
}
// Calling generatearray function
generatearray();
// Calling generate_idx function
generate_idx();
// Calling QuickSort function
QuickSort(0, 19);
Producción:
