Here is the idea. I want to implement a sorting algorithm where one would not only be able to sort a given array, but also:
- Inspect the current status of the array
- Pause sorting of array in between to resume it at a later point of time.
An initial idea was to accept a compare and a swap function. That would have allowed:
- Counting the number of compares and swaps.
- Record current status of array in another array using
array.slice()
.
function customSort(array, compareFn, swapFn) { ... }
var compares = 0;
var swaps = 0;
var states = [];
var array = [13, 18, 20, 80, 1];
var compareFn = (a, b) => {
compares++;
return a-b;
};
var swapFn = (i, j, array) => {
swaps++;
states.push(array.slice());
var t = array[i];
array[i] = array[j];
array[j] = t;
};
customSort(array, compareFn, swapFn);
This enables fetching some statistics of the sort operation, but but does allow it to be paused. My second attempt is to convert the customSort
to a generator function that yields when the swap function returns true
.
function* customSort(array, compareFn, sortFn) { ... }
var compares = 0;
var swaps = 0;
var states = [];
var array = [13, 18, 20, 80, 1];
var compareFn = (a, b) => {
compares++;
return a-b;
};
var swapFn = (i, j, array) => {
swaps++;
states.push(array.slice());
var t = array[i];
array[i] = array[j];
array[j] = t;
return swaps % 10 === 0;
};
var iterable = customSort(array, compareFn, swapFn);
var iterator = iterable[Symbol.iterator]();
var {value, done} = iterator.next().value;
// after first 10 swaps, sorting is paused
// if so desired, sorting can now be paused after a certain time as well
while (!done) {
var {value, done} = iterator.next();
}
var result = value;
// and the final value returned is always the sorted array
This approach changes the function signature of sort()
to an unexpected one. Could you come up with an alternative approach to this? Perhaps incorporating even percent completion status, or with minimum performance impact.
Consider this as an academic/fun exercise.
Aucun commentaire:
Enregistrer un commentaire