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

此答案使用非恢复合并排序，该排序可以保留该类型阶段的历史记录。整个排序是在绘制之前执行的，然后在所有阶段绘制步骤，以便我们可以看到算法如何移动线以实现排序。该代码改编自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>

Answer 2

为了可视化我们需要在排序过程中以间隔绘制的那种。在这里，我添加了一个深度变量，以便可以控制这种排序的发展。每次绘制称为i增长深度，以便我们可以看到进度。

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>