QuickSort es un algoritmo Divide and Conquer. Selecciona un elemento como pivote y divide la array dada alrededor del pivote elegido. Hay muchas versiones diferentes de quickSort que seleccionan el pivote de diferentes maneras.
- Elija siempre el primer elemento como pivote.
- Elija siempre el último elemento como pivote.
- Elija un elemento aleatorio como pivote.
- Elija la mediana como pivote.
Acercarse:
- En primer lugar, tome una array de valores aleatorios.
- Dibuje rectángulos uno al lado del otro de acuerdo con los valores en el índice de esa array.
- Implemente el algoritmo QuickSort en p5.js.
- Asigne retardos de tiempo para visualizar los cambios realizados en cada etapa sucesiva.
Ejemplo:
<!DOCTYPE html>
<html>
<head>
<meta charset="UTF-8">
<title>QuickSort Sorting Algorithm</title>
<script src=
"https://cdnjs.cloudflare.com/ajax/libs/p5.js/0.8.0/p5.js"
type="text/javascript"></script>
<style>
body {
padding: 0;
margin: 0;
}
canvas {
vertical-align: top;
}
</style>
</head>
<body>
<script type="text/javascript">
// Assign Global Values
let values = [];
let w = 20;
let states = [];
function setup() {
// Create Canvas of given Size
createCanvas(800, 500);
// Assign Array of Random Values
values = new Array(floor(width/w));
for(let i = 0; i < values.length; i++) {
values[i] = float(random(height));
states[i] = -1;
}
// To print values to Browser's Console
print("Unsorted Array:" + values);
// Invoke QuickSort Function
quickSort(values, 0, values.length);
print("Sorted Array:" + values);
}
// Asynchronous Definition of Quick Sort Function
async function quickSort(arr, start, end) {
if(start >= end) {
return;
}
let index = await partition(arr, start, end);
states[index] = -1;
// Promise.all is used so that each function
// should invoke simultaneously
await Promise.all([quickSort(arr, start, index-1),
quickSort(arr, index+1, end)]);
}
// Asynchronous Definition of Partition Function
async function partition(arr, start, end) {
for(let i = start; i< end; i++) {
states[i] = 1;
}
let pivotIndex = start;
let pivotValue = arr[end];
states[pivotIndex] = 0;
for(let i = start; i < end; i++) {
if(arr[i]<pivotValue) {
await swap(arr, i, pivotIndex);
states[pivotIndex] = -1;
pivotIndex++;
states[pivotIndex] = 0;
}
}
await swap(arr, pivotIndex, end);
for(let i = start; i < end; i++) {
states[i] = -1;
}
return pivotIndex;
}
// Definition of Draw function
function draw() {
// Set Background Color
background(51);
for(let i = 0; i < values.length; i++) {
stroke(0);
fill(255);
if(states[i] == 0) {
// Pivot Element
fill(255, 0, 0);
}
else if (states[i]==1) {
// Sorting bar
fill("#58FA82");
}
else {
// Sorted Bars
fill(255);
}
rect(i*w, height - values[i], w, values[i]);
}
}
async function swap(arr, a, b) {
// Call to sleep function
await sleep(100);
let t = arr[a];
arr[a] = arr[b];
arr[b] = t;
}
// Definition of sleep function
function sleep(ms) {
return new Promise(resolve
=> setTimeout(resolve, ms));
}
</script>
</body>
</html>
Producción:
Publicación traducida automáticamente
Artículo escrito por sarthak_ishu11 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA