时间戳

首页 > 解决方案 > p5.j​​s 递归冒泡排序

algorithm - p5.j​​s 递归冒泡排序

问题描述

我正在尝试修改此解决方案以适用于冒泡排序，但我有点超出我的深度，尤其是整个async function业务。该代码在一定程度上工作，但不遵循我对冒泡排序所期望的确切模式，并且仅对数组​​进行部分排序。

谁能帮帮我？

let values = [];
let startSort = true;

function bubbleSort( a ) {
    // create copy of the array 
    clone = a.slice();
    // asynchronous sort the copy
    recursiveBubbleSort( clone, clone.length );
    return;
}

//Recursive Bubble Sort
async function recursiveBubbleSort( arr, n ) {
    //If there is only single element 
    //the return the array
    if ( n === 1 ) {
    return arr;
    }

    await recursiveBubbleSort( arr, n - 1 );

    //Swap the elements by comparing them
    for ( let j = 0; j < n - 1; j++ ) {
    if ( arr[j] > arr[j + 1] ) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
    }
    }

    // copy back the current state of the sorting
    values = arr.slice();

    // slow down
    await sleep( 500 );
}

async function sleep( ms ) {
    return new Promise( resolve => setTimeout( resolve, ms ) );
}

function setup() {
    createCanvas( 600, 190 );
    frameRate( 60 );
}

let numOfRects = 15;
let rectWidth;
function draw() {
    if ( startSort ) {
    startSort = false;

    rectWidth = floor( width / numOfRects );
    values = new Array( floor( width / rectWidth ) );
    for ( let i = 0; i < values.length; i++ ) {
        values[i] = random( height );
    }

    bubbleSort( values );
    }

    background( 23 );
    stroke( 0 );
    fill( 255 );
    for ( let i = 0; i < values.length; i++ ) {
    rect( i * rectWidth, height - values[i], rectWidth, values[i] );
    }
}
<script src="https://cdnjs.cloudflare.com/ajax/libs/p5.js/1.1.9/p5.min.js"></script>

标签： algorithmvisualizationp5.jsbubble-sort

解决方案

在这个答案中，我不会关注如何async和await工作，因为这似乎不是你的目标。我将向您展示如何制作冒泡排序的工作版本。

首先让我们摆脱startSort你拥有的这个变量：你用它来初始化你的值，更好的方法是使用setup()p5 使用的函数：

function setup() {
    createCanvas(600, 190);

    rectWidth = floor(width / numOfRects);
    // Generate the values
    values = new Array(floor(width / rectWidth));
    for (let i = 0; i < values.length; i++) {
        values[i] = random(height);
    }
    // The number of iterations is equal to the number of values
    n = values.length;
}

我们首先用随机值填充您的数组并定义一个全局变量n，该变量将保存剩余的迭代次数（与值的数量相同）。

然后让我们修改你的冒泡排序函数。在这里，我们不需要它是递归的，因为正如我稍后将展示的那样，我们将简单地调用它几次，直到我们完成所有迭代。

// Bubble Sort
function bubbleSort(arr, n) {
    // If there is no remaining iterations do nothing
    if (n <= 1) {
        return 0;
    }

    // Swap the elements by comparing them
    for (let j = 0; j < n - 1; j++) {
        if (arr[j] > arr[j + 1]) {
            [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        }
    }

    // We did one more iteration return the remaining number of iterations
    return n - 1;
}

这里有 3 件重要的事情：

  • 该函数在适当的位置修改 arr：因此，当您使用数组调用该函数时，您将在同一个数组中获得结果。
  • 函数返回剩余的迭代次数（每次调用函数都是一次迭代）
  • 如果你用n剩余的迭代次数来调用它，1否则0它将什么也不做。否则它将在数组上进行一次传递。

现在你可以改变你的draw()功能了。此函数由 p5 X 次以秒为单位自动调用（默认为 60）。所以每次运行它都会调用冒泡排序函数，更新数组和剩余迭代次数：

function draw() {
    // Define the "speed" at which we do the iterations
    frameRate(10);
    background(23);
    stroke(0);
    fill(255);

    // Show the values
    for (let i = 0; i < values.length; i++) {
        rect(i * rectWidth, height - values[i], rectWidth, values[i]);
    }

    // Make one new iteration
    n = bubbleSort(values, n);
}

请注意我们过去如何frameRate()不那么频繁地调用它以让用户看到排序的不同步骤。

您只需要在草图开始时声明全局变量，将所有内容放在一起即可。

let values = [];
let numOfRects = 15;
let rectWidth;
let n;

你可以在这里看到完整的代码，你会注意到我在这个实现中做了更多的事情：

  • 我提取了在它自己的函数中将新值放入数组中的代码resetArray()
  • 我在函数中调用这个函数setup()来初始化动画，但也在draw()什么时候调用这个函数，n===0这样当数组排序时，我们会生成新值来获得无限动画。

关于async和的注释await。这些函数用于在 javascript 中创建异步代码。这是一个完整的话题，对于刚接触编程的人来说并非易事，您可以在此处阅读文档。基本上async是用来说一个函数需要时间来执行，await用来说等待函数完成它的执行。

在您从中获得灵感的函数中，此异步代码用于在两次调用bubbleSort函数之间设置延迟，以便用户可以看到不同的迭代。在这里你真的不需要它，因为 p5 为你提供了更容易处理它的draw()机制frameRate()。

推荐阅读