Why My Teenage Code Was Terrible: Sorting Algorithms and Big O Notation
Vložit
- čas přidán 5. 01. 2020
- When I was a teenager, I wrote some terrible code. Here's why. • Sponsored by Dashlane - for free on your first device @ www.dashlane.com/tomscott
MORE BASICS: • The Basics
Written with Sean Elliott / seanmelliott
Directed by Tomek
Graphics by Mooviemakers www.mooviemakers.co.uk/
Audio mix by Haerther Productions haerther.net/
I'm at tomscott.com
on Twitter at / tomscott
on Facebook at / tomscott
and on Instagram as tomscott
Dashlane continue to be a great sponsor for these videos! You can get their password manager for free on your first device at www.dashlane.com/tomscott - there's a 30-day free trial, and 10% off with my code, "tomscott"!
Dashlane more like Raid Shadow Legends. Am I right, or am I right?
You haven't pasted your code
How does Dashlane work if I split my time between home (where I have everything configured as I want), and the office (where there are MASSIVE security restrictions and I'm unable to install any software - including browser extensions)? By my understanding, Dashlane would auto-generate random passwords and store them at home - but I'd be totally unable to retrieve them from anywhere while logged on at work. Am I wrong?
Tom, could you do a deeper dive into Big O?
This video telling interns to do there work hmmmm “Tom hasn’t got an intern now?”
I usually clean my room with bogosort
fair enough
One man's chaos is another man's order.
what, toss everything around untill it happens to land in the right spot?
@@QueueWithACapitalQ Yep.
Trouble is getting the damn tornado started in your room...
@@MazeFrame and stopping it too
Bogosort has the possibility of sorting any list in 1 try, it's the most op.
It's that one superpower that never works.
Bubble sort can also do it with 1 try, if the list randomly happens to be in order to begin with.
@@konskift so not any list. Bogosort has the possibility to sort *ANY* list in one operation.
Just destroy all the universes where it incorrectly sorted. 100% success rate guaranteed.
The shuffle is still O(n) though.
I personally prefer quantum bogosort:
1. Randomize the list.
2. If it isn't sorted, destroy the universe.
In some parallel universe, it got sorted instantly, and that's good enough.
not bad.
Actually really creative. Thanks for this.
@@A1rPun Not actually my joke, but thanks!
you gonna need (n+1)! amount of parallel universe though
O(1/0)
>Select all
>FInd and replace every name with "content"
>Presto, everything has a technically correct description
Or just "image"
Or do it in SQL
got the reference bro. This is such a roast 😂
Ono...
Is it a ref to onosecond?
My favourite sorting algorithm still has to be miracle sort, check if the data is sorted, if yes, great, if not wait for a bit and check again...repeat. Eventually due to bit flipping or divine intervention the data will eventually be sorted...
It's hard to get reliable complexity estimates for it though...
What you need is my Quantum Unentangler™ - Put an end to entropy today!
You dont even need to wait, just check again! :)
To be fair near every problem in the universe will (theoretically) solve itself if you just throw infinite time at it.
if (list_sorted) return OK;
else return MEH;
I recently read a paper on a new linear sorting algorithm: It's called Stalin-Sort
It achieves this by simply eliminating any element that isn't in order.
Need to implement this for sorting bills for my chef!
Thats the funniest thing ive ever read on a sorting alg video
Stalin-sort, or little purgy, as I like to call it.
I've heard of Stalin Photoshop, it's main feature is that it's really good at removing people from pictures.
I wonder if Stalin sort isn't actually used in apps running over UDP, like games where you really only need to receive the latest position of your opponents
Got a funny feeling my brain is running on bogosort
That would explain _so much_ about me.
Thank you for giving me my new discord status
That's unfortunate for you, I'm definitely running in "Big O's"
*This* is your brain on bogosort
I prefer Schrodinger's sort: the list is sorted and unsorted, as long as if you never find out what the list actually is. No work required.
You cant verify if the list is sorted or not if you do not know the correct order of the list to begin with!
@@SpencerKaup This reply finishes the joke beautifully.
@@nutronstar45 👴
O(0) :D
@@nutronstar45 no, superposition doesn’t mean either, it states *both* are true
Like the double slit experiment
I actually implemented bogosort when I was bored at work once. I think it took about 6 hours to sort a list of 12 numbers.
lmao
thats actually a little slower than i would expect.
@@michaelwilkes0 it might have been a bit more than 12
@@tf2excession Yes, but how slow can it sort array {5} ?
Fran x1024 about 12 min 30 sec.
If it makes you feel any better my adult code is terrible
No-one wants to hear about your adult code, this is a family friendly channel!
@@Gamer-uf1kl I'm 25 and my code is terrible, just keep practising, you have a head start on most adults
There's ancient spaghetti code in production servers, if that gives you some comfort
FullNuclearBreakfast lmao!
Oh I can't even code.
As someone who develops for a living, I can tell everyone to never ever ever try to get clever for the sake of being clever. The end result is you solving a puzzle and a load of frustrated users that probably didn't get their needs met, and team members that now need to jump through hoops to support your code.
Well there's your problem, you have extraneous variables like users and team members :D
otacon1024 ikr? Who needs that? - Me, who can’t 3D model or do art
The KISS method is timeless. Keep It Simple, Stupid.
Always remind yourself that there is no point in reinventing the wheel.
@@otacon1024 As someone who has been writing software for quite a while, trust me, teammates are very much not a bad thing. Nobody knows everything. You can learn a lot from others and also they'll catch mistakes you might not have noticed
Users on the other hand...
I can not imagine Tom as a teenager, my brain refuses to.
As a teenager is easy. Before his voice changed, OTOH ...
He'd look the same anyway
Tom was born old. When he was delivered, he looked up to his mother and said: "Hello! Bit chilly in here, isn't it? Hand me some programming software, would you?"
I can't imagine him not as a teenager. To me he's *still* an excited teenager nerding out about stuff. (He's actually older than me...)
he will be forever 30ish I swear this doesn't really age that much
"They're not disenchanted enough with the world yet".
The most British sentence ever uttered, folks
Ignorance is bliss.
I don't agree, it is the most "work experience" sentence ever uttered. I say this as being from another country that has such a system.
@@Zorbeltuss Still sounds better than mine. I got sent to the local insurance company to do a presentation on a new security system. At a similar time to Tom by the sounds of it.
lads
@@dcarbs2979 I think you misunderstand, the whole motivation behind a work experience system seems to be "They're not disenchanted enough with the world yet" regardless of where in the world it is. I didn't say what mine was, or the severity.
I'm always amazed how Tom can do these videos in one take without a single stutter, pause or 'umm'
multiple takes
That's the power of having a script.
3:40
It also helps having such detailed knowledge of the subject matter.
@@Robtecz what are you implying happens at 3:40?
3:03 "each block bubbling up" I have a compsci degree but I've just now learned why it's called bubble sort...
We did this by hand, drawing circles (bubbles) round each pair of items that were being compared.
@Winston McGee tf was that for mate? No need to be an ass
I just learned Shell sort is named after its creator and has no association to physical shells
@@RochRich. I read this thinking of Mario Kart
"Randomise the list. Is it sorted?"
"How do I know if it's sorted?"
"Check it against some kind of sorting algorithm I guess"
checking if it is sorted can be done in O(n) time, by checking 2 items at a time and comparing them in order.
This reads like an xkcd joke 😂
for x in list: if x > x-1
while((b=(A[i]
all(L[i]
"It's the job you give the 'work experience' kid, because they're not disenchanted enough with the world yet." - might be the most cuttingly true thing Tom has ever said. Much love, Tom.
I spent two weeks measuring .22 bullets with a micrometre
what a boring work experience
Was 'shadowing' an engineer at a Warburtons factory. Not the greatest experience but I did get a tonne of free bread!
@@smithjjoseph eyyyy you got that bread then
ok i'll kms now bye
I managed to avoid my work experience, I thought the purpose of an adult was to hate work and not do any if possible, it would be several years before I made the realisation that I actually really enjoy work but just have severe social anxiety.
I got 1 week in two locations.
a local high end kitchen where companies offices, actually did work for a few days and sorted their files on the other days.
A local non profit, cut down invasive trees and put posters on their wall.
Loved the end. Hit the issue on the head.
Solutions are only good if they solve the problem that was asked.
Actually it is "solve the problem they intended to ask"
@@kensmith5694 can't emphasize this enough. Most users don't know how to articulate the problem.
@@kensmith5694 YES. We had a client once ask us to re-introduce a bug we just fixed because they didn't realize it was a bug, didn't know what was happening, and assumed the application was doing postal code validation that it absolutely wasn't. A co-worker just did what was asked, and when I saw his PR, I was like... "no. No, we're not doing this. Marking this as 'Needs Work' while I talk to the analyst." I explained everything to the analyst, asked him to pass it on to the client and then to give me a *really good reason* why we should put bugs back into our application. A day later, the client came back to us saying, "Oh, THAT'S what was happening? No, of course we don't want that!"
Step 0 of any requirement analysis is to assume the client/customer knows nothing about the application and then think about whether the requirements make sense as a use case behavior. Only then do you move onto step 1: actually starting development on the feature.
Fulfil the requirement, the whole requirement and nothing but the requirement. Next time they'll be more careful what they ask for.
@@timflatus
Chaotic Good? Is that you?!
2:02 “Complete with BLEEP BLOOP sound effects when I was, tiny.”
This made me really laugh. I will now forever refer to my childhood as,
“The Time I was Tiny”
That would work better if I was tiny as a kid (I was the "big-headed" one, literally) or if I grew up to be huge. Unfortunately, none of those are true.
I love how Tom asserts dominance by doing these videos in one take
1. Calculate a combination of elements & speed required for bogosort to complete a sort in approximately 1 year
2. Plug it in to a visualization with sound and begin sorting
3. Start a 24/7 Livestream
4. ???
5. Profit
Since you would be trying to visualize it, I wouldn’t recommend making your sort go too quickly. An 11 item list would take an average of a year at a little over 1 try a second.
If you tried 12 items in the list, you would have to try 15-16 times a second, which seems a bit quick to follow.
Plot twist: bogosort does it in 1 iteration.
@@theblinkingbrownie4654 Plot twist: it's rigged to get it sorted exactly after a year
yes
Are we talking mean sort time or median? The real question is what percentage of the time do you want it to terminate in less then a year vs over a year. If you make it 50% then there's 6.25% chance it runs for over 4 years.
Also, another limitation to remember with Big O notation is that some algorithms scale really well but are slower on smaller samples; and if you know you only need to deal with under a hundred items every operation but you need to do this a lot of times per minute, it might be better to use the algorithm that scales poorly but runs fast at that sample size.
Pick the algorithm that's right for your use case.
I “gotcha” a bunch of people with the question, “when would you use bubblesort?” It’s hard to think about the domain-specific conditions under which Bubblesort would actually be a useful algorithm, but I try and use it to point out that tools have their use, even if they can end up being super narrow.
Which ones Dare?
@@puellanivis, well, Bubble sort actually has an advantage that Quick sort fails at. if two items are considered equal, Quick sort might swap them, Bubble sort does not. So for example, take a vocabulary list that includes two items with different capitalization, like 'Frank' and another item 'frank', when your equality check is not case sensitive, then Bubble sort will keep the 'Frank' and 'frank' in the same order as it was originally, while Quick sort cannot be relied on at all for this.
@@humilulo That’s also a great point. There’s a quite a few cases where a language provides not just a `Sort` but a `StableSort` as well for this very reason.
But if know the problem is always smaller then X, then that steps becomes constant. It might add a scalar factor, but never more.
Quicksort may be O(n^2) in the worst case, but that's only if your list is already sorted (the wrong way). Interestingly, in the real world, this is highly likely to be the case, because any time a system touches data, it usually imposes order on it. So this is why it's recommended that every quicksort implementation be started with a shuffle. Once shuffled, it's nearly certain to be O(n*log n). And the shuffle itself is O(n) so it adds effectively nothing to the total time as long as your list isn't stupidly short.
Ah, the bogo-quicksort
Most quicksort implementations use a random pivot already, the likelihood of the pathologic O(n^2) case occurring isn't reduced rather it is evenly distributed across all input.
Other than that there is also a quicksort variant with worst case runtime of O(n*logn) which uses the median of medians method to guarantee the pivot is always "good enough", admittedly it has large hidden constant compared to randomized quicksort which is why randomized quicksort is the one most used in practice.
If you're interviewing candidates for an IT-related job, the most important question should be what the worst mistake they've ever made was. If they don't have an answer then they're either lying or inexperienced. If they give an answer then the level of detail they provide about why it went wrong and how it could have been prevented will give you more than enough of an idea of how capable they are.
Something else to keep in mind is that just because something has a worse complexity class, it doesn't mean it is slower. Or that an algorithm can have multiple complexity classes.
Bubble sort is O(n) in the best case, while Quick sort maintains O(n log n). If your list is already sorted, Bubble sort will figure that out faster than Quick sort.
A single Quick sort operation is also much worse than a single Bubble sort operation. While Quick sort scales better, Bubble sort is actually better for small lists. The default sort function in Java, for example, uses Bubble sort for lists of length 5 or lower, and Quick sort for anything else.
Sometimes O(n²) is better than O(n log n) - the complexity does not tell the whole story, it just focuses on how it scales.
The O() notation is about *statistical* performance, i.e. considering general cases, with a huge number of measurements.
Are you sure about that? The docs make no mention of of falling back to bubble sort, and while it makes sense to not use quicksort for small lists, insertion sort would almost certainly be better than bubble. The docs say quicksort for primitives but I know Java uses timsort for objects, which falls back on insertion below a certain length.
@@quinnbattaglia5189 I know that std::sort is definitely a quicksort that instead uses insertion sort when the list gets small.
@@mynewaccount2361 That's what I assumed java did, but I did some more research, and apparently the "Dual-pivot Quicksort" java uses for primitives chooses between quick, merge, insertion, and counting sorts based on the length of the list and type of the array.
Use insertion sort instead of bubble sort for small lists
...or, as Donald Knuth had it: "the fastest code is the code that never runs".
Smart Human.
A good developer can write an efficient sort algorithm. A great developer just uses the system libraries.
I came up with a sorting algorithm that runs in O(1)
Stalin Sort:
1. Declare input list to be sorted
2. If user complain, send to gulag.
list.sortstate=true;
if (complain==true) {
return(gulag(user))
}
@@niklasschmidt3610 Error: gulag is not defined.
Error: memory out of range
Back in my undergrad days I earned a bit of extra money working in the library. Part of this was sorting books prior to putting them back on the shelves. My colleagues used insertion sort. I used quicksort.
Happy new year!
I used the built-in sorting method and still don't know if it's fast or slow
Nowdays the bots all sort the books for the librarians.
@@bananya6020 yes but those sorting bots are still using a sorting algorithm
@@tpdabomb3 i was just thinking how we have fully automated libraries now so the difference between insertion / quick not so big
I used to use merge sort. Nowadays, for sorting ~150 items, I apply domain-specific knowledge and do a few levels of bucket sort, followed by insertion sort once the piles are small enough.
Is school: Why do I need to learn this?
Now: It’s kind of nice knowing if this will take 10 minutes or if the expected time is a week and I should fix the code instead of waiting.
You learned Big-O notation at school? Very nice. I wish I had learned it in school too.
@@aikslf fam its second semester of computer science a. Near the end i think
Adi Septiana for me, isSchool() == false
Bogosort is like a move in a video game that has a 10% chance to insta-kill an enemy.
It would probably be "randomly set enemy HP to a value equal or less to their max HP", meaning that it would be a 10% instakill on a 10 HP enemy or 1% on a 100 HP enemy.
The best sorting algorithm is obviously the intelligent design sort, which is instantaneous as given any random list of items, the algorithm simply returns the unaltered list, saying it must have been put in that order by a higher power which is the correct order and no further examination is required.
I took a highschool class on web design once, even got certified for it. all I remember now is how to make your background pink and your text comic sans.
And it was likely wrong/out of date too!
The number of sites online still telling people to use bgcolor and font tags... 😡
2001 called
@Mäander *s h u t*
Who would want comic sans in their website?
@@francescoaiazzone who wouldnt? please hire me for web design 😊
One Cut. Very impressed!
You joined YT 11 years ago and you're at 111K subs as of now. Nice.
Edit : And this video is 11 months old... Ok...
@@jimhalpert9803 and now your reply is 11 months old
@@jimhalpert9803 and now you have 11 likes. Nice
Gets defeated by the sponsor
The best solution isn't always the fastest or the smartest, its the one that works for everyone. BRILLIANT!
When I was 14 my website stored passwords, comments, and profile names/descriptions in plain text
In a text file everyone can see
"stored passwords in plain text"
You have committed a felony, please come with me to the Supreme Computer Science Court where you will be judged for your crimes
So now that you've encrypted your passwords, do you still use the same ones.
@@charlesgantz5865 I had to shutdown the website when I was 16
@@bbqgiraffe3766 To bad.
Disappointed not to hear the “ONE TAKE” screech at the end of the video
Probably the 2^256th take
I’m 39 years old, and I miss “utterly unjustified confidence”.... sigh, the nostalgia.
ok boomer
@@4everparky If SETI was searching for intelligent life from CZcams comments, they would be just as succesful ...
I'm 18 years old and I've never even been confident in my ability to chew
@@thekingoffailure9967 You're in a good place. Your confidence will gradually build up as you learn and practise things, and will always scale directly from your abilities. This will have you automatically sidestepping a lot of problems with overconfidence and the dumb mistakes that result from it.
I'm guessing what you have now is "utterly unjustified lack of confidence", which is just as bad, except it's also worse for your self-esteem.
It's sometimes counterintuitive, but the most common lesson I have to teach graduates coming into our industry (Game development) is that a lot of those nice fancy algorithms that are Nlog(N) and similar - frequently are not the best choice in practice. Most of the datasets we deal with are actually tiny, you'd be amazed how frequently replacing a smart hashmap with a dumb array and some brute force, or a quicksort with an insertion sort (or ideally, Introsort) saves a huge amount of time when you're not dealing with thousands of elements.
The biggest issue i struggle with as a CS student is trying to come up with the " perfect " solution , while there is none , and ignoring the simplest solutions , just because they seemed " Too easy "
"So that the teachers have a break". You sunshine are having a laugh. What it actually meant was driving round the locale, checking up on the kids, finding things to do with the ones that got fired, filling in forms with feedback from the companies, fending off calls from parents complaining that their kids hadn't got suitable placements, chasing up the ones that just went missing. And all that was at the "good" grammar school I was teaching at.
"Why teachers complain about their wages, they get the summers and weekends off!" People having a giggle, I tell you.
To be fair at my school I did work experience was on a construction site opposite a pub, it was all of us working on the same site which is probably illegal but anyhow every day we seen the entire teaching staff, in the pub from midday onwards. I guess it can depend on the school and how exact they tend to be.
Judging by the other responses here. Aye that was a good grammar school.
Don't forget: Teach the other classes in the meantime.
Ever heard of a joke?
If Tom Scott explained every programming concept I ever struggled with, I would no longer struggle.
When I was in high school, I was in charge of sorting in the largest online image gallery of a certain TV show that was popular, but also slightly obscure enough that we could be completely sure that it was in fact the largest gallery of images from that show and it's corresponding merchandise on the web at that time.
I created folders and subfolders, probably the most folders. Nothing had tags, so I had to organize one by one into the correct folders and subfolders that I came up with. I could move files that were sent to my section and create and delete folders, but not change any base code. I was excellent at it and thought about what would be most efficient as I sorted away.
This wasn't for school or anything and I'm sure it'll help everyone sleep at night knowing that the gallery was last forever after it was put on temporary hold while a Google search consultant was organizing a site revamp and the owner died. I spent two or three years of my free time on that.
My Electronic heart just died witnessing this tragedy
Years of programming later my technique is now
1. Does my this need a tree?
2. Does my thing need a linked list?
3. If no to the above, screw it, quicksort. I aint got time for the rest.
As a software developer in the 70's I realised most of our problems - AND we had a lot, were caused because we didn't really understand what the client really wanted. After several meetings and arguments we decided to implement a "system" to overcome this. To most peoples astonishment our software quality made an order of magnitude improvement over night. We produced software much quicker, we developed it much cheaper, and more importantly it worked and did what it was supposed to do. Not rocket science but even today an important factor all too often missed by "smart" programmers, (and development managers). Nice video Thanks.
I'm curious, what kind of system did you implement ? I feel like this kind of communication problem will always be a big issue.
@@enjaad1654 We developed automated industrial control systems. Automated machines and robots used in a variety of industries. Later I became a software quality control consultant.
@@rickharriss Thank you very much !
Tom, this might actually be the last recorded time that an end user actually knew exactly what they wanted!
Bubble Sort, although yes has an exponential algorithm of O(n^2), you can make more efficient. Since you're "bubbling the largest to the top", or shifting your elements right, for each subsequent pass you don't need to compare the last elements because they're already sorted. For each "and then you do it again", you subtract 1 from the length of the list. Because you keep subtracting one, each subsequent "sort" is performed on a smaller list, therefore making it quicker to progress through.
In short: There's no point in trying to sort things you've already sorted. You know the largest elements are at the end of the list, so don't bother with them on subsequent passes.
This is what I thought bubble sort was which you just described, but after watching the video I found out people check the entire array for each iteration 😕
it is still O n^2
@@DanielQRT Yep
square != exponential
That reduces the number of iterations by about 1/2 but that still makes it an O(n^2) sorting algorithm. I presume if it is used it is used like that though. It'd be really dumb to double the sorting algorithm's run time to avoid doing the linear process of counting down the sort length.
When I saw Tom Scott and “My Teenage Code” and “Bogosort” I cried
"Should have done what the client asked for"
if they were actually clients sure.
Giving that job to a work experience kid would be illegal in Australia because its a waste of work experience
Here the whole idea of work experience is to give menial unfulfilling jobs, with the implicit message that if you stay in school and do well you can avoid this sort of work later.
How does Australian work experience differ?
If Tom learned a lesson which was of value later in his career, it wasn't a waste.
@@gvigary1 That lesson is that work experience can be bs
Work experience is exactly that, experience of what it is like to be in a workplace, the work you do will be pointless as it is not long enough to train you...
You have my gratitude for removing the inevitable CRT whine that was in this video
Adult me: Eh, at least you could do a bit of coding at that age!
Teenage me: **chortles every single time Tom said "Big O"**
I Love this series Tom! Please keep going. As a Junior Software engineer almost finished with university i Love going Back to the basics and love your personal touch.
When I was about that age, I came up with a sort algorithm, it had a run time of n! x 2^n .
I’d like to know what it was like lmao
Exact code, Python3
@@donaldhobson8873 sure
(I am assuming that is a question to seek confirmation since I do not see the code anywhere at the moment)
@@rcksnxc361 It's a year later, and the code that Donald Hobson wrote to paste the code here is still running.
Knowing about Big O and runtime and so on is one of those things in computer science that you hardly ever really "use" (and it gets fuzzy really quickly if you think about it too hard) but knowing about it makes you think about problems in a totaly different way. And I like the remark at the end about premature optimization :-)
The fact you do these videos in one single shot is why I enjoy watching them so much. That, and the content is always interesting!
As a software engineer who takes the quality of my work seriously, I have mixed feelings about this. There are times when I _have_ had to tell clients to suck it up and learn how to use the thing I made for them, because it was in fact better than what they asked for _and would scale with the growth of their workload over time._ Clients know what they want, and on rare occasion they might have even figured out what they need _today_ -- but they almost never know what they _will_ need _next year._ Just because the world operates on a "no time to do it correctly, we'll just re-do it later" mentality, that doesn't mean professionals have to enable that mentality.
"Ah, that case will never happen" means usually that it will happen next week and if you did not design your software for this case, there will be a problem.
And you, the almighty star programmer, know for them? lmfao
Questionable pfp
@@julianegner5997 That is when you explicitly disallow that case, along with a warning message "That operation is not allowed per company request". Then it isn't a bug.
And yet despite being right you still in the wrong here at the bigger picture
I remember trying to code a 'quick' sort at computer science a level which took ages and didnt really work for a lot of different tests.
Well for one thing for n < 10, bubble sort is the fastest algorithm. Most sorting algorithms are thus a hybrid. Well actually since one rarely starts with a pile of unsorted data, but rather you acquire data "on the fly", the most sorting algorithms are binary search INSERT algorithms -- but even there for n < 10 (or so) the linear search is fastest. So you go recursive for a while, but *well* before you hit n==1 or n==0, you switch over to something seemingly stupidly dumb as the seemingly stupidly dumb algorithms run really fast for small data sets.
@@jamestanis3274 Bubble sorts are definitely easy, I did one at GCSE and from then on used the built in sort or fastest as often was a quick sort.
@@leo_warren Please forgive me, but I'm having a bit of trouble understanding what you meant (and as a CS major I *am* interested) but as Tom points out, quicksort is still O(n^2), so it's still a slow sort (in the average).
Quicksort is n^2 worst case. n * log(n) in the average case.
"Real world" implementations of sort functions are almost never quicksort-like, but it is a nice one to use in education, because it's relatively easy to understand and implement compared to the ones that have n * log(n) worst case performance.
I have a friend who is still trying to come up with improved pivot selection algorithms. It is amazingly hairy to re-implement it decently :-)
2:50 Bit to add here, in computer science class we learnt that once you have sorted the biggest and put it at the end (here anyway), you don't need to check it again, so you stop checking pre-sorted sectors. I've never actually PROGRAMMED a bubble sort, but that's the theory we learned anyway, this would be much more efficient. Still though, correct me if i'm actually wrong.
That's true, and in the best case it halves the run time. The problem is, it's still O(n²), so it's still gonna take forever when you have a lot of list elements. If you double the size of the list, it quadruples the run time. So if it takes 15 seconds to sort 10000 elements, it will take 60 seconds to sort 20000 elements, and that's just unusable.
@Nikhilesh Kumar Malik n! is 1*2*...*n, while the complexity of the algorithm is 1+2+...+n
Unknown Person It’s approximately O(n^2/2) but the constant tends to get dropped in big O notation, so it becomes O(n^2)
Definitely true. Actual cost is n(n-1)/2, the classic "triangular" loop cost. In the grand scheme of things there's still an n^2 in there though, and we just ignore the rest.
It would still be O(n^2) unfortunately
Tom you never cease to teach me something new, thank you.
Why is it that “big O” is all anyone talks about on the internet but in college we didn’t even use it at all. We used theta notation exclusively.
Probably a mix of common misconceptions and the fact big O is the upper bound (as that is usually what people care about). Typically online people use big O as theta notation (which is still true because a complexity in big theta notation implies that same complexity in big O as well as big omega (the lower bound)). A potential issue with this misconception is that they might get confused by the fact that if an algorithm has O(n) complexity it also has O(2^n) but typically these types of observations aren’t brought up because they aren’t relevant (because it is a upper bound, all complexities with faster growth rates are also upper bounds).
I recently watched Ted-ed's video about the fastest way to sort books, and I was happy to realize that the same concept is used in programming! Thanks for the great video!
I LOVED the conclusion ! "Do what's NEEDED, not what you think would make you look cook". Sure, your software might be cool or whatever, but the client just wants something that works for them !
This is an incredibly well timed video for someone going into a second semester programming course starting yesterday
I love the message at the end of the video about what you should have done. It highlights the importance of the goal. If your goal is to show-off, you are going to think very differently than if your goal was meeting client needs. There is a time and place for most things, so make sure you're setting the right goal for the job and it's constraints. At work and in real life.
Tom's facial expressions while storytelling are just one of a kind! ❤️
You are incredibly humble. You use your mistakes as a learning experience and have no problem using your own mistakes to teach others. Thanks, Tom.
Bogos sorted?
An exceptionally good episode! It reflects exactly how it works and shows what you need to learn and cover in the "real" world. This video is an example which I like to share regardless of the profession.
That is one of the most important engineering and development lessons: do what is the best solution for the user.
0:10 American schools have “work experience” as well for their older students. It’s called different things in different districts. Mine was called CWE (Continuing Work Experience). It wasn’t an internship because it was just an entry level job in retail or food service for most of the kids. But it got them out of the school and making some money for a few hours work a day.
This video came with perfect timing for me. We are just now starting to learn different sorting algorithms in my AP Computer Science A class.
Love your videos Tom! Keep them coming!
It's so weird i was thinking about sorting algorithms the whole day and you uploaded a video about it now
"Do what the client asks for"
I have to tell people that so often! So many developers think they can do the job faster by themselves and turn in something that doesn't do what the client wanted
At uni (software engineering), any deviation from the instructions that were given to us (often, multiple pages of text) would result in an immediate 0% score on that task.
That's how we learned to be disciplined. And now, it sucks working with any non-software-engineering people, because they always let stuff slip between the cracks. You can never give them a list of 20 points and expect them to do all 20 in the way and order that was asked.
I have heard of big O notation before but couldn’t really wrap my head around it until this video. Thanks!
You do such a outstanding job explaining these concepts compared to some popularized books. 👏🏻
I misheard that as, "When I was 50" and was going, "Ok wait HOW old are you for that to be a teen!? Are you secretly the Norse God of Red Shirts!?"
Two days work experience? Our teachers got rid of us for a whole fortnight.
During the Brazilian World Cup, I came up with a few variations of the tournament sort before I knew what the tournament sort was, as well add a few newt features to it (which ultimately slow the algorithm down a bit but provide some neat information).
3:13
That animation with that hand movement was so satisfying!!!
Besides just being a generally amazing explanation of Big O, thank you so much for that ending. I can imagine many CS students stumbling upon this video, and they should really hear this
It was not a "amazing explanation." This video does not even teach you what "Big O", even is.
Tom you are such an amazing inspiration to me! Thank you so much for making these videos and the linguistics ones and others, as a 13 year old who's been coding for 3 years you've given me loads of inspiration, thank you so much!
Wow I love your final answer for the best solution being the one that works for everyone!! So very true!
i have been obsessed with watching sorting algorithms recently but i didnt really know anything about them so this was a really cool watch !!!
"The big problem wasn't that I used a bad algorithm, the big problem was that I was ignoring what my users actually needed because I wanted to show off how clever I thought I was"
I'm seriously printing this quote and putting it up on my desk as a jab to some assholes I have to deal with.
I feel like I finally understand what my teacher's trying to say 2 years ago.
That was super interesting! I know nothing about computer science, but I know this notation from when you taylor expand some function and want to express how large the error is/at which degree you stopped the taylor polynomial. Had no idea it was used for this stuff as well.
Thanks, I use dashlane for more than 2 years and I am very happy with it. It is really nice to have relevant sponsors like this. Nice video
There is an oversight/improvement in the animation of Quicksort. You don't need to look at any pivot element ever again after splitting the list because you know they are in the correct position
This video and the one about Turing machine are gold for me.i currently studying for my master degree in computer science and network security the network part isn’t a problem at least not like the computer part. I have a module about turning machine RAM complexity and O notation and i literally don’t have any idea about those things but after ur videos i feel like there’s a hope after all .thx
I really needed this today! Thanks!
Wow. Hit me right in the premature optimization.
In my heart, the best sorting Algo still is Sleep Sort ;)
Great intro to big O. Simple to understand and with nice visual aid. I have you do more programming basics videos.
Currently learning this in discrete math. It’s a blast seeing why my quintuple for loops makes things run in slow motion.
As a former teacher I can confirm the two weeks when an entire year group of snotty kids, I mean delightful teenagers, was out on work experience was like a mini-holiday. And yes, I know, as a teacher I had plenty of holiday anyway. The payback was every teacher had to go and visit at least two of the pupils at their placement to see how they were getting on, but that was also a rare trip out of school and meant we could get some shopping in or have a coffee.
Before this Derek told to use lastpas and now you're saying dashlane.. what to do??
Idea:
I'll use dashlane to protect my lastpas master password 👍
Best video on sorting Algorithms I've seen
Kudos Tom!
I did work experience here in Australia, did it at an electronics company. I sat on a solder sucker for 5 days...but learned heaps and a bridge rectifier in action is so much easier to understand