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

В этом ответе используется нерекурсивная сортировка слиянием, которая хранит историю этапов сортировки. Вся сортировка выполняется перед отрисовкой, а затем прорисовывается все этапы, чтобы мы могли видеть, как алгоритм перемещает линии для достижения сортировки. Код адаптирован из алгоритмов визуализации Майка Бостока.

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

Чтобы визуализировать сортировку, нам нужно рисовать с интервалами во время сортировки.Здесь я добавил переменную глубины, чтобы я мог контролировать, как далеко идет сортировка.Каждый раз, когда ничья называется, я увеличиваю глубину, чтобы мы могли видеть прогресс.

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>