5 ms·

In high school, I once volunteered at a local library for a few hours, sorting returned book alphabetically. At the start, I tried just grabbing the alphabetica

by Zelizz 6y ago

In high school, I once volunteered at a local library for a few hours, sorting returned book alphabetically. At the start, I tried just grabbing the alphabetically "first" book repeatedly, moving it to the front. This got old fast, so after a little while, I started looking at just the first letters, and grabbing all the books I could fit in my hand with that letter. When I had them all "roughly" sorted, I did the same with the second letter, etc. A few years later I learned about sorting algorithms. It's interesting to me that my natural book-sorting intuition was O(n^2) selection sort, but then it wasn't a very big leap for me to tweak it a bit and discover a form of O(n)(ish) radix sort. In school you don't really spend a few hours manually executing sorting algorithms to build an intuition, so the algorithms can feel a bit like artifacts handed down from the gods. How could someone have come up with these? But then, if that's the specific problem you're trying to solve, developing a fairly efficient and sophisticated (and sometimes opaque to future students) algorithm can feel completely natural.

C1sc0cat 6y ago
Back when I had a Saturday job at my local library I used to roughly sort the books alphabetically on the trolley that had the books to be shelved first then go round the shelves.
thaumasiotes 6y ago
> It's interesting to me that my natural book-sorting intuition was O(n^2) selection sort, but then it wasn't a very big leap for me to tweak it a bit and discover a form of O(n)(ish) radix sort. The concepts don't directly apply to sorting physical books on a shelf. For example, insertion sort works well (pick up any book, then put it in the correct place). It is O(n^2) as implemented as a standard sorting algorithm, shuffling numbers around in an inflexible array. But bookshelves are nothing like that. On the shelf, you just shove everything to the left (or right) in a single operation, opening the gap you need. This is not O(n^2). The bookshelf is more like a doubly linked list than like an array.
- Izkata 6y ago
  GP's description is selection sort, not insertion sort, which still requires extra scanning instead of manipulation and remains O(n^2), even in real life.
  - thaumasiotes 6y ago
    > remains O(n^2), even in real life. This is something of a grandiose claim. How are you thinking of a physical insertion sort working? If you don't have a model, you can't say anything about the time requirements. But note that if we conceptualize insertion sort like this: loop: pick up a book find the place within the sorted books where this book belongs open a space for the book insert the book the four steps in that model are O(1), O(log n), O(1), and O(1), and the loop repeats n times, so we have an upper bound of O(n log n). The reason insertion sort is O(n^2) when operating on an array is that step 3, "open a space for the book in our hand" is O(n) in that case, because we can only move one book at a time.
    - Izkata 6y ago
      Please stop arguing, you're agreeing with both of us. I only replied originally because I thought you misread the original comment.
      - thaumasiotes 6y ago
        Ah, my error. If you want to see what I was thinking, imagine I'd pulled the "fuller" quote 'insertion sort, which still requires extra scanning instead of manipulation and remains O(n^2), even in real life'. The point of my comment was just that the complexity of an algorithm as analyzed under one set of primitive operations doesn't automatically translate into another set of operations, even when at a high level it's the same algorithm. It is dangerous to study CS, learn that selection sort (on arrays, on a computer well described by a C-like language) is O(n^2), and then conclude that selection sort (in any context) is inherently O(n^2). That may be true of selection sort in specific -- it's difficult to avoid concluding that the selection step is roughly ϴ(n), and must always run n times -- but the reasoning is faulty, and won't transfer to other algorithms.

by Zelizz 6y ago

C1sc0cat 6y ago

Back when I had a Saturday job at my local library I used to roughly sort the books alphabetically on the trolley that had the books to be shelved first then go round the shelves.

thaumasiotes 6y ago

> It's interesting to me that my natural book-sorting intuition was O(n^2) selection sort, but then it wasn't a very big leap for me to tweak it a bit and discover a form of O(n)(ish) radix sort. The concepts don't directly apply to sorting physical books on a shelf. For example, insertion sort works well (pick up any book, then put it in the correct place). It is O(n^2) as implemented as a standard sorting algorithm, shuffling numbers around in an inflexible array. But bookshelves are nothing like that. On the shelf, you just shove everything to the left (or right) in a single operation, opening the gap you need. This is not O(n^2). The bookshelf is more like a doubly linked list than like an array.

Izkata 6y ago
GP's description is selection sort, not insertion sort, which still requires extra scanning instead of manipulation and remains O(n^2), even in real life.
- thaumasiotes 6y ago
  > remains O(n^2), even in real life. This is something of a grandiose claim. How are you thinking of a physical insertion sort working? If you don't have a model, you can't say anything about the time requirements. But note that if we conceptualize insertion sort like this: loop: pick up a book find the place within the sorted books where this book belongs open a space for the book insert the book the four steps in that model are O(1), O(log n), O(1), and O(1), and the loop repeats n times, so we have an upper bound of O(n log n). The reason insertion sort is O(n^2) when operating on an array is that step 3, "open a space for the book in our hand" is O(n) in that case, because we can only move one book at a time.
  - Izkata 6y ago
    Please stop arguing, you're agreeing with both of us. I only replied originally because I thought you misread the original comment.
    - thaumasiotes 6y ago
      Ah, my error. If you want to see what I was thinking, imagine I'd pulled the "fuller" quote 'insertion sort, which still requires extra scanning instead of manipulation and remains O(n^2), even in real life'. The point of my comment was just that the complexity of an algorithm as analyzed under one set of primitive operations doesn't automatically translate into another set of operations, even when at a high level it's the same algorithm. It is dangerous to study CS, learn that selection sort (on arrays, on a computer well described by a C-like language) is O(n^2), and then conclude that selection sort (in any context) is inherently O(n^2). That may be true of selection sort in specific -- it's difficult to avoid concluding that the selection step is roughly ϴ(n), and must always run n times -- but the reasoning is faulty, and won't transfer to other algorithms.