Printable View
I would like to sort a simple linked list using swap-sort method what in arrays would be:
I know how to do it using arrays but I a unable to make it work using simple linked lists.Code:for (i=MIN; i<MAX; i++) {
for (j=MIN; j<MAX-1; j++) {
if v[j] > v[j+1] {
aux ← v[j] ;
v[j] ← v[j+1];
v[j+1] ← aux;
}
}
}
Any ideas?
You rearrange the "next" pointers, eg:
Of course, the problem here is the node whose's next was "first", should now point to second. So you can either use a double-linked list to do it, or if possible you can keep track of the previous pointer with a loop (best solution) or (worst solution) you can use a seperate function to find the node whose's next is first.Code:if (first->value > second->value) {
first->next=second->next;
second->next=first;
}
Or what's on third? :0
It sounds like you're specifically after code for bubble-sorting doubly-linked-list via swapping pointers rather than values.
I do have code for that already, but let me tell you that it is very difficult to write. I'm actually on holiday at the moment, but the code is on my website.
The sorting algorithms that are easiest to write for arrays are actually often quite a bit harder for linked lists. Also those that are harder for arrays are sometimes easier for linked lists.
I believe the easiest one for linked-lists is Insertion Sort, so perhaps you could try that?
Merge Sort is however not much harder and is far more effective.
This is just wrong. I've written a merge sort for link lists (which qsort is a refined merge-sort). IN ANY CASE YOU SWAP POINTERS, NEVER VALUES.Quote:
Originally Posted by iMalc
Imagine my node looks like this:
Now, please tell me you are going to write some linked list sorting code that swaps values and not pointers. YOU'D HAVE TO BE A TOTAL FOOL.Code:typedef struct _node {
char firstname[32];
char lastname[32];
char middleinitial;
int group;
float balance;
char note[256];
double special;
struct _node* next;
}
And telling someone that "a quicksort is much easier to write than a bubble sort" is another obvious piece of deception. I would love to hear from even one other person that agrees with what iMalc has written here today.
I corrected myself straight after I first posted. You must have taken over 5 minutes to post. I'm amazed you managed to see what I had written incorrectly. I realised immediately that I was thinking of one of the other sorts.
You can definitely sort a doubly-linked list by swapping values. A number of coders who are used to array sorting try this as their first attempt at linked-list sorting. I certainly agree, it's a very bad idea and you've pointed out one reason why, but some people do it. The other reason is that you are stuck with algorithms that are O(n*n) because you have neither random access, nor tha ability to 'insert' items as you would with a list. I never intended to imply that swapping values would be the normal way of doing it.
Edited for spelling this time.
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.Quote:
Originally Posted by iMalc
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.
All that means is that you @#$#@$ed up the implementation of bubble sort -- or, to be more kind, are implementing some other sort than bubble sort. If you have a flag, it's not bubble sort, since the definition of bubble sort contains no such thing. You can say that it's an easy addition to the algorithm (which it is), and is beneficial (which it is), but that still makes it "something other than bubble sort". An algorithm and its implementation are not the same thing.Quote:
Originally Posted by MK27
Oh really? This is a bubble sort:Quote:
Originally Posted by tabstop
1) Compare two adjacent items.
2) Swap if necessary.
3) Move forward one.
4) Repeat until the list is sorted.
Find me a bubble sort that does not use a flag. The other option is
4) Repeat infinitely.
If "an algorithm and its implementation are not the same thing" means the difference between something that WILL NOT RUN ON A COMPUTER and something that will, then we agree.
I have not "improved" the bubble sort by using a flag -- and they all do -- because otherwise an implimentation IS NOT POSSIBLE.
However, I think I now understand the root of what is obviously a historical argument.
That's not hard -- any bubble sort will do:Quote:
Originally Posted by MK27
If you're an "end for" partisan (or a "next" partisan) then you can close the for-loops appropriately. (I happen to be an "indentation" partisan, so the loops are closed.) You don't have to believe me -- you can check Sedgewick (p. 278 in my copy) if you want.Code:for start <- 0 to n-2
for i <- n-1 downto start+1
if array_(i-1) > array_i
swap array_(i-1) and array_i
Okay! So the formula is O(n^2) because this sort must iterate through the entire list a number of times equal to the length of the list (which with a flag this would be the worst case)?
You may have redeemed computer science in my eyes, tabstop. But barely.
ps. I thought Sedgewick was a girl in a Woodie Allen film.
That's sort of right -- the worst case with a flag is the only case without a flag -- do all the steps that could possibly be needed. However, each time through the list takes one less step (since one number is in place), so it's 1+2+3+4+...+n-1 = n^2-n, which is O(n^2).Quote:
Originally Posted by MK27
So it's polynomial instead of exponential...Quote:
Originally Posted by tabstop
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.Quote:
Originally Posted by MK27
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...
No, actually I've been trying to take you back from the dark side. Of course, I never really believed what I was saying, I just thought I did.Quote:
Originally Posted by iMalc
I've also formed a sort of emotional defensiveness about bubblesort since the first time I had to sort anything, that's what I intuitively wrote. laserlight later identified it as such, scornfully I think -- and now tabstop says I've been using some kind of cheat flag!
So when I heard somebody else in history had come up with a better method(s), I felt determined to master them. Not to be outdone as a masochist either, I'm actually writing (another) program that performs four or five different styles of searches, counts comparisons and list iterations, shuffles, generates random lists, switches criteria, breaks ties with secondary criteria, etc. Real fun, for the whole family! So I expected to see those O(n^2) tables confirmed, and thankfully tabstop cleared this flag issue up or my suspicion that many computer science gurus are more determined to obfuscate than explain would have reached critical proportions.
No doubt. I've never taken any math beyond grade ten but I imagine I will have to if I ever want to work as a programmer. It just seems to me that most computer math is really not complicated, but it ends up couched in "confusing to the layman" style because the assumption (probably correct in most cases) is that the student of computers was already a student of math. What's further implied is that you have to be because it's so useful, and that's part of what I doubt. So anyway, instead of one esoteric, obscurantistic swamp to wade in, there is two! I should probably be happy. But seriously (I hope someone is listening!), much of the information could be explained much better, rather than just sticking to that old story. A lot of web tutorials read like photocopies of one another, which might be okay if the original had more merit. The more such "methods of explanation" get repeated, the more they acquire a weight potentially divorced from their real value. That is probably the heart of my criticism, iMalc. Honestly. About guarding the establishment. It would be nice if we had more "look, I did this/had to do this, and I'm not saying I regret it myself, but for the future maybe we really don't need to use so much latin where english will do".Quote:
It's all about mathematics and logical reasoning and deduction.
Is that a gauntlet on the floor?!Quote:
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.
Just kidding. By "insert/remove in constant time" I presume you mean the difference between a linked list and an array, where the entire array must be re-numbered. "Random access" I'll have to google...ugh.
Well, one possible relevance is that in circumstances where a list is mostly sorted but slightly changed, the bubblesort may be the best choice.Quote:
I don't see any relevance in the fact that bubble sort can be optimised to perform n-1 operations in the best case.
Hmmm.Quote:
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.
This one is definitely an armoured glove.Quote:
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.
Okay, but if you are worried that you potentially sound like someone who is (are you worried, iMalc?) but really you are not, why not test yourself further by seeing if you can come up with a new/different/better method of explanation rather than resorting to the one everyone's heard already? At least then there is the chance of some original thought occurring.Quote:
You should know that I am emphatically NOT someone who just quotes other literature on a subject.
...said the spider to the fly. What if The Emperor Wears No Clothes?Quote:
Anyway, I most certainly do not pass on knowledge I have not at least verified myself.
:)
Pursuant to all this, what's a the relative intensity of processor activity for the following
actions:
- interating thru a character array
- comparing two chars (numerically)
- comparing two ints numerically
- assigning a pointer address
- evaluating an if, for, while statement
You should see them confirmed. If you don't, then your input sizes are not large enough to matter (since "big O" notation refers to asymptotic growth, not actual runtime performance in all cases) and/or you used pathological worst case input for the faster algorithms (e.g., certain canonical variants of quick sort degrade to O(n^2) complexity when sorting an array already sorted in reverse), and/or best case input for the slower algorithms.Quote:
Originally Posted by MK27
Well I've certainly learned that you are a rather interesting character.Quote:
Originally Posted by MK27
My first sorting algorithm wasn't bubblesort. It was pretty similiar except it didn't swap only adjacent items. Coming up with bubblesort independently is nothing to be sneezed at. If one were to immediately think it were the best method there is, that might be well, less-productive thinking.Quote:
Originally Posted by MK27
Code as much as you can, I have no problem with that. You've simply shown me that it's just harder than I realised to explain something to someone who you don't realise doesn't know common terms etc.Quote:
Originally Posted by MK27
I never took classes because I felt I had to, to be a programmer. As far as I was concerned, I already was a programmer. I did so because they were interesting to me. I know a number of programmers with quite varying levels of capability or qualification in various areas, but I believe the main thing you need to be successful is determination and a passion for knowledge, which probably mostly comes down to being one of a certain group of personality types.Quote:
Originally Posted by MK27
You'll find that it isn't really possible to learn such a huge amount about a various subject without ending up using the same terms commonly used, even though you're at the same time putting it in your own words.
I'm sorry, I'm not so good with metaphors or quotes sometimes.Quote:
Originally Posted by MK27
Yeah that's it. Sorry, I'm not used to someone not knowing the term. You'll know what it is, you just aren't familiar with the term for it.Quote:
Originally Posted by MK27
Yeah bubblesort definitely has it's uses where counts are small etc.Quote:
Originally Posted by MK27
Again, I'm not familiar with the metaphor. Nevermind, this time it's my turn to look something up!Quote:
Originally Posted by MK27
You know I'm not really worried. I'm guilty of blabbering today though. Hey, I'm on holiday and it was raining most of the day outside. I had to do something :). It's kind of hard to prove you came up with something independently of someone else when the facts lead you both down the same path though. I guess I should be flattered that any explanations I've given sound like something someone else once wrote. I didn't think I was that good at explaining stuff.Quote:
Originally Posted by MK27
If I cared enough you'd certainly be keeping me busy here. Seriously, I don't read fiction - ever.Quote:
Originally Posted by MK27
But I digress. Can we be of any more assistance with the original topic?
For the most part, yes. I think I've written the coolest linked-list comparative sort demo program ever! It does everything I mentioned earlier plus you can use two text files (lists of a single word on each line) to create random lists for the node struct (a first name, a last name, and an assigned "number").Quote:
Originally Posted by laserlight
You can also choose which criteria to use in the sort and a secondary criteria used to break ties. So using a short dictionary*, you can create lists of hundreds of thousands of nodes with very few possible ties, or using secondary criteria millions. However, you probably don't want to use the slower sorts there -- on my dual core pentium it took about about half an hour to bubblesort 65500 records (over 5 billion iterations). The mergesort will do 1,000,000 records in 6 seconds (a little less than 20 million iterations).Code:typedef struct _node { /* singly linked list */
char first[64];
char second[64];
int ID;
struct _node *next;
}node;
*there are lots of these kinds of (usually alphabetized) text lists of names and/or words around.
But the real purpose of my post now is to shed some further light on the significance of the big O notation and the issues it conceals.
Of course, deciding how to count the iterations was not as clear cut for all the sort styles. But here's some sample output:
(The "shuffle" is a Fisher-Yates algorithm.)Code:[root~/C] ./a.out -h
Usage: ./a.out [-h] [-f -l] [-1] [-2] [-d]
-d either 1 or 2: copious output to stderr
-h print this message
-f filename
-l number of records in list, needed with -f
-1 primary sort criteria (1=first name, 2=last name[default], 3=number)
-2 secondary sort criteria (0=none[default], 1=first name, etc.)
Eg. "./a.out -f data.txt -l 27 -1 2 -2 1"
Records should have the structure "Some Name:0101".
[root~/C] ./a.out
Using "", 0 records
Primary Criteria offset=64
Command (h for help, Q to quit): h
d display list
h show this message
b (modified) bubblesort
i insertion sort
m mergesort
q quicksort
s selection sort
S shuffle
N new random list
R reload from file
W write to file
Command (h for help, Q to quit): N
How many records? 10
New list is 1.41 kb
Command (h for help, Q to quit): d
0x1a90010 nonglare,James (1)
0x1a900b0 stroys,James (420)
0x1a90150 enslave,Jim (1024)
0x1a901f0 mirex,Tammy (666)
0x1a90290 peartly,Lorenzo (420)
0x1a90330 soymilks,Bob (1024)
0x1a903d0 weeks,Robert (0)
0x1a90470 addrest,Tammy (69)
0x1a90510 starnose,Leslie (27)
0x1a905b0 acerous,Paul (1024)
Command (h for help, Q to quit): N
How many records? 10000
New list is 1406.25 kb
Command (h for help, Q to quit): b
Bubblesorting.......
97760000 Iterations Comparison calls: 97750224
Elapsed time: 0 min 31 sec
Command (h for help, Q to quit): S
Shuffled.
Command (h for help, Q to quit): s
Selectionsorting....
99980002 Iterations Comparison calls: 49995000
Elapsed time: 0 min 19 sec
Command (h for help, Q to quit): S
Shuffled.
Command (h for help, Q to quit): i
Insertionsorting.......
24883640 Iterations Comparison calls: 24883640
Elapsed time: 0 min 6 sec
So the bubble sort and the selection sort do about what is expected vis. "iterations", (10,000 squared), the insertion sort comes out quite a bit better. Iterations/comparisons remain at a constant ratio for the selection sort, whereas because the bubblesort is "modified" (using a flag as per my discussion with tabstop above), the bubblesort and the insertion sort have a best case of n or n-1 for both iterations and comparisons.
The default is a string comparison, which is much more processor intensive than a numerical comparison (eg, selection sort will do 10,000 records by ID number in 8 seconds). The difference between the number of comparisons is what accounts for the speed difference above; while both bubble and selection sort did almost n^2 iterations, selection sort did half as many comparisons. It should be noted that while the iteration count may be subject to criticism, the comparison count is absolute as it is incremented every time a discrete comparison function is called. This discrepancy (that an iteration need not be a comparison) is not referred to in many discussions of sorting efficiency and is not accounted for with big O.
A third measure is available with the number of recursive function calls in merge sort and quick sort. Because the sorts are similarly recursive, these counts are always the same:
2^21 is 2097152, so we would expect 43830192 here as the the big O (n*log(n)) best/average score here. Initially, I could not write a quick sort faster than a merge sort and am not sure why anyone would think it should be faster, except that it does hold out some possibilities for optimization with the pivot value. I couldn't be bothered to go further than selecting the lowest of the two first values as the pivot. It does much, much worse using just the head of each list as it's pivot, probably since with very long alphabetic matches lists will end up composed of smaller subsections of the alphabet, easily creating a lopsided division with a totally random pivot value. Its open ended "worst case" means it's prone to certain weaknesses, such as when a secondary criteria is added to resolve ties. This becomes increasingly obvious as the list size increases, as all these differences do (at ten items, a bubblesort only does about twice as many iterations as a mergesort, at a hundred items it does ten times as many):Code:Command (h for help, Q to quit): N
How many records? 2097152
New list is 294912.00 kb
Command (h for help, Q to quit): m
Mergesorting..............2097151 function calls
61865985 Iterations Comparison calls: 41388898
Elapsed time: 0 min 15 sec
Command (h for help, Q to quit): S
Shuffled.
Command (h for help, Q to quit): q
Quicksorting..............2097151 function calls
148857828 Iterations Comparison calls: 75517673
Elapsed time: 0 min 32 sec
Quicksort suffers this way with ties for the same reason it suffers sorting an already ordered list, which is it's worst case scenario. Because mergesort does not spend time putting a list in order after it's been split off, and instead does it when merging them together, it will benefit if the original list was already in some kind of order, whereas this will only hurt quicksort depending on how the pivot value is choosen. To establish a mean or median value, we must iterate through the list before splitting it -- although in discussions of quicksort I have seen, this process apparently "does not count" as part of it's big O notation. Additional comparisons at each of these iterations would be required as well. Taking the pivot from an already ordered tied list will usually end up on the low side, creating an imbalanced list. Putting pivot ties on the right (opposite the pivot) may improve performance slightly.Code:/* set primary criteria to "3" (ID number, of which there are only ten possible) and
secondary to first name (of which there are 59 possible). So there will be lots and
lots of ties to "resolve". Other cases in this demo use a single criteria (the last name)
of which there are 80638 unique possibilities: */
[root~/C] ./a.out -1 3 -2 1
Using "", 0 records
Primary Criteria offset=128
Secondary Criteria offset=0
Command (h for help, Q to quit): N
How many records? 100000
New list is 14062.50 kb
Command (h for help, Q to quit): m
Mergesorting..............99999 function calls
2315025 Iterations Comparison calls: 2748000
Elapsed time: 0 min 0 sec
Command (h for help, Q to quit): S
Shuffled.
Command (h for help, Q to quit): q
Quicksorting..............99999 function calls
20542647 Iterations Comparison calls: 20123133
Elapsed time: 0 min 2 sec
Command (h for help, Q to quit): N
How many records? 1000000
New list is 140625.00 kb
Command (h for help, Q to quit): m
Mergesorting..............999999 function calls
27884993 Iterations Comparison calls: 34081612
Elapsed time: 0 min 6 sec
Command (h for help, Q to quit): S
Shuffled.
Command (h for help, Q to quit): q
Quicksorting..............999999 function calls
1836821111 Iterations Comparison calls: 1832407830
Elapsed time: 4 min 4 sec
Notice the number of recursions is still the same -- an imbalanced list does not increase the number of recursions, since the short half simply goes through fewer. But the number of iterations and comparisons with quicksort can change radically:
This is the "worst case" (n^2) on an ordered list.Code:Command (h for help, Q to quit): N
How many records? 100
New list is 14.06 kb
Command (h for help, Q to quit): q
Quicksorting..............99 function calls
1256 Iterations Comparison calls: 694
Elapsed time: 0 min 0 sec
Command (h for help, Q to quit): q
Quicksorting..............99 function calls
9800 Iterations Comparison calls: 4950
Elapsed time: 0 min 0 sec
Now, apparently merge sort will perform the same in either case. This is true if we just measure iterations, but if we take more reality into account, the number of comparisons can, will, and must change. This is because when two split lists come back to be merged, if one list already contains all smaller values, all of the values on the left will be compared one at a time to the first element of the right, and then (since the returned lists have an internal order) no further comparisons need be done and the right is simply iterated onto the end. That is the normative and perhaps only way to implement a merge sort:
The second last two lines represent these presorted/tied (hence already unequal) cases -- which in quicksort would be a handicapping imbalance. If the values are well mixed, these two lines are irrelevant and a comparison is made for every iteration. Observation bears this out:Code:/* the end (merge) of the sort function */
while ((left) && (right) && (lenL>LC) && (lenR>RC)) {
Iterations++;
result=compfunc(offset,left,right);
if ((result==0) && (altfunc)) result=altfunc(altset,left,right);
if (result==2) { ptr->next=right; ptr=right; right=right->next; RC++; }
else { ptr->next=left; ptr=left; left=left->next; LC++; }
} /* if one list is longer or contains more high values, leaving a final remainder */
while ((left) && (lenL>LC)) { ptr->next=left; ptr=left; left=left->next; LC++; Iterations++; }
while ((right) && (lenR>RC)) { ptr->next=right; ptr=right; right=right->next; RC++; Iterations++; }
ptr->next=NULL; /* the new tail */
As predicted, the number of function calls and iterations (roughly n*log(n)) remains constant, but in the case of the ordered list, the number of comparisons is almost cut in half. This factor is completely hidden when considering big O notation.Code:Command (h for help, Q to quit): N
How many records? 100
New list is 14.06 kb
Command (h for help, Q to quit): m
Mergesorting..............99 function calls
817 Iterations Comparison calls: 545
Elapsed time: 0 min 0 sec
Command (h for help, Q to quit): m
Mergesorting..............99 function calls
817 Iterations Comparison calls: 316
Elapsed time: 0 min 0 sec
To give quicksort one last chance, I decided to add a function which could select a better pivot, despite my misgivings about the additional iterations and comparisons required. So now, the quicksort compares the head with an element about half way thru, and if these are identical, goes thru the whole list until it finds one that isn't. Then we take a mean of the two different values. This helps to ensure that that we will actually have two lists.
This clearly helped to divert quicksort (which it should really be contrasted with mergesort as "splitsort", but anyway...) away from it's worst case, the already sorted list:
In the second instance the list is already sorted. Contrast this with the cruder quicksort, above, which made the n*n on an already sorted list. While it still hasn't quite caught up to the mergesort, it very nearly has -- the time for the much tied sort of one million records went from over 4 minutes to 7 seconds.Code:
Command (h for help, Q to quit): N
How many records? 100
New list is 14.06 kb
Command (h for help, Q to quit): q
Quicksorting..............99 function calls
1443 Iterations Comparison calls: 882
Elapsed time: 0 min 0 sec
Command (h for help, Q to quit): q
Quicksorting..............99 function calls
1127 Iterations Comparison calls: 754
Elapsed time: 0 min 0 sec
Then I modified the newlist() function to assign random ID's just from rand(), rather than a fixed set of 10. That means billions of possibilities on a 64-bit so I could now compare the sorts on scrambled sets of millions of unique numbers:
There is still obviously room to optimize the selection of the pivot value further, particularly if we were only dealing with unique numbers, since then taking a true mean of a sublist would be more feasible. But if quicksort and mergesort still both have a best case of n*log(n) (88 million here) anyway, I think I will just stick with merge sort.Code:[root~/C] ./a.out -1 3
Using "", 0 records
Primary Criteria offset=128
Command (h for help, Q to quit): N
How many records? 4000000
New list is 562500.00 kb
Command (h for help, Q to quit): m
Mergesorting..............3999999 function calls
123539969 Iterations Comparison calls: 82696100
Elapsed time: 0 min 9 sec
Command (h for help, Q to quit): S
Shuffled.
Command (h for help, Q to quit): q
Quicksorting..............4000000 function calls
190179315 Iterations Comparison calls: 100817020
Elapsed time: 0 min 23 sec
A final interesting point: both the quicksort and the insertion sort demonstrated the variation inherent in their design; with insertion sort this variation is toward a "best case" (improving on n^2), whereas with quicksort this is toward a "worst case" (away from n*log(n)). A quick sort cannot really do better than a merge sort although the implementation of a quicksort may be easier to tweak closer to the best case, but in any case would be better known as the "split sort" or "quack sort".
I put up a nice syntax-colored version of the code which produced this nonsense, in case someone wants to argue some silly point:
MK27's linked list comparative sort demo program!
I believe this is fairly portable. It could almost be used as a crude API, since the sort functions use external comparison functions with offsets to criteria (meaning you could plug any kind of struct into it without changes).
Bubblesort is n-1 iterations, each of which makes 1, 2, 3, ..., n comparisons. So the comparison count is n^2, not the iteration count. (Again, big O does not concern itself with constants or non-important terms. 4n^2 is O(n^2), n^2+n is O(n^2), etc.)
With the bubblesort the ratio of iterations to comparisons is exact (in the demo, comparisons is invariably within 0.5% of iterations). Big O count cannot be based on comparison count and must be based on iteration count, as I pointed out with reference to merge sort, or else merge sort cannot have a constant best/average/worst rating.Quote:
Originally Posted by tabstop
I'm not sure why you belabored yourself with testing the Quicksort algorithm, for linked lists, since it is not designed for any data that must be retrieved (relatively), slowly.
Whether it's a linked list, a tape drive, or data that must be accessed over a (relatively slow) network, Quicksort is simply not the algorithm of choice.
Mergesort is designed for that purpose.
Put your data into an array or static disk drive, give Quicksort some smart tweaks (and watch out because it is "fragile"), and *then* you can watch Quicksort *fly*.
In this case that abhorrent snail, the RAM.Quote:
Originally Posted by Adak
Don't be silly Adak. The weaknesses I concerned myself with vis. "quicksort" are inherit to the algorithm and independent of the implementation.Quote:
Originally Posted by Adak
The reason why it "does not count" is that it does not change the complexity in terms of big O notation. In order to split the list into two partitions an iteration must be made over the entire list. Making another iteration over part of the list, or the entire list, just increases the constant factor, so the complexity remains the same.Quote:
Originally Posted by MK27
I would echo Adak's complaint here: you have selected a data structure on which quick sort is not commonly used. For example, are you aware of the "median of three" method for selecting a pivot for quicksort? Typically, this method involves selecting as the pivot the median of the first, middle and last elements. It should still be possible to construct pathological worst case input, but harder and rarer in practice. Another possibility is random pivot selection, but that means using a RNG or PRNG. However, both these methods require random access to be efficient, but linked lists do not provide random access.Quote:
Originally Posted by MK27
What do you mean? If you have forgotten, RAM stands for Random Access Memory, and that describes an array, not a linked list. Relative to disk, RAM is fast.Quote:
Originally Posted by MK27
The choice of data structure can affect the complexity and performance of the algorithm. A commonly cited case is where selection sort is used on a heap: the result is otherwise known as heap sort, which has an average and worst case complexity of O(n log n).Quote:
Originally Posted by MK27
Fisher-Yates huh? I had to lok that one up. It turns out that I'm using Durstenfeld's version of the algorithm, which is the fast, modern way of implementing that algorithm. But as I've tried to show previously with other stuff I've posted about, I wasn't told about this algorithm, or been asked to implement it. I simply needed to shuffle an array and I wrote code that would do it in such a way that to me would obviously produce no bias.Quote:
Originally Posted by MK27
As others say, Big Oh notation isn't exact operation counts. The implementation could do anything from 1000*n*log(n) operations to 0.001*n*log(n) operations or even outside that range. For example, using an SIMD instruction set. you could perform multiple compares or swaps in one operation.Quote:
2^21 is 2097152, so we would expect 43830192 here as the the big O (n*log(n)) best/average score here. Initially, I could not write a quick sort faster than a merge sort and am not sure why anyone would think it should be faster, except that it does hold out some possibilities for optimization with the pivot value.
See my comments below.Quote:
Quicksort suffers this way with ties for the same reason it suffers sorting an already ordered list, which is it's worst case scenario. Because mergesort does not spend time putting a list in order after it's been split off, and instead does it when merging them together, it will benefit if the original list was already in some kind of order, whereas this will only hurt quicksort depending on how the pivot value is choosen. To establish a mean or median value, we must iterate through the list before splitting it -- although in discussions of quicksort I have seen, this process apparently "does not count" as part of it's big O notation. Additional comparisons at each of these iterations would be required as well. Taking the pivot from an already ordered tied list will usually end up on the low side, creating an imbalanced list. Putting pivot ties on the right (opposite the pivot) may improve performance slightly.
You may notice that the number of comparisons is bounded by a factor of two. The case where all items in one list are less than the other gives say k cmparisons where both lists are of length k. Incidentally the concatenation of the two lists can be done in constant time. Then the worse case is that 2k comparisons are required. This can be taken form the fact that each comparison reduces the number of items by 1, there are two lists of length k, items never move between the two lists being merged, and only the head items are compared each time. So Merge Sort performs between n*log(n) and 2*n*log(n) comparisons.Quote:
Now, apparently merge sort will perform the same in either case. This is true if we just measure iterations, but if we take more reality into account, the number of comparisons can, will, and must change. This is because when two split lists come back to be merged, if one list already contains all smaller values, all of the values on the left will be compared one at a time to the first element of the right, and then (since the returned lists have an internal order) no further comparisons need be done and the right is simply iterated onto the end. That is the normative and perhaps only way to implement a merge sort:
Taking the mean isn't an option for every data type, but something like that has been done before, for integers. Someone has previously called this Artificial Sort. My prior work to this only requires that two items be subtractable, not averagable.Quote:
To give quicksort one last chance, I decided to add a function which could select a better pivot, despite my misgivings about the additional iterations and comparisons required. So now, the quicksort compares the head with an element about half way thru, and if these are identical, goes thru the whole list until it finds one that isn't. Then we take a mean of the two different values. This helps to ensure that that we will actually have two lists.
My own findings with sorting on linked lists also agree that quicksort for linked lists doesn't win out until the list length gets really really long.Quote:
In the second instance the list is already sorted. Contrast this with the cruder quicksort, above, which made the n*n on an already sorted list. While it still hasn't quite caught up to the mergesort, it very nearly has -- the time for the much tied sort of one million records went from over 4 minutes to 7 seconds.
Let me introduce you to the smart splitter choosing techinque of my SuperQuickSort for linked-lists. The already sorted and reverse sorted cases become O(n). The trick is that the work done in hunting for a splitter isn't simply additional work that reduces the avarage amount of work required later by picking a beter splitter. Instead it actually replaces a portion of the splitting process (potentially the entire splitting process, if the list was already sorted). Have a look at it on my website. It's one of the things that I've actually gone into much more detail with. (Link in sig)Quote:
There is still obviously room to optimize the selection of the pivot value further, particularly if we were only dealing with unique numbers, since then taking a true mean of a sublist would be more feasible. But if quicksort and mergesort still both have a best case of n*log(n) (88 million here) anyway, I think I will just stick with merge sort.
I agree that the standard quicksort probably isn't worthwhile for lists.Quote:
A final interesting point: both the quicksort and the insertion sort demonstrated the variation inherent in their design; with insertion sort this variation is toward a "best case" (improving on n^2), whereas with quicksort this is toward a "worst case" (away from n*log(n)). A quick sort cannot really do better than a merge sort although the implementation of a quicksort may be easier to tweak closer to the best case, but in any case would be better known as the "split sort" or "quack sort".
Incidentally I've recently become of the opinion that Splay-Tree-Sort is in many ways the ultimate doubly-linked-list sorting algorithm.
It's just so amazingly adaptive, and the list links can be reused as tree child pointer links during the sorting. Any initial sort order you can throw at it, other than random order, gives astoundingly low comparison counts. If this interests you, I highly recommend trying it out.
Nice!Quote:
I put up a nice syntax-colored version of the code which produced this nonsense, in case someone wants to argue some silly point:
MK27's linked list comparative sort demo program!
I believe this is fairly portable. It could almost be used as a crude API, since the sort functions use external comparison functions with offsets to criteria (meaning you could plug any kind of struct into it without changes).
Mine is implemented in C++ rather than C and this means I don't have to make any modifications whatsoever to the algorithms to animate then and count comparisons etc. The same code you would use in a real program is the exact code I use in my demo app. I recommend you download it and check it out as I'm sure you'll enjoy it. It's linked at the bottom of many of my pages.
you just pick on pointer store its value
and search in the rest of the list for the minimal
value
and swap the values
then go next to the next node
hello
i want a bubblesorting program of a string using 2d array n using pointers.plz
help me plzzzzzzzzzzzzz.
hello
i want a bubblesorting program of a string using 2d array n using pointers.plz
help me plzzzzzzzzzzzzz.
plz.
i wil be highly thank ful to him/her.
plz