Skip to content
Snippets Groups Projects
Select Git revision
  • b294fb373482561898870428f9ecde0a3c7df49d
  • main default protected
  • solution
3 results

kthSmallest.js

Blame
  • kthSmallest.js 825 B
    import { View } from './view.js';
    
    function partition(sequence) {
      console.assert(sequence.length > 0, 'Tried to partition an empty sequence.');
      const pivot = sequence[0];
      let i = 1;
      let j = sequence.length - 1;
      while (i !== 0) {
        while (i < sequence.length && sequence[i] <= pivot) {
          ++i;
        }
        while (j > 0 && sequence[j] >= pivot) {
          --j;
        }
        if (i >= j) {
          i = 0;
        }
        const swap = sequence[i];
        sequence[i] = sequence[j];
        sequence[j] = swap;
      }
      return [
        new View(sequence, 0, j),
        sequence[j],
        new View(sequence, j + 1, sequence.length),
      ];
    }
    
    export function kthSmallest(sequence, k) {
      console.assert(
        k >= 0 && k < sequence.length,
        'Tried to find the kth smallest element when k is out of bounds.',
      );
      return sequence[0]; // TODO: stub
    }