Как написать QuickSort с сопоставлениями с событиями?

Question

Я пишу веб-приложение, которое задает пользователю ряд вопросов, которые являются просто субъективными сравнениями двух значений. Они выбирают тот, который больше, и он представляет собой следующее сравнение, необходимое для сортировки. Цель состоит в том, чтобы отсортировать 58 элементов и отобразить упорядоченный список.

Я хочу использовать QuickSort, так как 80% времени потребуется меньше сравнений, чем сортировка слияния, что требует 342 сравнения. (Я написал программу, которая провела 5 000 000 симуляций сортировки массивов из 58 элементов и обнаружила, что 342 был 80-м процентилем для количества сравнений, требуемых QS.) Поскольку это выполняется в JavaScript, мне нужен алгоритм для ожидания событие каждый раз, когда требуется сравнение, а затем, когда событие запускается, продолжите алгоритм. Мне нелегко обдумывать, что это должно было бы выглядеть.

Я уверен, что для реализации QS этот путь - если только не существует какого-то умного метода с закрытием JavaScript, о котором я не думаю - я не могу сделать это рекурсивно. Я нашел iterative implementation of QS, и я пытаюсь выяснить, как я могу разделить его так, чтобы триггер события продолжал алгоритм, с которого он остановился.

Я бы опубликовал код, который у меня есть, но, честно говоря, я думаю, что, учитывая, как он смешался и разобщен, это принесет больше вреда, чем пользы. Мне бы очень понравилась реализация 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.