Thread: How to sort a simple linked list using swap-sort method

Originally Posted by MK27

A lot of what I have read about comparative sorting on the web has been, I think, regurgitated to the point where the regurgitator has a hard time finding reality.

I don't really understand the formulas used to express the efficiency of the algorithms, but I do understand the algorithms themselves in so far as they are applied in programming. I believe the O(n^2) etc style measurements of efficiency are actually based on a mathematical abstraction of the method ("algorithm") AND NOT statistical measurement of how the method performs in practice. (In other words, this is someone's deductive reasoning and not an empirical observation). After all, you could write a sort according to the algorithm and then average or measure the number of comparisons it makes. But that IS NOT how these formulas (eg. O(n^2)) came into being, and the actual logic of them is not always made apparent.

For example, a normative statement about the bubble sort is that "bubble sort always performs n-1 passes through the data, period. Its best case and worst case behaviors are completely identical". I actually have several charts and tables of formuli that all say this, sometimes vehemently, and I imagine they all actually have the same source somewhere in time and space, which is never referenced because they appear to rest on the authority of deductive reasoning. Yet in practice this statement about bubble sort CANNOT BE TRUE.

In practice, a flag is used to indicate the completion of a sort. Bubble sort passes thru data one item at a time and swaps it forward if it's value is higher than the next item. If, after a pass, nothing has changed, the sort is done.

That means by definition bubble sort will make a variable number of passes. If the list is already sorted (a best case), then you have n-1 passes.

Selection sort, which works by moving lowest values one at a time, will always have the same number of passes since it proceeds the same way regardless. So with an badly unsorted list it will tend to do better than bubble sort, but if the list is only slightly out of order, bubble sort will do much, much better, making a comparable number of passes and comparisons to a merge sort.

So regurgitating these "measurements" out of a textbook tends to imply ??what?? about some of the computer science clergy, iMalc.

I guess it all amounts to the same thing anyway. A merge sort is better than a selection sort is better than a bubble sort, etc.

You seem to putting all kinds of words in my mouth. Big-Oh notation is of course all about the number of operations performed during a sort for the worst case, and taking the steepest of those curves. Hence anything that is for example n*n/2 + n - 1 or something like that is just O(n*n). It's all about mathematics and logical reasoning and deduction. Nested loops are clearly n*m operations where n and m are the loopcount for the respective loops. Clearly then if n and m are the same you have an n*n factor. In the absense of something greater, the n*n is all that matters.
I found that of all the sorting algorithms that are possible when you remove both random access and the ability to insert/remove in constant time from the middle of the data, are all limited to being in the O(n*n) class of algorithms or worse. I'd be pleased to be proven wrong there though, as it should mean there is an algorithm I've overlooked.

I don't see any relevance in the fact that bubble sort can be optimised to perform n-1 operations in the best case. That still means it's O(n*n) because the worst case is unchanged. Saying that all implementations of bubble sort use a flag is either wrong, or rather naieve at best. That isn't even the best way to improve bubble sort. Instead of a boolean flag, you can for the same amount of effort, store the integer position that the bubble floated to, and this improves the running time for even more cases. It's still bubble sort, it just eliminates even more redundant comparisons in certain cases.

Yes I possibly made a mistake, and corrected myself, when I momentarily stated that bubblesort for a linked list (by swapping pointers) is harder to write than quicksort. However as it happens, it actually is pretty damn difficult though anyway, and unless you've actually tried it (and succeeded) then you can't really say otherwise. It probably depends on the language too.
If you do attempt it, be sure to test it very thoroughly, as you may think you have it right, but it might fall over in certain circumstances.
If that's not hard enough for you, try shaker sort for a doubly-linked list. Now that's seriously hard to implement and get right, and I would certainly confidently say that that is harder than just implementing quicksort! Make sure you're doing it by swapping pointers only too.

You should know that I am emphatically NOT someone who just quotes other literature on a subject. I am someone who always learns by doing. I remember once in a lecture on Prolog where we were all told that we should never ever use a certain construct. I argued this to death with my flatmate because before we were even told this, I had written a program which made specific use of that construct. About a month later when the lecturer thought we were at a high enough level to understand it, he told us how he had lied earlier and that there was a specific usage of the construct I mentioned earlier. I could fully understand why he had dumbed it down for us earlier, as using this construct when we didn't understand it would have been disastrous, but I discovered the correct use for it on my own. Anyway, I most certainly do not pass on knowledge I have not at least verified myself.
As it happens, my claim above about being limited to O(n*n) algorithms when there is no random access or insertion is my own claim. I'm not even aware of any literature making the same claim. I'm as against people simply regurgitating information they've had shoved down their throats as much as you are. So, try not to jump to conclusions.

You've no idea how many times I edited that post afterwards...