>Of course I wasn't the first to think of it but that didn't matter, the joy is the same.
Exactly right.
When I was in undergrad physics, I signed up for the intro comp-sci course (which is recommended back then but not yet required). First we learned the basic syntax of C, and in the second unit we learned about sorting algorithms. The Prof introduced us to bubble sort, selection sort, and insertion sort, and also the idea that the efficiency of a sorting algorithm was proportional to how many comparisons it required.
Being a physics student, I knew that there were physical process, like driven granular systems, that sorted objects by size without mathematically comparing anything at all. I wondered if I could beat the efficiency of all three of the algorithms by programming the computer to do something similar, treating integers like differently-sized grains of sand.
Over the weekend I first coded an algorithm I called jostle sort that sent the unsorted integers flying across a 2D array a distance equal to their magnitude, then picked them up again from left to right, top to bottom. This worked, but slowly because it had to look at every cell of the 2D array.
Thinking about it further, I imagined tipping the 2D array up from the bottom edge, so that all the integers in a column slid into a pile in the top row. I realized I only needed the count of how many integers ended up in each column, not the columns themselves. I could just initialize a 1D array of zeroes the size of the max value to be sorted, and increment the value in index n whenever I encountered n in the unsorted array. This worked really well, easily beating the other three algorithms in the criteria we'd been asked to test on our homework assignment.
I'd invented counting sort.
I would later learn that I wasn't the first, but that didn't lessen my pleasure. It's still my favorite sorting algorithm, because of that joy of discovery.
Exactly right.
When I was in undergrad physics, I signed up for the intro comp-sci course (which is recommended back then but not yet required). First we learned the basic syntax of C, and in the second unit we learned about sorting algorithms. The Prof introduced us to bubble sort, selection sort, and insertion sort, and also the idea that the efficiency of a sorting algorithm was proportional to how many comparisons it required.
Being a physics student, I knew that there were physical process, like driven granular systems, that sorted objects by size without mathematically comparing anything at all. I wondered if I could beat the efficiency of all three of the algorithms by programming the computer to do something similar, treating integers like differently-sized grains of sand.
Over the weekend I first coded an algorithm I called jostle sort that sent the unsorted integers flying across a 2D array a distance equal to their magnitude, then picked them up again from left to right, top to bottom. This worked, but slowly because it had to look at every cell of the 2D array.
Thinking about it further, I imagined tipping the 2D array up from the bottom edge, so that all the integers in a column slid into a pile in the top row. I realized I only needed the count of how many integers ended up in each column, not the columns themselves. I could just initialize a 1D array of zeroes the size of the max value to be sorted, and increment the value in index n whenever I encountered n in the unsorted array. This worked really well, easily beating the other three algorithms in the criteria we'd been asked to test on our homework assignment.
I'd invented counting sort.
I would later learn that I wasn't the first, but that didn't lessen my pleasure. It's still my favorite sorting algorithm, because of that joy of discovery.