[QUOTE=CanadianBill;44335648][media]http://www.youtube.com/watch?v=kPRA0W1kECg[/media][/QUOTE]
this must be what alien speak sounds like
I'd like to see a video like this but with Bogo Sort
[url]http://en.wikipedia.org/wiki/Bogosort[/url]
[QUOTE=nerdster409;44335056]I always wondered what quick sort was. Never thought about it being recursive.[/QUOTE]
Most sorts can be thought of recursively. Recursive versions can also be easier to write.
Iterative versions of anything are generally better though because you don't have the overhead of method calls / the stack
I feel like I'm learning these algorithms subconciously by watching/listening to this.
Edit: oops I mean the 15 alg video
[QUOTE=Llamaguy;44335932]I'd like to see a video like this but with Bogo Sort
[url]http://en.wikipedia.org/wiki/Bogosort[/url][/QUOTE]
[media]http://www.youtube.com/watch?v=kcPFxKVu8T4[/media]
repeat until in order
[QUOTE=sirdownloadsalot;44337068][media]http://www.youtube.com/watch?v=kcPFxKVu8T4[/media]
repeat until in order[/QUOTE]
With a pack of cards, you have a one in 80,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000
Chance of getting it in order.
that's more atoms than there are in the universe..
[QUOTE=cherry gmod;44338180]With a pack of cards, you have a one in 80,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000
Chance of getting it in order.
that's more atoms than there are in the universe..[/QUOTE]
Math is nuts
[QUOTE=Llamaguy;44335932]I'd like to see a video like this but with Bogo Sort
[url]http://en.wikipedia.org/wiki/Bogosort[/url][/QUOTE]
[video=youtube;DaPJkYo2quc]http://www.youtube.com/watch?v=DaPJkYo2quc&list=PLZh3kxyHrVp_AcOanN_jpuQbcMVdXbqei&index=22[/video]
One caveat; it does sorta matter how you pick your pivot point. If your algorithm always picks the lowest or highest number, the algorithm degrades into O(N^2) efficiency. There are ways to guarantee that your pivot is decently chosen.
Imagine that you always chose the first element to be the pivot, and the numbers are in reverse order. Imagine what that'd do.
Quantum Bogosort, the only sorting algorithm with a constant time best case complexity
[QUOTE=DoctorSalt;44340951]One caveat; it does sorta matter how you pick your pivot point. If your algorithm always picks the lowest or highest number, the algorithm degrades into O(N^2) efficiency. There are ways to guarantee that your pivot is decently chosen.
Imagine that you always chose the first element to be the pivot, and the numbers are in reverse order. Imagine what that'd do.[/QUOTE]
Every algorithm has it's downsides, just because it's called quicksort doesn't mean it'll always be the the best one.
[editline]25th March 2014[/editline]
[QUOTE=sloppy_joes;44341484]Quantum Bogosort, the only sorting algorithm with a constant time best case complexity[/QUOTE]
That's the one where we randomize the array and if it's not sorted we destroy the universe right?
The logic goes that in the universe we destroy causality ends so it doesn't matter, but in at least one of the (theoretically) infinite universes it was sorted, perfectly, first try, and only those universes continue existing, so functionally it always sorts the table first try.
[QUOTE=Empty_Shadow;44341620]Every algorithm has it's downsides, just because it's called quicksort doesn't mean it'll always be the the best one.[/QUOTE]
You could randomize the pivot point, or attempt to efficiently find the midpoint by choosing n random elements and making the pivot the midpoint of those elements.
[QUOTE=DoctorSalt;44351174]You could randomize the pivot point, or attempt to efficiently find the midpoint by choosing n random elements and making the pivot the midpoint of those elements.[/QUOTE]
with a sufficiently large unsorted list, the chance of continuously picking the smallest or largest element as the pivot is pretty small.
Quantum Bogosort
1. Shuffle the list randomly.
2. If the list is sorted, stop.
3. If it isn't sorted, destroy the entire universe.
[QUOTE=sloppy_joes;44341484]Quantum Bogosort, the only sorting algorithm with a constant time best case complexity[/QUOTE]
Nope, it's O(n) not O(1).
[QUOTE=Ziks;44353468]Nope, it's O(n) not O(1).[/QUOTE]
Oops you're right I just looked it up.
[QUOTE=sloppy_joes;44353531]Oops you're right I just looked it up.[/QUOTE]
Although it's pretty embarrassing that even with the capacity to instantaneously destroy the entire universe we can't implement a sorting algorithm faster than O(n).
[QUOTE=sloppy_joes;44352422]with a sufficiently large unsorted list, the chance of continuously picking the smallest or largest element as the pivot is pretty small.[/QUOTE]
Without a randomized pivot point an adversary could choose a list of numbers that results in worst case sorting time.
Just studied this at uni about 2 weeks ago, this video might be able to help some of the guys in my course that still dont understand but im kind of afraid that it might just confuse them more..
[QUOTE=DoctorSalt;44357602]Without a randomized pivot point an adversary could choose a list of numbers that results in worst case sorting time.[/QUOTE]
I was agreeing with you, I think there was a misunderstanding.
what the fuck are you guys talking about
what does any of this shit mean
[QUOTE=Rediscover;44363035]what the fuck are you guys talking about
what does any of this shit mean[/QUOTE]
wizardry is real. tell your friends
Sorry, you need to Log In to post a reply to this thread.
