ferrybig

Javascript sorting with generators

Mar 1st, 2021
814
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // HTML for this example: <pre id="output"></pre>
  2.  
  3. function compare(a/*: number*/, b/*: number*/)/*: ['compare', number, number]*/ {
  4.     return ['compare', a, b];
  5. }
  6. function swap(a/*: number*/, b/*: number*/)/*: ['swap', number, number]*/ {
  7.     return ['swap', a, b];
  8. }
  9.  
  10. function* bubbleSort(from/*: number*/, to/*: number*/)/*: Generator<['swap' | 'compare', number, number], void, number> */ {
  11.     let swapped/*: boolean */;
  12.     do {
  13.         swapped = false;
  14.         to -= 1; // decrement by 1 EACH loop, as we know the last element will be in place
  15.         for (let j = from; j < to; j++) {
  16.             if ((yield compare(j, j + 1)) > 0) {
  17.                 yield swap(j, j + 1);
  18.                 swapped = true;
  19.             }
  20.         }
  21.     } while(swapped);
  22. }
  23.  
  24. function log(text/*: string*/)/*: void */ {
  25.     console.log(text);
  26.     document.getElementById('output').innerText += text + '\n';
  27. }
  28.  
  29. function test(array/*: number[] */)/*: void */ {
  30.     const generator = bubbleSort(0, array.length);
  31.     let latestArray = array;
  32.     let nextValue = 0;
  33.     while(true) {
  34.         const action = generator.next(nextValue);
  35.         if(action.done) {
  36.             log(JSON.stringify(latestArray) + ': Done')
  37.             return;
  38.         } else if (action.value[0] === 'compare') {
  39.             const a = latestArray[action.value[1]];
  40.             const b = latestArray[action.value[2]];
  41.             if(a > b) {
  42.                 nextValue = 1;
  43.             } else if (a < b) {
  44.                 nextValue = -1;
  45.             } else {
  46.                 nextValue = 0;
  47.             }
  48.             log(JSON.stringify(latestArray) + `: Compared ${action.value[1]}: ${a} to ${action.value[2]}: ${b} resulting in ${nextValue}`);
  49.         } else if (action.value[0] === 'swap') {
  50.             latestArray = [...latestArray]
  51.             const tmp = latestArray[action.value[1]];
  52.             latestArray[action.value[1]] = latestArray[action.value[2]];
  53.             latestArray[action.value[2]] = tmp;
  54.             log(JSON.stringify(latestArray) + `: Swapped index ${action.value[1]} and ${action.value[2]}`);
  55.         } else {
  56.             throw new Error('What? ' + JSON.stringify(action.value));
  57.         }
  58.     }
  59. }
  60. const array = [9, 3, 4, 0, 7, 5, 2, 8, 1, 6];
  61. test(array);
Advertisement
Add Comment
Please, Sign In to add comment