Hacker News new | past | comments | ask | show | jobs | submit login

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.






A 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.


Agreed. My use of the word "optimal" in the original comment was a bit careless.

Hope my comment did not got across as a disagreement. Just wanted to add some relevant detail.

A 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.


> A program generator seems rather advanced for a beginner's assignment...

Ha, it's nothing more complicated than string concatenation.




Applications are open for YC Summer 2020

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: