イベントドリブンの比較でQuickSortを書くにはどうしたらいいですか？

Question

私は、ユーザーに2つの値の主観的な比較である一連の質問をするWebアプリケーションを作成しています。彼らはより大きなものを選び、その並べ替えに必要な次の比較を提示します。目標は58項目をソートし、順序付きリストを表示することです。

私はクイックソートを使用したいと思っています。これは、マージソートよりも比較の回数が80％少ないため、342回の比較が必要です。 （私は、58項目の配列をソートする500万回のシミュレーションを実行したプログラムを書いて、342がQSで必要とされる比較数の80番目のパーセンタイルであることを発見しました）。これはJavaScriptで行われているので、イベントがトリガされたら、アルゴリズムを続行します。私はこのように見えなければならないものの周りに自分の心を包み込むのに苦労している。

QSをこのように実装するには、私はかなり確信しています.JavaScriptクロージャを使った賢明な方法がない限り、再帰的に行うことはできません。私はiterative implementation of QSを見つけて、イベントトリガーが途絶えたところからアルゴリズムを続行できるように、どうやって分割するのか把握しようとしています。

私はどのようなコードを書いていますが、正直言って、どうやって混乱してしまったかを考えると、それは良いことよりも害を及ぼすでしょう。私はJavaScriptで完全な実装が大好きですが、擬似コードでさえ役立つでしょう。

Answer 1

私はJavaScriptの約束と再帰を使ってそれを理解しました。それはかなりきれいな解決策だと私は思います。

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); 
} 

それはボタンのonclickによってトリガされます関数にresolveを渡すためにあまりにも難しいことではありません。