如何使用事件驱动比较编写 QuickSort？

Question

我正在编写一个网络应用程序，它会向用户询问一系列问题，这些问题只是两个值的主观比较。他们选择更大的那个，然后它构成了排序所需的下一个比较。目标是对58个项目进行排序，并显示排序后的列表。

我想使用快速排序，因为在 80% 的情况下，它需要的比较次数少于归并排序，后者需要 342 次比较。（我写了一个程序，运行 5,000,000 次模拟排序 58 项数组，发现 342 是 QS 要求的比较次数的第 80 个百分位数。）由于这是在 JavaScript 中完成的，我需要算法在每次需要比较时等待一个事件，然后，当事件被触发时，继续算法。我很难想象这应该是什么样子。

我很确定要以这种方式实现 QS——除非有一些我没有想到的带有 JavaScript 闭包的聪明方法——我不能递归地做到这一点。我找到了一个 iterative implementation of QS，并试图弄清楚如何拆分它，以便事件触发器将从它停止的地方继续算法。

我会 post 我有什么代码，但老实说，我认为考虑到它是多么混乱和脱节，弊大于利。我喜欢 JavaScript 中的完整实现，但即使是伪代码也会有所帮助。

Answer 1

我使用 JavaScript Promises 和递归解决了这个问题。我认为这是一个非常干净的解决方案。

class QS {
    constructor(array) {
        this._array = array;
        this._comparisons = 0;
    }

    run() {
        new Promise(r => {
            return this.runQS(0, this._array.length - 1, r);
        }).then(() => {
            console.log(this._array);
            console.log(this._comparisons);
        });
    }

    runQS(low, high, resolve, part) {
        if (low < high) {
            return new Promise(r => {
                this.partition(low, high, r);
            }).then(p => {
                return new Promise(r => {
                    this.runQS(low, p - 1, r, p);
                });
            }).then(p => {
                return new Promise(r => {
                    this.runQS(p + 1, high, r, p);
                });
            }).then(() => {
                resolve(part);
            });
        } else {
            resolve(part);
        }
    }

    partition(low, high, res) {
        let self = this,
            i = low - 1,
            j = low,
            partProm = Promise.resolve();

        function inner(i, j, doSwap) {
            if (doSwap) {
                i++;
                self.swap(i, j);
            }

            j++;
            if (j < high) {
                addThen(i, j);
            } else {
                i++;
                self.swap(i, high);
                res(i);
            }
        }

        function addThen(i, j) {
            partProm = partProm.then(() => {
                self._comparisons++;
                return new Promise(r => {
                    promptUser(self._array, j, high, r);
                });
            }).then(s => {
                inner(i, j, s);
            });
        }

        if (low < high) {
            addThen(i, j);
        }
    }

    swap(i, j) {
        let temp = this._array[i];
        this._array[i] = this._array[j];
        this._array[j] = temp;
    }
}

我 promptUser() 的占位符是：

function promptUser(a, i, j, resolve) {
    setTimeout(() => {
        console.log('Comparing ' + a[i] + ' against ' + a[j]);
        resolve(a[i] < a[j]);
    }, 10);
}

将 resolve 传递给由按钮 onclick 触发的函数并不难。

如何使用事件驱动比较编写 QuickSort？

How can I write QuickSort with event-driven comparisons?

javascript

quicksort

dom-events