javascript - 我将如何通过带有交换的数组直观地显示合并排序算法?
问题描述
我无法使用我的算法尝试直观地显示合并排序的过程。对于我过去的数组,我已经能够将交换与 Bubblesort 等算法一起使用,但归并排序更难,因为它是一种递归算法。我正在考虑将合并函数中的元素推送到另一个数组,但它没有按排序顺序返回,并且最后与排序后的数组进行比较不是真正的合并排序。如果有人可以帮助我,那就太棒了。这是我现在的算法:
export const doMergeSort = (array) => {
function merge(leftArr, rightArr){
const output = [];
let leftIndex = 0;
let rightIndex = 0;
while(leftIndex < leftArr.length && rightIndex < rightArr.length){
const leftEl = leftArr[leftIndex];
const rightEl = rightArr[rightIndex];
if(leftEl < rightEl){
output.push(leftEl);
leftIndex++;
}
else{
output.push(rightEl);
rightIndex++;
}
}
return ( [...output, ...leftArr.slice(leftIndex), ...rightArr.slice(rightIndex)]);
};
function mergeSort(array) {
if(array.length <= 1){
return array;
}
const middleIndex = Math.floor(array.length / 2);
const leftArr = array.slice(0, middleIndex);
const rightArr = array.slice(middleIndex, array.length);
return merge(
mergeSort(leftArr),
mergeSort(rightArr),
);
}
return mergeSort(array);
}
export default mergeSortAnimations;
解决方案
这是我做过的事情,不久前为了实现这一点。使用单个对象来跟踪每个函数级别的数组,所有这些都包装在类似闭包的环境中。还使用了生成器,这样我就可以在每次交换之间暂停。
const getMergeSortGenerator = (object: SortingVisualizerController) => {
// Doing this so that I can pause at any swap for a while using
// setTimeout, or setInterval
function* mergeSortGenerator(start: number, end: number) {
if (start === end) {
return;
}
const mid = Math.floor((start + end) / 2);
// Merge sort on first half
for (const _ of mergeSortGenerator(start, mid)) {
yield;
}
// Merge sort on second half
for (const _ of mergeSortGenerator(mid + 1, end)) {
yield;
}
// Merge both the halves
for (const _ of merge(start, mid, mid + 1, end)) {
yield;
}
// Plot array after each merge.
object.plotArray();
}
// Standard merge algorithm
function* merge(start1: number,
end1: number,
start2: number,
end2: number) {
const newArray = []; // Why? Explained below
let index1 = start1;
let index2 = start2;
// Keep merging while the both sub-arrays have elements
while (index1 <= end1 && index2 <= end2) {
if (object.array[index1] < object.array[index2]) {
newArray.push(object.array[index1++]);
} else {
newArray.push(object.array[index2++]);
}
// Mark the swap color as red
object.color[index1] = object.color[index2] = "red";
// Plot the swap
plotArray(newArray, start1, index1, index2, end1);
// Reset the swap color
object.color[index1] = object.color[index2] = "white";
yield;
}
// If first sub-array has elements left, just add
// them directly
while (index1 <= end1) {
newArray.push(object.array[index1++]);
object.color[index1] = "red";
plotArray(newArray, start1, index1, index2, end1);
object.color[index1] = "white";
yield;
}
// If second sub-array has elements left, just add
// them directly
while (index2 <= end2) {
newArray.push(object.array[index2++]);
object.color[index2 - 1] = "red";
plotArray(newArray, start1, index1, index2, end1);
object.color[index2 - 1] = "white";
yield;
}
// I could not do this in-place because doing each swap
// in-place would mean that, I have to shift other elements
// by 1 to left and that would be a bit tricky to handle.
// So, I managed swaps in the different array, and when the merge
// was completed, I substituted the swaps back in the original
// array.
newArray.forEach((value, index) => {
object.array[index + start1] = value;
});
}
function plotArray(
array: number[],
startOfFirstHalf: number,
index1: number, // First half sorted till this index
index2: number, // Second half sorted till this index
endOfFirstHalf: number,
) {
// Need this because I am using an intermediate array to
// perform the merge.
const visualizingArray = [
...object.array.slice(0, startOfFirstHalf),
...array.slice(0, array.length),
...object.array.slice(index1, endOfFirstHalf + 1),
...object.array.slice(index2, object.array.length),
];
object.plotArray(visualizingArray);
}
return mergeSortGenerator(0, object.array.length - 1);
};
export default class SortingVisualizerController {
arraySize = 166;
minimumHeightOfPipe = 2;
selectedSortAlgorithm = "merge";
animationRunning = false;
constructor(canvasEl: HTMLCanvasElement) {
this.color = [];
this.array = [];
// Canvas is just a class that has some utility functions for drawing on the canvas.
// Find more about it here: https://github.com/vighnesh153/canvas-api-illustrations/blob/master/src/models/canvas.ts
this.canvas = new Canvas(canvasEl);
this.randomizeArray();
}
isArraySorted() {
let prev = -Infinity;
let isSorted = true;
this.array.forEach((value) => {
if (value < prev) {
isSorted = false;
}
prev = value;
});
return isSorted;
}
startAnimation() {
if (this.isArraySorted()) {
return;
}
this.animationRunning = true;
const generatorObject = getMergeSortGenerator(this);
const timer = 30;
this.interval = setInterval(() => {
// Keep yielding, so that we pause after each swap
if (generatorObject.next().done) {
this.stopAnimation();
}
}, timer);
}
clearBackground() {
const {width, height} = this.canvas;
this.canvas.drawFilledRect(0, 0, width, height, "black");
}
generateRandomArray() {
this.array = [];
this.color = [];
const maxHeight = this.canvas.height - 50;
const { floor, random } = Math;
for (let i = 0; i < this.arraySize; i++) {
this.array.push(floor(random() * maxHeight) + 20);
this.color.push("white");
}
}
plotArray(array?: number[]) {
if (array === undefined) {
array = this.array;
}
this.clearBackground();
array.forEach((height: number, index: number) => {
const x = index * 3;
const y = this.canvas.height - value;
const width = 2;
const color = this.color[index];
this.canvas.drawFilledRect(x, y, width,
height + this.minimumHeightOfPipe, color);
});
}
randomizeArray() {
this.generateRandomArray();
this.plotArray();
}
stopAnimation() {
this.animationRunning = false;
clearInterval(this.interval);
this.resetColor();
this.plotArray();
}
resetColor() {
this.color.forEach((v, i) => {
this.color[i] = "white";
});
}
}
推荐阅读
- node.js - 如何使用 vb.net 客户端连接到 node.js Websocket 服务器
- c - 在 C 中解密密码
- c# - 我不能在注册表中添加超过 10 个数字值 DWord
- django - 获取 django.contrib.staticfiles.views.serve 引发的异常
- legend - 删除饼图图例中名称和百分比之间的空格 (amcharts4)
- cuda - 如何对 CUDA 内核中的结构进行原子操作?
- c# - 闪烁的文本框
- c - 如何进入路径中的上一个文件夹?
- javascript - html到内容管理系统
- python - 当类存储在熊猫数据框中时,如何矢量化以访问类方法而不是应用?