[QUOTE=Dalto11;41701338]Am I the only one that found this incredibly relaxing in addition to being interesting?[/QUOTE]
I'm happy to admit I have no idea what this is, and yet it just feels so...[I]satisfying[/I]. I can't quite explain.
Bogo sounds like a slowed down crazy bus theme.
This might explain a lot.
Ooh man, this is fucking awesome. The sounds make me think of this though
[quote][video=youtube;k18eKo7d0nA]http://www.youtube.com/watch?v=k18eKo7d0nA[/video]
[/quote]
They should've showed something like this in my high school's Computer Science class.
The subject went from mildly interesting to mesmerizing with the addition of video and sound.
Never knew watching a video about sorting out data could be so interesting to watch.
I came in expecting someone popping bubblewrap.
Is there somewhere where I can find more stuff like this?
Maybe I'm just going crazy but to me it sounded like I could almost hear the Super Mario theme during parts of the gnome sort.
[QUOTE=ThePuska;41697828]An efficient implementation of quicksort is probably the best generic comparison sort, though it's a very close competition with merge sort. Radix sort outperforms both of them at sorting integers because it's not a comparison sort, but an integer sorting algorithm.[/QUOTE]
It's really hard to get better than nlog(n) time on anything without having some specific information about what your data is. The fun stuff is when you get into non generic solutions, or situations where you don't actually need fully sorted information.
A major thing to consider (that is all too often overlooked) is what is the data like, and what information is actually important. Keeping heaps of some stuff is actually stupidly efficient if all you care about are top or bottom values, but it's not actually "sorted", more like organized. There is a surprising amount of data for which the most bog standard 2-5 line insertion sort does the job perfectly (IE data is almost entirely presorted and only needs a few elements, or new elements added into it). Even some tweaked bubble sorts have their places.
For example, if you know that no single element in an array is more than 10 places out of line, the most basic bubble sort can solve that in 10n time or better every single time. Straight up linear scaling is really hard to beat in those cases. A basic quick sort is usually going to be slower, even with extra checks to let it skip a lot of stuff, just because it wastes so much time moving elements around when they don't need to be moved around, and performing what end up being redundant comparisons because of the special cases that the data exhibits.
I can't seem to find it at the moment, but there was this excellent hour long video about this stuff that I found a few years ago. It did a great job of compressing an entire semesters worth of DSA into a well laid out overview.
[QUOTE=bisousbisous;41704939]Is there somewhere where I can find more stuff like this?[/QUOTE]
There's a program where you can set up your own random mix, pick a method, and watch it go.
[url]http://panthema.net/2013/sound-of-sorting/[/url]
Haha Bogo Sorting's hillarious
[QUOTE=Skyward;41705256]Haha Bogo Sorting's hillarious[/QUOTE]
I prefer Quantum Bogo
[quote]Uses true quantum randomness to randomly permute the list. The list is then inspected, and if it is not in order, the universe is destroyed. By the many-worlds interpretation of quantum physics, the quantum randomization spawns 2^N (where N is the number of random bits) universes and one of these will be such that this single shuffle had produced the list in sorted order.[/quote]
[quote]Bogobogo sort
is an algorithm that was designed not to succeed before the heat death of the universe on any sizable list. It works by implementing the Bogo sort on the first two elements in the list. If they are in order, then it Bogo sorts the first three elements, and so on, increasing by one until the entire list is sorted. Should the list not be in order at any point, the sort starts over with the first two elements.[/quote]
they had to work hard to make it that bad
[editline]4th August 2013[/editline]
im doing a bitonic sort with 2046 array size, lets see how long this takes
[editline]4th August 2013[/editline]
did a cocktail shaker w/ 2046 array size, 1400460 comparisons and 4203374 array accesses, goddamn
Bogo? Bo[I]gone![/I]
[img]http://i.imgur.com/ro4H4o2.png[/img]
It took like 5 minutes and over 312,257,979 accesses to sort 11 numbers.
I tried 15 but it was still going after 30 minutes and there were so many accesses that the counter in the program broke and rolled over into negative numbers.
So all you smart sorting people. Is there ever any reason to use bogo sort?
[QUOTE=Tinter;41707255]So all you smart sorting people. Is there ever any reason to use bogo sort?[/QUOTE]
Bogo sort is just a joke and more or less an example in programming/logic of what not to do.
[QUOTE=Recurracy;41707271]Bogo sort is just a joke and more or less an example in programming/logic of what not to do.[/QUOTE]
I know, but sometimes thought to be useless stuff actually have uses.
[QUOTE=Tinter;41707520]I know, but sometimes thought to be useless stuff actually have uses.[/QUOTE]
Abusing Asimov's laws of robotics to crash an AI
[QUOTE=bisousbisous;41704939]Is there somewhere where I can find more stuff like this?[/QUOTE]
He's got a playlist of more algorithms
[url]http://www.youtube.com/playlist?list=PLZh3kxyHrVp_AcOanN_jpuQbcMVdXbqei[/url]
[QUOTE=kaze4159;41707548]Abusing Asimov's laws of robotics to crash an AI[/QUOTE]
If somebody ever asks me why I don't fear an AI uprising I'll just tell them to watch bogo sorting.
My programming professor showed us this in class last year. To this day I'm convinced bitonic sort and radix sort are simply products of black magic.
[QUOTE=Tinter;41707520]I know, but sometimes thought to be useless stuff actually have uses.[/QUOTE]
There's a lot of useless joke algorithms and programming languages, [url=http://en.wikipedia.org/wiki/Malbolge]Malbolge[/url] springs to mind as it's one of the hardest languages to program in that was made for no other reason than to be impossible to program in.
[QUOTE=Smasher 006;41708935]There's a lot of useless joke algorithms and programming languages, [url=http://en.wikipedia.org/wiki/Malbolge]Malbolge[/url] springs to mind as it's one of the hardest languages to program in that was made for no other reason than to be impossible to program in.[/QUOTE]
The joke is that they actually failed to make it impossible.
[quote]The peculiarity of Malbolge is that it was specifically designed to be impossible to write useful programs in. However, weaknesses in this design have been found that make it possible (though still very difficult) to write Malbolge programs in an organized fashion.[/quote]
I might have a limited knowledge of algorithmic math and all, but couldn't a sort function be made that gives all of the values a once over and immediately sorts them? Even that quicksort thing took quite awhile to put all of the values in their place.
[QUOTE=Dalto11;41701338]Am I the only one that found this incredibly relaxing in addition to being interesting?[/QUOTE]
I was actually pretty disturbed by the sounds
bogo was the only one I would share some beers with
[QUOTE=U.S.S.R;41710021]I might have a limited knowledge of algorithmic math and all, but couldn't a sort function be made that gives all of the values a once over and immediately sorts them? Even that quicksort thing took quite awhile to put all of the values in their place.[/QUOTE]
No, your brain does a lot more calculations than you realize when you sort things.
[QUOTE=U.S.S.R;41710021]I might have a limited knowledge of algorithmic math and all, but couldn't a sort function be made that gives all of the values a once over and immediately sorts them? Even that quicksort thing took quite awhile to put all of the values in their place.[/QUOTE]
Well, it might work in this particular example, where we can make the algorithm know in advance the range of the values and the fact that the sorted array is meant to be a continuous sequence. It's not like that in general however. Also, the computer doesn't have the same "overview" capacity as your brain will have when looking at all the elements laid out in front of you. For example, your brain may be able to instantly recognize the smallest element in the bunch, but the computer has to look at each and every one and compare them in order to be sure.
Your idea is vaguely reminiscent of Insertion sort, which works like "take an element and put it in its correct place in the sorted part of the array".
i don't even care for sorting myself and i still find this incredibly fascinating
[QUOTE=U.S.S.R;41710021]I might have a limited knowledge of algorithmic math and all, but couldn't a sort function be made that gives all of the values a once over and immediately sorts them? Even that quicksort thing took quite awhile to put all of the values in their place.[/QUOTE]
That would fall into the realms of knowing special information about your data that I mentioned earlier.
Say you have 100 items, and they are valued 1-100, with no duplicates. You can look at a value and determine which slot to put it in instantly. This is obviously a very extreme example and is extremely rare outside of these little demonstrations, but you can frequently do little things to enhance performance on subsets of your data.
The problem is that these solutions are based on assumptions that are unique to whatever data you are working on. That means that they frequently become incredibly inefficient when things aren't aligned with what you think your data contains. They frequently require a lot of special debugging and general development time because of this, and they need to be redone, often in their entirety, if the scope of your task changes even remotely. The latter happens pretty much everywhere for everything. In general you are better off going with generic sorts because they are good enough, and far, far faster to implement.
Sorry, you need to Log In to post a reply to this thread.
