tag:blogger.com,1999:blog-1806360094658697411.post6097403193265206323..comments2022-12-04T08:59:01.682-05:00Comments on The Lowly Programmer: Introducing: Marriage SortEric Burnetthttp://www.blogger.com/profile/10741882872804697111noreply@blogger.comBlogger22125tag:blogger.com,1999:blog-1806360094658697411.post-14500271589490676152012-08-07T18:21:21.479-04:002012-08-07T18:21:21.479-04:00You are quite correct. If my memory serves me righ...You are quite correct. If my memory serves me right, I took artistic<br />liberties when making that diagram to make the swap pattern obvious,<br />but the partition really should be the first two elements only.<br /><br />Ruby port you say? Awesome! I shall have to check it out when I get<br />back to a real computer.Eric Burnetthttp://www.thelowlyprogrammer.comnoreply@blogger.comtag:blogger.com,1999:blog-1806360094658697411.post-56063744015430633482010-11-13T20:49:26.371-05:002010-11-13T20:49:26.371-05:00Kinda cool, but not quite sure why you would want ...Kinda cool, but not quite sure why you would want to use it. If it does run O(n^1.5) then it is no improvement. There is already merge-sort and heap-sort that run in O(nlg(n)) which is asymptotically faster than O(n^1.5). So there isn't any improvement, nor can there be. There is a lower bound on comparison based sorting algorithms of nlg(n). So it is impossible to beat merge and heap. Unless you use a non comparison based sorting algorithm like counting sort or radix sort.Bitt3r0blivionnoreply@blogger.comtag:blogger.com,1999:blog-1806360094658697411.post-43477224217130910662010-08-24T10:24:47.344-04:002010-08-24T10:24:47.344-04:00Ahhh... that makes sense. It's interesting how...Ahhh... that makes sense. It's interesting how hard this is to test. The insertion sort at the end covers up a multitude of sins. <br /><br />I know you put code up on GitHub and you're welcome (if it looks correct to you) to grab it and share it there also.slabountyhttp://steamcode.blogspot.com/noreply@blogger.comtag:blogger.com,1999:blog-1806360094658697411.post-16009804162467913932010-08-24T09:48:36.477-04:002010-08-24T09:48:36.477-04:00Sorry about coming so late here, but I just saw th...Sorry about coming so late here, but I just saw this over on Programming Praxis (http://programmingpraxis.com/2010/08/20/marriage-sort/) where I did a Ruby version. One question though, in the picture for the one pass of the merge sort, why isn't the max of the sqrt(N)-1 the value "7" rather than "8"? Wouldn't the sqrt(10)-1 just check the first two values of the array?slabountyhttp://steamcode.blogspot.com/noreply@blogger.comtag:blogger.com,1999:blog-1806360094658697411.post-47696643511076631862010-05-04T17:24:28.357-04:002010-05-04T17:24:28.357-04:00Brilliant work. I am constantly amazed by the crea...Brilliant work. I am constantly amazed by the creativity of programmers in their free time! If only we mathematicians knew that much about programming :)<br /><br />RubenRuben Berenguelhttp://www.mostlymaths.net/noreply@blogger.comtag:blogger.com,1999:blog-1806360094658697411.post-81860585413962241052010-04-15T18:55:20.310-04:002010-04-15T18:55:20.310-04:00@Anonymous: Ok, I have made a better version of th...@Anonymous: Ok, I have made a better version of the "fruit salad" visualization and added it to the post. Thanks, that was a good idea.Eric Burnetthttps://www.blogger.com/profile/10741882872804697111noreply@blogger.comtag:blogger.com,1999:blog-1806360094658697411.post-877296107173032522010-04-15T11:02:57.868-04:002010-04-15T11:02:57.868-04:00@Anonymous: sure, here is a visualization with 512...@Anonymous: sure, here is a visualization with 512 items:<br />http://3.bp.blogspot.com/_4uUxYbT6E0Q/S8cpqJpVF1I/AAAAAAAAD7I/GdEUsBuqHQk/s1600/marriagesort.png<br /><br />Note that this only shows swaps, not compares, so the time isn't as dominated by the insertion sorts as it appears.Eric Burnetthttps://www.blogger.com/profile/10741882872804697111noreply@blogger.comtag:blogger.com,1999:blog-1806360094658697411.post-18116661647444170802010-04-15T10:33:25.226-04:002010-04-15T10:33:25.226-04:00How about posting an image using that "fruit ...How about posting an image using that "fruit salad" visualization from sortvis? I always found that a lot more informative than the spaghetti tangle one:<br /><br />http://corte.si/posts/code/sortvis-fruitsalad/index.htmlAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-1806360094658697411.post-58650671564754325352010-04-15T10:11:42.545-04:002010-04-15T10:11:42.545-04:00Shell sort (with 2^j-1 increments) is one algorith...Shell sort (with 2^j-1 increments) is one algorithm that has a complexity of O(n^{3/2}).Ashutosh Mehrahttp://ashutoshmehra.net/blog/noreply@blogger.comtag:blogger.com,1999:blog-1806360094658697411.post-14789130391005591162010-04-15T10:08:11.697-04:002010-04-15T10:08:11.697-04:00@Andy: So it does! I had looked at Shell sort brie...@Andy: So it does! I had looked at Shell sort briefly and saw it was O(n log(n)^2) in the best case, but I didn't realize it had other known sequences with differing complexities. Time to read up on Shell sort I think.<br /><br />@Jeremy: The most common Shell sort has complexity O(n log(n)^2), so for a rough comparison we can simply plot the two of them: http://www.wolframalpha.com/input/?i=plot+x^1.5,+x*(log(x)/log(2))^2+from+1+to+100000<br />It would seem these two sorts are approximately equivalent in the average case (ignoring constant factor differences) for arrays up to about 100,000 elements. Hmm...I may have to try implementing Shell sort, and see how it actually compare in practice. If I do, I'll report the results back here.Eric Burnetthttps://www.blogger.com/profile/10741882872804697111noreply@blogger.comtag:blogger.com,1999:blog-1806360094658697411.post-43355717282405381872010-04-15T08:50:06.537-04:002010-04-15T08:50:06.537-04:00It'd be interesting to compare this to shell s...It'd be interesting to compare this to shell sort , another sorting algorithm whose complexity is greater than O(n log n) but less than quadratic.Jeremy Fincherhttps://www.blogger.com/profile/03753146170165050792noreply@blogger.comtag:blogger.com,1999:blog-1806360094658697411.post-49683397872083863152010-04-15T08:43:43.058-04:002010-04-15T08:43:43.058-04:00Just for your reference, shell sort (with particul...Just for your reference, shell sort (with particular gap sequences) gives O(n^1.5) worst case.<br /><br />Shell sort is probably my favourite sort, just because of the magic behind the gap sequences :)Andyhttp://www.ultra-premium.com/bnoreply@blogger.comtag:blogger.com,1999:blog-1806360094658697411.post-55723766219759986142010-04-15T07:58:50.668-04:002010-04-15T07:58:50.668-04:00This is also known as the "secretary problem&...This is also known as the "secretary problem" and is nothing spectacularly new. More accurate formulae are given at http://en.wikipedia.org/wiki/Secretary_problem, showing the odds of selecting the best one are far from certain and actually approach zero if you don't know the value of N initially; if N is known initially, they converge on 0.368 as N increases.Speaker-to-Animalshttps://www.blogger.com/profile/05656953232494343804noreply@blogger.comtag:blogger.com,1999:blog-1806360094658697411.post-3888113112445233252010-04-14T20:14:46.969-04:002010-04-14T20:14:46.969-04:00Python is pseudo code!:)Python is pseudo code!:)mechanoidshttps://www.blogger.com/profile/02554146075040307561noreply@blogger.comtag:blogger.com,1999:blog-1806360094658697411.post-48079529638064159972010-04-14T18:11:09.226-04:002010-04-14T18:11:09.226-04:00Ugh, that's the blogger post interface trying ...Ugh, that's the blogger post interface trying to be "smart". I write the posts in html, but when I use the "Compose" interface to add the images, it has a tendency to corrupt the code I wrote. I can only hope there is a better editor coming someday.<br /><br />Should be fixed now.Eric Burnetthttps://www.blogger.com/profile/10741882872804697111noreply@blogger.comtag:blogger.com,1999:blog-1806360094658697411.post-38243527220833559022010-04-14T17:52:36.635-04:002010-04-14T17:52:36.635-04:00Your footnote reference takes me to log in to Blog...Your footnote reference takes me to log in to Blogger. What?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-1806360094658697411.post-50358051606878438142010-04-14T13:41:53.848-04:002010-04-14T13:41:53.848-04:00Photoshop. I don't have any good tools for mak...Photoshop. I don't have any good tools for making diagrams like that, unfortunately, so that one was made by hand.Eric Burnetthttps://www.blogger.com/profile/10741882872804697111noreply@blogger.comtag:blogger.com,1999:blog-1806360094658697411.post-77668083351031889282010-04-14T13:06:15.733-04:002010-04-14T13:06:15.733-04:00What did you use to create one+pass.png?What did you use to create one+pass.png?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-1806360094658697411.post-21984971932167987592010-04-14T11:25:37.638-04:002010-04-14T11:25:37.638-04:00If I call it pseudocode I can skip details like fl...If I call it pseudocode I can skip details like float->int casts, and I don't have to make sure it actually runs ;)Eric Burnetthttps://www.blogger.com/profile/10741882872804697111noreply@blogger.comtag:blogger.com,1999:blog-1806360094658697411.post-64155801349229303412010-04-14T11:19:03.290-04:002010-04-14T11:19:03.290-04:00That's Python, not pseudocode! :-DThat's Python, not pseudocode! :-DAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-1806360094658697411.post-48901696071659668562010-04-14T10:30:11.278-04:002010-04-14T10:30:11.278-04:00You are correct, my pseudocode was broken. The fir...You are correct, my pseudocode was broken. The first inner while loop should have been i < skip, and the second one for i < end was missing entirely. Thanks for catching that!Eric Burnetthttps://www.blogger.com/profile/10741882872804697111noreply@blogger.comtag:blogger.com,1999:blog-1806360094658697411.post-17144097441846909482010-04-14T10:15:14.675-04:002010-04-14T10:15:14.675-04:00Is there an error in your pseudocode? It looks li...Is there an error in your pseudocode? It looks like the first inner while loop should be "while i < skip" instead of "while i < end". Am I missing something?kbobnoreply@blogger.com