Javascript 合并排序可视化

Question

我已经设法在 p5.js 中使用合并排序来对不同长度的行进行排序，但无法弄清楚如何实际显示它们正在排序。即显示它们未排序，然后在排序时更新它们的位置。我不确定是否有一种简单的方法可以按照我当前编写的代码的方式执行此操作，或者我是否需要分解排序功能并在每个阶段后重新绘制它？

var values = [];
var numLines = 500;

function setup() {
  createCanvas(900, 600);
  colorMode(HSB, height);
  for (i = 0; i < numLines; i++) {
    values[i] = (round(random(height)));
  }
  
 values = mergeSort(values);
 
  noLoop();
 }


function draw() {
  background(51);

  for (let i = 0; i < values.length; i++) {
    let col = color(values[i], height, height);
    stroke(col);
    fill(col);
    var location = map(i, 0, values.length, 0, width);
    rect(location, height - values[i], width/numLines, height);
  } 
}

function mergeSort(a) {
  if (a.length <= 1) {
    return a;
  }
  var mid = Math.round((a.length / 2));
  var left = a.slice(0, mid);
  var right = a.slice(mid);
  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
  sorted = [];
  
  while (left && left.length > 0 && right && right.length > 0) {
    if (left[0] <= right[0]) {
      sorted.push(left.shift());
    }
    else {
      sorted.push(right.shift());
    }
  }
  return sorted.concat(left, right);
}

<script src="https://cdnjs.cloudflare.com/ajax/libs/p5.js/0.7.2/p5.min.js"></script>

Answer 1

为了可视化排序，我们需要在排序过程中间隔绘制。在这里，我添加了一个深度变量，以便我可以控制排序的范围。每次调用绘制时，我都会增加深度，以便我们可以看到进度。

var values = [];
var numLines = 500;

function setup() {
  createCanvas(900, 600);
  colorMode(HSB, height);
  for (i = 0; i < numLines; i++) {
    values[i] = (round(random(height)));
  }
  frameRate(1);
 }

var depth = 1;
function draw() {
  background(51);
  values = mergeSort(values, depth);
  depth++;
  for (i = 0; i < values.length; i++) {
    let col = color(values[i], height, height);
    stroke(col);
    fill(col);
    var location = map(i, 0, values.length, 0, width);
    rect(location, height - values[i], width/numLines, height);
  } 
  if (depth > 10){
   noLoop();
  }
}

function mergeSort(a, d) {
  if (a.length <= 1) {
    return a;
  }
  d--;
  if (d < 1){
    return a;
  }
  var mid = Math.round((a.length / 2));
  var left = a.slice(0, mid);
  var right = a.slice(mid);
  return merge(mergeSort(left,d), mergeSort(right, d));
}

function merge(left, right) {
  sorted = [];
  while (left && left.length > 0 && right && right.length > 0) {
    if (left[0] <= right[0]) {
      sorted.push(left.shift());
    }
    else {
      sorted.push(right.shift());
    }
  }
  return sorted.concat(left, right);
}

<script src="https://cdnjs.cloudflare.com/ajax/libs/p5.js/0.7.2/p5.min.js"></script>

Answer 2

此答案使用非递归合并排序，保留排序阶段的历史记录。整个排序在绘制之前执行，然后绘制所有阶段的步骤，以便我们可以看到算法如何移动线条来实现排序。该代码改编自 Mike Bostock 的可视化算法。

https://bost.ocks.org/mike/algorithms/ https://bl.ocks.org/mbostock/1b5450d525babd28425f

var values = [];
var numLines = 500;
var sortHist = [];
function setup() {
  createCanvas(900, 600);
  colorMode(HSB, height);
  for (i = 0; i < numLines; i++) {
    values[i] =random(height);
  }
  sortHist = mergeSort(values);
  frameRate(1);
}
  
var historyIndex = 0;
function draw() {
  background(51);
  for (i = 0; i < sortHist[historyIndex].length; i++) {
    let col = color(sortHist[historyIndex][i], height, height);
    stroke(col);
    fill(col);
    var location = map(i, 0, sortHist[historyIndex].length, 0, width);
    rect(location, height - sortHist[historyIndex][i], width/numLines, height);
  } 
  historyIndex++;
  if (historyIndex > sortHist.length -1){
    noLoop();
  }
}

function mergeSort(array) {
  var arrays = [array.slice()],
  n = array.length,
  array0 = array,
  array1 = new Array(n);

  for (var m = 1; m < n; m <<= 1) {
    for (var i = 0; i < n; i += (m << 1)) {
      merge(i, Math.min(i + m, n), Math.min(i + (m << 1), n));
    }
    arrays.push(array1.slice());
    array = array0, array0 = array1, array1 = array;
  }

function merge(left, right, end) {
  for (var i0 = left, i1 = right, j = left; j < end; ++j) {
    array1[j] = array0[i0 < right && (i1 >= end || array0[i0] <=    array0[i1]) ? i0++ : i1++];
   }
 }
 return arrays;
}

<script src="https://cdnjs.cloudflare.com/ajax/libs/p5.js/0.7.2/p5.min.js"></script>

Javascript 合并排序可视化

Javascript merge sort visualisation

javascript

mergesort

p5.js