JavaScript合并排序可视化 [英] Javascript merge sort visualisation

问题描述

我已经设法在p5.js中使一个合并排序工作，以对不同的长度行进行排序，但是无法弄清楚如何真正显示它们正在排序.即显示它们未排序，然后在排序时更新其位置.我不确定是否可以通过一种简便的方式来实现当前代码的编写方式，或者是否需要在每个阶段之后拆分排序功能并重新绘制?

I have managed to get a merge sort working in p5.js to sort different length lines but can not figure out how to actually show them being sorted. I.e show them unsorted and then update their position as they are being sorted. I'm not sure if there is an easy way to do this with the way my code is currently written or if I need to break the sorting function up and re draw it after each stage?

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>

推荐答案

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

This answer uses a non-recursive merge sort that keeps a history of the stages of the sort. The entire sort is performed before draw and then draw steps through all the stages so that we can see how the algorithm moves the lines to achieve the sort. The code is adapted from Mike Bostock's Visualizing Algorithms.

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合并排序可视化的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！