Sorting: Ep 11 - Bogosort


Uploaded by lcc0612 on 09.02.2010

Transcript:
Hello YouTube and welcome to the last episode of Sorting Algorithms
Today I have a very special sorting algorithm to show you
The nature of this algorithm prevents me from doing it on the computer
This only works in real life
We'll only sort one suit out of an entire deck of cards
This is how the algorithm works
Toss the cards into the air, and they will fall in a random order
Then pick up the cards to see if they're in the correct order
If not, pick up the cards, and repeat the process over
This sorting algorithm is called Bogosort
Without further ado let's begin with the demonstration
That was a messy throw, but nevermind - We'll open the first card
It's a five... I don't think our deck of cards starts with a five
Nevermind, let's check another one
It's a nine - Not sorted. We'd give it another throw.
First card... four
I don't think so...
J? Nah, totally wrong.
First card... J? Naah.
Let's see...
Oooh, an A, our list does start with that!
2! ... 3! ... 4!
Wow! It's all correct! This is an example of a successful Bogosort!
You may be wondering how the Bogosort fares under the Big O Notation
Well, it has the most amazing timing of all...
O(infinity)
Yes, as you can see, there's no saying when bogosort will complete
It could possibly take forever!
Now, Bogosort does indeed exist as a sorting technique, but only in schools, presented to beginners in sorting
Bogosort is a demonstration of why it is important ot have efficient sorting algorithms!
As you can tell, an algorithm of infinite time is absolutely impractical!
So there you have it - A demonstration of an extremely impractical sorting algorithm
And that's all there is for this series
Thanks for following through it from start to finish
You're watching 0612 TV