Why My Teenage Code Was Terrible: Sorting Algorithms and Big O Notation

[@TomScottGo]

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"!

[@waffleen]

Dashlane more like Raid Shadow Legends. Am I right, or am I right?

[@teamgb692]

You haven't pasted your code

[@ChrisMelville]

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?

[@lonjohnson5161]

Tom, could you do a deeper dive into Big O?

[@clearcontentment3695]

This video telling interns to do there work hmmmm “Tom hasn’t got an intern now?”

[@dwavenminer]

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...

[@rmsgrey]

It's hard to get reliable complexity estimates for it though...

[@krashd]

What you need is my Quantum Unentangler™ - Put an end to entropy today!

[@RolfRBakke]

You dont even need to wait, just check again! :)

[@hkr667]

To be fair near every problem in the universe will (theoretically) solve itself if you just throw infinite time at it.

[@epiendless1128]

if (list_sorted) return OK; else return MEH;

[@TheSecondVersion]

>Select all >FInd and replace every name with "content" >Presto, everything has a technically correct description

[@njdotson]

Or just "image"

[@TheManchineel]

Or do it in SQL

[@bernardoborges8598]

got the reference bro. This is such a roast 😂

[@superslimanoniem4712]

Ono...

[@codinghub3759]

Is it a ref to onosecond?

[@howdenking]

Bogosort has the possibility of sorting any list in 1 try, it's the most op.

[@bananya6020]

It's that one superpower that never works.

[@konskift]

Bubble sort can also do it with 1 try, if the list randomly happens to be in order to begin with.

[@thedead456321]

@@konskift so not any list. Bogosort has the possibility to sort *ANY* list in one operation.

[@AmeshaSpentaArmaiti]

Just destroy all the universes where it incorrectly sorted. 100% success rate guaranteed.

[@fluffycritter]

The shuffle is still O(n) though.

[@willjones8849]

Got a funny feeling my brain is running on bogosort

[@Wubbazt]

That would explain _so much_ about me.

[@CaTastrophy427]

Thank you for giving me my new discord status

[@auralunaprettycure]

That's unfortunate for you, I'm definitely running in "Big O's"

[@fubbernuckin]

*This* is your brain on bogosort

[@QuantumQuantonium]

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.

[@SpencerKaup]

You cant verify if the list is sorted or not if you do not know the correct order of the list to begin with!

[@lamenwatch1877]

@@SpencerKaup This reply finishes the joke beautifully.

[@srimpingkid3490]

@@nutronstar45 👴

[@yama123numbercauseytdemand4]

O(0) :D

[@theomni1012]

@@nutronstar45 no, superposition doesn’t mean either, it states *both* are true Like the double slit experiment

[@BadgerStyler]

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.

[@GuRuGeorge03]

lmao

[@michaelwilkes0]

thats actually a little slower than i would expect.

[@BadgerStyler]

@@michaelwilkes0 it might have been a bit more than 12

[@Franx-bd8om]

@@tf2excession Yes, but how slow can it sort array {5} ?

[@emadgergis6710]

Fran x1024 about 12 min 30 sec.

[@hangkikuta6786]

I usually clean my room with bogosort

[@bananya6020]

fair enough

[@hkr667]

One man's chaos is another man's order.

[@Queue3612]

what, toss everything around untill it happens to land in the right spot?

[@MazeFrame]

@@Queue3612 Yep. Trouble is getting the damn tornado started in your room...

[@bananya6020]

@@MazeFrame and stopping it too

[@shookings]

"They're not disenchanted enough with the world yet". The most British sentence ever uttered, folks

[@Schattengewaechs99]

Ignorance is bliss.

[@Zorbeltuss]

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.

[@dcarbs2979]

@@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.

[@mairacristian54]

lads

[@Zorbeltuss]

@@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.

[@JouvaMoufette]

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.

[@mediahighlights-r1w]

Well there's your problem, you have extraneous variables like users and team members :D

[@palmberry5576]

otacon1024 ikr? Who needs that? - Me, who can’t 3D model or do art

[@Efflorescentey]

The KISS method is timeless. Keep It Simple, Stupid.

[@maythesciencebewithyou]

Always remind yourself that there is no point in reinventing the wheel.

[@JouvaMoufette]

@@mediahighlights-r1w 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...

[@gaelansteele9224]

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.

[@lafeo0077]

not bad.

[@A1rPun]

Actually really creative. Thanks for this.

[@gaelansteele9224]

@@A1rPun Not actually my joke, but thanks!

[@brambl3014]

you gonna need (n+1)! amount of parallel universe though

[@Xnoob545]

O(1/0)

[@DerKlappspaten]

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.

[@pimp2570]

Need to implement this for sorting bills for my chef!

[@jimothyus]

Thats the funniest thing ive ever read on a sorting alg video

[@oz_jones]

Stalin-sort, or little purgy, as I like to call it.

[@djoakeydoakey1076]

I've heard of Stalin Photoshop, it's main feature is that it's really good at removing people from pictures.

[@110110010]

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

[@spacecasejay]

If it makes you feel any better my adult code is terrible

[@fullnuclearbreakfast]

No-one wants to hear about your adult code, this is a family friendly channel!

[@Cemtexify]

@@Gamer-uf1kl I'm 25 and my code is terrible, just keep practising, you have a head start on most adults

[@Nadia1989]

There's ancient spaghetti code in production servers, if that gives you some comfort

[@sm7085]

FullNuclearBreakfast lmao!

[@captainrobots1]

Oh I can't even code.

[@theaidanator]

I'm always amazed how Tom can do these videos in one take without a single stutter, pause or 'umm'

[@garret1317]

multiple takes

[@RialuCaos]

That's the power of having a script.

[@Robtecz]

3:40

[@ditzfough]

It also helps having such detailed knowledge of the subject matter.

[@ABLEARC]

@@Robtecz what are you implying happens at 3:40?

[@hiqwertyhi]

3:03 "each block bubbling up" I have a compsci degree but I've just now learned why it's called bubble sort...

[@tompw3141]

We did this by hand, drawing circles (bubbles) round each pair of items that were being compared.

[@tomkab7976]

@Winston McGee tf was that for mate? No need to be an ass

[@RochRich.]

I just learned Shell sort is named after its creator and has no association to physical shells

[@FarmYardGaming]

​@@RochRich. I read this thinking of Mario Kart

[@MrBLARG85]

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”

[@PravinDahal]

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.

[@Joe0400]

Loved the end. Hit the issue on the head. Solutions are only good if they solve the problem that was asked.

[@kensmith5694]

Actually it is "solve the problem they intended to ask"

[@RadiationOverdose]

@@kensmith5694 can't emphasize this enough. Most users don't know how to articulate the problem.

[@IceMetalPunk]

@@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.

[@timflatus]

Fulfil the requirement, the whole requirement and nothing but the requirement. Next time they'll be more careful what they ask for.

[@scalesconfrey5739]

@@timflatus Chaotic Good? Is that you?!

[@Jim73]

"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.

[@artski09]

I spent two weeks measuring .22 bullets with a micrometre what a boring work experience

[@smithjjoseph]

Was 'shadowing' an engineer at a Warburtons factory. Not the greatest experience but I did get a tonne of free bread!

[@bananya6020]

@@smithjjoseph eyyyy you got that bread then ok i'll kms now bye

[@krashd]

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.

[@caijones156]

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.

[@F1onan]

I love how Tom asserts dominance by doing these videos in one take

[@johnnye87]

"Randomise the list. Is it sorted?" "How do I know if it's sorted?" "Check it against some kind of sorting algorithm I guess"

[@AlexWohlbruck]

checking if it is sorted can be done in O(n) time, by checking 2 items at a time and comparing them in order.

[@katyungodly]

This reads like an xkcd joke 😂

[@typecasto]

for x in list: if x > x-1

[@atzuras]

while((b=(A[i]

[@joeybf]

all(L[i]

[@drewmandan]

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.

[@kekchanbiggestfan]

Ah, the bogo-quicksort

[@natnial1]

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.

[@daredaemon8878]

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.

[@puellanivis]

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.

[@horserage]

Which ones Dare?

[@humilulo]

@@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.

[@puellanivis]

@@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.

[@AsAMonkeyInAPinata]

But if know the problem is always smaller then X, then that steps becomes constant. It might add a scalar factor, but never more.

[@CalvinsWorldNews]

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.

[@marsgal42]

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!

[@li_tsz_fung]

I used the built-in sorting method and still don't know if it's fast or slow

[@bananya6020]

Nowdays the bots all sort the books for the librarians.

[@tpdabomb3]

@@bananya6020 yes but those sorting bots are still using a sorting algorithm

[@bananya6020]

@@tpdabomb3 i was just thinking how we have fully automated libraries now so the difference between insertion / quick not so big

[@rmsgrey]

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.

[@MegaFPVFlyer]

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

[@chompyzilla]

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.

[@theblinkingbrownie4654]

Plot twist: bogosort does it in 1 iteration.

[@Mkemcz]

@@theblinkingbrownie4654 Plot twist: it's rigged to get it sorted exactly after a year

[@jimhalpert9803]

yes

[@solsystem1342]

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.

[@MoistMoments]

The best solution isn't always the fastest or the smartest, its the one that works for everyone. BRILLIANT!

[@Yotanido]

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.

[@RandomNullpointer]

The O() notation is about *statistical* performance, i.e. considering general cases, with a huge number of measurements.

[@quinnbattaglia5189]

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.

[@mynewaccount2361]

@@quinnbattaglia5189 I know that std::sort is definitely a quicksort that instead uses insertion sort when the list gets small.

[@quinnbattaglia5189]

@@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.

[@DanielNyong]

Use insertion sort instead of bubble sort for small lists

[@valentinmoeller]

One Cut. Very impressed!

[@jimhalpert9803]

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...

[@multiarray2320]

@@jimhalpert9803 and now your reply is 11 months old

[@Andy.Bennett]

@@jimhalpert9803 and now you have 11 likes. Nice

[@johnzhibai]

Gets defeated by the sponsor

[@lisaea]

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.

[@aikslf]

You learned Big-O notation at school? Very nice. I wish I had learned it in school too.

[@CarlosLopez-ch6bu]

@@aikslf fam its second semester of computer science a. Near the end i think

[@robinw77]

Adi Septiana for me, isSchool() == false

[@markallen97]

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.

[@adrianscarlett]

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.

[@klaxoncow]

...or, as Donald Knuth had it: "the fastest code is the code that never runs".

[@DLCS-2]

Smart Human.

[@AleksWorkshop]

Disappointed not to hear the “ONE TAKE” screech at the end of the video

[@arnavanand8037]

Probably the 2^256th take

[@olipolygon]

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.

[@ShaunDreclin]

And it was likely wrong/out of date too! The number of sites online still telling people to use bgcolor and font tags... 😡

[@jd_27]

2001 called

[@mayhair]

@ *s h u t*

[@francescoaiazzone]

Who would want comic sans in their website?

[@olipolygon]

@@francescoaiazzone who wouldnt? please hire me for web design 😊

[@igfoobar]

A good developer can write an efficient sort algorithm. A great developer just uses the system libraries.

[@TXnine7nine]

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.

[@donaldasayers]

"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.

[@oz_jones]

"Why teachers complain about their wages, they get the summers and weekends off!" People having a giggle, I tell you.

[@livifan45]

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.

[@Madhattersinjeans]

Judging by the other responses here. Aye that was a good grammar school.

[@whuzzzup]

Don't forget: Teach the other classes in the meantime.

[@dylanharding5720]

Ever heard of a joke?

[@rickharriss]

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.

[@enjaad1654]

I'm curious, what kind of system did you implement ? I feel like this kind of communication problem will always be a big issue.

[@rickharriss]

@@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.

[@enjaad1654]

@@rickharriss Thank you very much !

[@robpatershuk]

If Tom Scott explained every programming concept I ever struggled with, I would no longer struggle.

[@samq146]

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 "

[@Gilgwathir]

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 :-)

[@edsanville]

I’m 39 years old, and I miss “utterly unjustified confidence”.... sigh, the nostalgia.

[@4everparky]

ok boomer

[@sleeptyper]

@@4everparky If SETI was searching for intelligent life from KZbin comments, they would be just as succesful ...

[@thekingoffailure9967]

I'm 18 years old and I've never even been confident in my ability to chew

[@boiledelephant]

@@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.

[@rambard5599]

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.

[@juststeve5542]

Tom, this might actually be the last recorded time that an end user actually knew exactly what they wanted!

[@danielbakergill]

You have my gratitude for removing the inevitable CRT whine that was in this video

[@mathieuviales7351]

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 !

[@doomcookies]

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.

[@niklasschmidt3610]

list.sortstate=true; if (complain==true) { return(gulag(user)) }

[@saperoi]

@@niklasschmidt3610 Error: gulag is not defined.

[@waterspray5743]

Error: memory out of range

[@Steve-nuru888]

@doomcookies Therese is a real sorting algoritm named stalin sort it removes the values that Are not sorted so that the values you Are left with Are sorted.

[@Big_Bad_Gammon]

Bogosort is like a move in a video game that has a 10% chance to insta-kill an enemy.

[@HasekuraIsuna]

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.

[@anthonybenci9035]

Fissure

[@hotaru8309]

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.

[@saatvikagarwal6358]

My Electronic heart just died witnessing this tragedy

[@malup1117]

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!

[@scpWyatt]

Stalin Sort is always the best due to it being Big O of N. Always. It goes something like this: for n in arr, if arr[n] < arr[n-1] pass, else drop arr[n]. By the end, the list will be ordered, give or take a few dropped items that didn’t make the cut.

[@bbqgiraffe3766]

When I was 14 my website stored passwords, comments, and profile names/descriptions in plain text

[@deadchannel1745]

In a text file everyone can see

[@PebsBeans]

"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

[@charlesgantz5865]

So now that you've encrypted your passwords, do you still use the same ones.

[@bbqgiraffe3766]

@@charlesgantz5865 I had to shutdown the website when I was 16

[@charlesgantz5865]

@@bbqgiraffe3766 To bad.

[@zoronic6248]

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.

[@tannerteddo]

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.

[@josephfiddes60]

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.

[@Quantum-yz9fc]

@Nikhilesh Kumar Malik n! is 1*2*...*n, while the complexity of the algorithm is 1+2+...+n

[@krepes8685]

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)

[@Datamining101]

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.

[@DarkStarCoreX]

It would still be O(n^2) unfortunately

[@sheskab8755]

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"**

[@history3042]

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.

[@krcb197]

That is one of the most important engineering and development lessons: do what is the best solution for the user.

[@keiran215]

"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

[@DudeWatIsThis]

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.

[@iceypino1086]

When I saw Tom Scott and “My Teenage Code” and “Bogosort” I cried

[@zion_fox]

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.

[@059_souravpaswan2]

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 😕

[@DanielQRT]

it is still O n^2

[@ПаскарАлексей]

@@DanielQRT Yep

[@0x8badf00d]

square != exponential

[@solsystem1342]

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.

[@mrvastayan]

Tom you never cease to teach me something new, thank you.

[@tosuxo]

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!

[@deusexaethera]

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.

[@julianegner5997]

"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.

[@WakingOne]

And you, the almighty star programmer, know for them? lmfao

[@spektriye]

Questionable pfp

[@mytech6779]

@@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.

[@Angry-Lynx]

And yet despite being right you still in the wrong here at the bigger picture

[@Icalasari]

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!?"

[@iamanidiotbut5523]

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.

[@cameronmyron5776]

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).

[@Markyparky56]

I'm a fan of heat-death sort. It's O(1). 1. Wait until the heat-death of the universe 2. There's no one left to care if the list is sorted now or not

[@Markyparky56]

Bonus: Email sort. O(n) Take a list of numbers: 1. Foreach item in the list, spawn n threads. 2. Sleep each thread for that item's value in seconds. 3. After that time has elapsed, send it to yourself as an email 4. The list is now sorted.

[@EpicScizor]

The reason quantum mechanics is complicated (on computers) is that the best algorithm we have, in terms of accuracy, is O(n^n) where n is number of particles. That one isn't used, however. Instead, there are series of approximations, each one a litte more inaccurate and much faster. The common ones for chemistry are, in order from most accurate to least accurate: CCSD (n^7), CCS(n^6), CC2 *and* MP2 (n^5), and finally HF (n^4). This means that when my computer uses 4 minutes to calculate the lowest-energy state of water (3 atoms), calculating the same for alcohol (8 atoms) takes roughly 3 hours using the fastest QM method we have. Meanwhile, a typical medicinal drug (~50 atoms) would by the same calculation use 50 days. Hence why we use supercomputers.

[@djd829]

"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.

[@rakibahsan6599]

Tom's facial expressions while storytelling are just one of a kind! ❤️

[@Caraxian]

"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

[@weckar]

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.

[@chexo3]

How does Australian work experience differ?

[@gvigary1]

If Tom learned a lesson which was of value later in his career, it wasn't a waste.

[@bananya6020]

@@gvigary1 That lesson is that work experience can be bs

[@davidioanhedges]

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...

[@BopsRusher]

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.

[@The9garr]

This is an incredibly well timed video for someone going into a second semester programming course starting yesterday

[@randomjasmicisrandom]

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.

[@jimbok21]

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.

[@jamestanis3274]

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.

[@leo_warren]

@@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.

[@jamestanis3274]

@@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).

[@greenUserman]

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.

[@davidweihe6052]

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 :-)

[@nonnnth]

I feel like I finally understand what my teacher's trying to say 2 years ago.

[@shreya...007]

3:13 That animation with that hand movement was so satisfying!!!

[@fahtfakcarl7695]

I watched another video, explaining the exact same thing, couldnt understand anything other than bubble and insertion sort, you explained it soooooooo much better. Thank you!

[@chatowa]

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

[@kaspers.2498]

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

[@gyroninjamodder]

It was not a "amazing explanation." This video does not even teach you what "Big O", even is.

[@Drakonus_]

I tend to imagine that the person who created the Bogosort didn't know that it would become the joke sorting algorithm.

[@dennisysj8868]

That was the simplest quick sort explanation ever

[@UnitCodesChannel]

at 15 when you were doing all that I was still figuring out how to eat ice cream by not dropping it on my shirt. Absolute Genius

[@MidnightSt]

6:30 since the moment you mentioned sorting and it was obvious you're going to use it as an example, I was hoping SO MUCH that you'd mention bogosort =D

[@MidnightSt]

...and I just realized funny thing - once that quantum computers are actually usable, won't bogosort become the fastest sorting algo? O_O

[@gyroninjamodder]

@@MidnightSt Why would it become the fastest? Running on a quantum computer doesn't magically make algorithms faster.

[@MidnightSt]

@@gyroninjamodder well... isn't the point of quantum computers that the computation can happen via superposition of all possible states, from which then pops up the desired result state? which to me sounds like bogosort would run on it in O(1) time, since one operation (within the superposition part) would be "randomly reorder the list", which would get you a superposition of all the list states, and second operation would be "from the superposition of all possibilities of how this list can be randomly reordered, return the state where the list is sorted"?

[@gyroninjamodder]

@@MidnightSt You can't just call the steps that you need to do a single operation. For example just finding an element in a list is ϴ(sqrt(n)). You seem to only have a high level idea on what quantum computers are doing. A quantum computer takes in an input, feeds those values into several special logic gates, and then measures what the output is. The benefit of quantum computing is that these logic gates works on bits that are in a super position. Our goal is to exploit the intermediary superpositions to make more efficient algorithms. The input and outputs will be regular 1s and 0s. Another thing to note is that current quantum computers suffer from noise making some algorithms impractical.

[@sodiboo]

7:34 The gesture with his right hand indicates to me that this video is flipped

[@scottbuchanan8300]

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!

[@jacob_90s]

Big O was one of those lessons I remember not thinking that much of in school, but I've found it to be incredibly helpful when I try to plan out whatever projects I'm working on. One mistake that I see programmers make very frequently though, is not taking into account the Big O performance of built in functions. A very common example is string operations in Javascript. They seem to just think that whatever strings they're working with will always be very small, and so they're code ends up scaling horribly. The sad thing is the modifications needed to make it scale better usually aren't that complicated.

[@kirbyblade2238]

i have been obsessed with watching sorting algorithms recently but i didnt really know anything about them so this was a really cool watch !!!

[@donaldhobson8873]

When I was about that age, I came up with a sort algorithm, it had a run time of n! x 2^n .

[@rcksnxc361]

I’d like to know what it was like lmao

[@donaldhobson8873]

Exact code, Python3

[@rcksnxc361]

@@donaldhobson8873 sure (I am assuming that is a question to seek confirmation since I do not see the code anywhere at the moment)

[@omp199]

@@rcksnxc361 It's a year later, and the code that Donald Hobson wrote to paste the code here is still running.

[@Traspler]

In my heart, the best sorting Algo still is Sleep Sort ;)

[@anuvette]

It's so weird i was thinking about sorting algorithms the whole day and you uploaded a video about it now

[@anishjoshi1999]

"the best solution isn't always the fastest or the smartest. it's the one that works for everyone, long-term." - Tom Scott

[@collinschofield808]

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.

[@LukeOverthinks]

Two days work experience? Our teachers got rid of us for a whole fortnight.

[@Templarfreak]

7:54 thank you for saying this, not enough people do :D Also, the way you describe "work experience" is not very different from the concept of an internship in America. You are given busy work to do so they can get as much work for free out of you as possible and you learn virtually nothing.

[@Foche_T._Schitt]

You can thank minimum wage laws for that.

[@SorryBones]

Currently learning this in discrete math. It’s a blast seeing why my quintuple for loops makes things run in slow motion.

[@MK73DS]

For bubble sort, you don't have to go through the end each step, since you know at the nth step, the (n-1) last elements are sorted. It doesn't change its complexity, but the number of operations basically is divided by 2 (n² vs n(n+1)/2)

[@DearHRS]

but you didn't half it, you increased it by weird amount n^2 = n * n n(n+1)/2 = (n* n)/2 + n/2 xd i know you meant to put minus, i am just messing with ye

[@wyllmRox]

I'm gonna send this to software engineers when they pretend their CS degree doesn't help them with their job

[@kiradotee]

"Do what the client asked you to do" Tom is growing old.

[@AttilaAsztalos]

Don't be daft, you never actually do that. If you did, the task would be impossible to complete, especially in the allotted time - modern management just "doesn't do" doable tasks. You need all your shortcuts of not actually doing what you are supposed to in order to ever end up with the thing done, "merely" late.

[@kiradotee]

@@AttilaAsztalos haha, I can relate to that 😂

[@williamgeorge2045]

Wow. Hit me right in the premature optimization.

[@SgtHappyHands]

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.

[@eskimoprime09]

5:47 but can you? I've already watched so many videos about different sorting algorithms because they're so much fun, but the way you explain things is just much more fascinating.