Printable View
I have encountered a lot of sorting algorithms. Some whose names I do not remember & some names associated with algorithms I do not know.
I have never seen nor heard of anything like the algorithm you described.
It does not seem to be a very useful algorithm. For a large number of items, you cannot afford the memory or disk space. For a small number of items you can use something like bubble sort which is simple but slow.
Perhaps I saw it on one of those sites that promotes useless/unreadable code.
I'll see how fast it can sort 6 random numbers compared to bubblesort.
I'm not proposing this as a serious algorithm you understand! Just something to pass the time :)
Wossname: Analyzing & contemplating sorting algorithms is an interesting pastime. There was a time when I did it for serious purposes. I understand your attitude toward this strange algorithm which is unknown to me.
BTW: Anything that does the job is not useless. At worst it is inefficient or ugly for some reason.
In the main frame world, the basic method was to read a file and use memory to create groups of sorted records (for some reason they called these groups strings). As groups were generated they were written alternately to two or more reels of magnetic tape. After this setup phase, the rest of the sort was done by merging groups read from tape into larger groups written to other tape drives.
Various algorithms were used for the initial phase fo the sort. In the early days when the CPU was slow, a lot of attention was paid to the algorithms used.
With the advent of better & cheaper disk technology, the mainframe world might now use disk files instead of tape or might use other algorithms better suited to disks.
I always wanted to test how well Quick Sort would do with sorting a huge disk file.
On a PC with disks as the only media usable for sorting, it is interesting to note that KwikSort will sort in place, while many of the other fast algorithms require a lot of work space.
If KwikSort is used for a huge disk file, I know that it is better to do the final cleanup with an Insertion Sort (not sure if this is the correct name for the algorithm). Kwiksort is efficient compared to other algorithms when many of the records are far from their correct postions. After multiple KwikSort passes, almost all of the records are close to where they belong, and other algorithms become more efficient. KwikSort is hurt by unnecessary latency time in this final phase of the sort. Even when sorting in memory, Kwiksort is often not used in the final phase of the sort.
BTW: It was always considered cool to refer to Quick Sort as KwikSort. This was supposed to be the mark of an elite programmer who was very savy about sorting.
I'm not sure if you can attribute this algorithm to one person in particular. If you could, it would be just because they were the first to actually write it down.
I'm sure many people, myself included, discovered it for themselves, just that they realise it takes up a lot of memory.
Guv, have you read TAOCP by any chance? Sounds like you may have :)
Since I started reading it I have found sorting to be a completely absorbing area of programming.
I first thought of the above ludicrous sorting method when writing down the lottery numbers as they were dictated by the guy on TV. If I had an A4 paper pad with me I would write the first number that came out half-way down the page and then went on from there with the rest.
Up to now I have found that scenario to be the only use for this method...writing by hand in real-time. However, it is a great party trick if you describe it to your companions properly!!
I wrote a program to simulate it last night...it involves doing a straight insertion sort on the positions of the added values every time one is added. Thus it is very much less efficient than Straight Insertion itself!
I'm sure many scientists / mathematicians over the centuries have shared the following sentiment...
"It is as edifying to disprove a theory or hypothesis, as it is to prove one valid."
(I just made that up by the way, I am certain that any scientific luninary would have put it in much more eloquent terms than have I, they always do. Take a look at the titles of their books for a start! :))
I'm currently translating D.E. Knuth's (Worship, grovel, idolise :D) proper Quicksort definition into PocketC code. Would you be interested filburt1? (if he's reading this).
My current favourite sort is the Distribution sort, (but only because I understand it!) as featured in TAOCP.
I can't believe I entertained that earlier idea for more than a day! Ye gods!