Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Spaghetti Sorting

Spaghetti Sorting

Spaghetti Sorting for Non Standard Computation Course

Aleksandrs Cudars

January 01, 2014
Tweet

More Decks by Aleksandrs Cudars

Other Decks in Science

Transcript

  1. • take n pieces of uncooked spaghetti • for i

    = 1 to n // O(n) • cut piece i to length li // choosing suitable units of measurement • pick up the n pieces // O(1) • and bang them down on the table • for i = 1 to n // O(n) • remove the tallest remaining piece, and measure it • the recorded sequence of measurements = the sorted list
  2. ~

  3. • S()= 2 3 4 = 3 3 2 •

    S()= 2 = 2 √