4 ms·
This reminds me of a programming exercise I was asked to write when I first learned programming: write a sorting program generator that given N, generates a pro
by kccqzy 7y ago
This reminds me of a programming exercise I was asked to write when I first learned programming: write a sorting program generator that given N, generates a program that sorts an array of N elements optimally: the generated code has N! branches, one for each possible permutation. With some CSE help from the compiler, it can be really quite fast at the expense of code size.
The author's explanation isn't entirely clear, but it seems similar to the above construction with a fixed N and then a merge sort afterwards.
- gizmo686 7y agoA program generator seems rather advanced for a beginner's assignment... When I started, I wrote an Excel spreadsheet to generate what I would now describe as a 50 element array. I also recall seeing a project to programatically generate mnemonic operators in Haskell, limited only by the ability of the compiler to not run out of memory. Sadly, I can't seem to find it.
- kccqzy 7y ago> A program generator seems rather advanced for a beginner's assignment... Ha, it's nothing more complicated than string concatenation.
- praptak 7y agoA truly optimal sorting for a given N is a nontrivial problem. By truly optimal I mean the actual absolute minimum in the number of comparisons, no O(...) approximation. For five elements the lower bound from counting the permutations is ceil(log2(5!)) which says you cannot sort 5 elements in less than 7 comparisons. An actual 7 comparison algorithm exists but it is not very easy to write it. For greater numbers it gets much much trickier - in general the log(#permutations) lower bound cannot be met.