Merken

# Sorting Rubyists

#### Automatisierte Medienanalyse

## Diese automatischen Videoanalysen setzt das TIB|AV-Portal ein:

**Szenenerkennung**—

**Shot Boundary Detection**segmentiert das Video anhand von Bildmerkmalen. Ein daraus erzeugtes visuelles Inhaltsverzeichnis gibt einen schnellen Überblick über den Inhalt des Videos und bietet einen zielgenauen Zugriff.

**Texterkennung**–

**Intelligent Character Recognition**erfasst, indexiert und macht geschriebene Sprache (zum Beispiel Text auf Folien) durchsuchbar.

**Spracherkennung**–

**Speech to Text**notiert die gesprochene Sprache im Video in Form eines Transkripts, das durchsuchbar ist.

**Bilderkennung**–

**Visual Concept Detection**indexiert das Bewegtbild mit fachspezifischen und fächerübergreifenden visuellen Konzepten (zum Beispiel Landschaft, Fassadendetail, technische Zeichnung, Computeranimation oder Vorlesung).

**Verschlagwortung**–

**Named Entity Recognition**beschreibt die einzelnen Videosegmente mit semantisch verknüpften Sachbegriffen. Synonyme oder Unterbegriffe von eingegebenen Suchbegriffen können dadurch automatisch mitgesucht werden, was die Treffermenge erweitert.

Erkannte Entitäten

Sprachtranskript

00:00

genes and here and uh at always where got the Griffin doors enchanted sorting at and I don't usually do interest for my doctor because the idea is you give a bio is to get you into the room and all of you are already here the but is somewhat like hi my name is Caleb as you can see this morning I was at a hundred hour 970 followers and loved it a thousand that means that I need to get 30 people to follow me the and there's at least 30 people in here so I think we can make this happen the itself if you like what you hear with they get fonts and follow me at killed Compton also on the slide we have joined Zhang giving a truism a little bit of information behind the scenes on what it takes to get up on the stage mostly not preparing for your talk right that this talk is

01:08

not for people who study computers if you know a big Oh notation is great sit back hopefully the son of a good time but I might not be teaching anything this talk is for

01:22

people who call sort and have no idea where demons removing strings around in the array you get back sorted and that's pretty cool you would like to learn a little bit more so would stay understand what Ruby or plus crest deal when you call sort we need to talk about algorithms Annual algorithms are a bit of a scary word but what it comes down to is over them they're just a set of step by step instructions a recipe for chocolate chip cookies is a novel I don't have to understand chemistry a gastronomy when I followed the instructions when I realize that this was just it was a good example I just found a recipe for chocolate chip cookies and made a batch immediately procrastinating on preparing for my talk and

02:11

I think the the all of

02:15

them of the before

02:20

we get too far else wanna talk about big o so this is another scary concept especially when you see it written out next to some over them or something and well you know I usually assume that it's for math people and I make websites placated said were not computer scientists so it's probably not me know it comes down to is the goes not really that's here

02:44

it's how we answer the question how fast is novel and how we can take that answer compared to other algorithms it's based on the assumption that the basic operations involved in an algorithm will take the same amount of time between different algorithms to in sense of the so what it does is allow us to compare using the number of operations as a function of the inputs as a instead of actual time taken in in running the of the operations the so the state I a

03:19

look at a couple of examples of algorithms for cutting out squares from paper when I previously give this talk the it was pointed out to me that our a little bit smaller heart disease and actually the 1st thing I did was by John pair of scissors and they are all In a giant panda Post-it notes so he could see so hopefully you can see the step butterfly appeared by flying right so each time I end up with another piece of paper that's can 1 operation we it in you know the 1 of the this is due to an end to what it the the we did in all of our the 2nd so you know what the the I had to go these lines because I kept on getting like really weirdly shaped pieces it what we I has had the scissors who came up with this idea uh it it I think so the the I think that the had fun facts this is actually the 1st time I've kept on board the accessible the so the to nodes on we what the it already In the then right so we ended up with 16 squares of paper that makes this algorithm uh an order of N squared times quadratic kind of were entirely linear for them the slide and so as you can see that the growth is linear goes right across the screen if I wanted to cut out 32 squares would take me 31 cuts now that's a different number that's not in so in is the number of squares that I need and so you know it's 15 and not 16 it's 31 and 32 but it doesn't matter because be goes a little bit lossy and the growth is linear and that's what we're really looking at in Figure notation right so they didn't expect this story look at another algorithm cutting up pieces of paper you think of the fact that this was a little bit better in the and if you what the will pay per a you have to really is a the all right and we still have 16 pieces of paper if I wanted 32 pieces of debris would take me only 1 market 5 cats which makes this on a logarithmic time or order of log in our the so much more much more performance than the original despite these kinds this is an example of a lot of different representations the fairly common for bigger down at the bottom that in orange and yellow FIL is actually behind Green the we have of the order of log n and order of n time algorithm so you can see that there's some very big ones here and the the 2 that we shall we we actually looked at the graphs already for her order and an order of organ you can see that the little it's more that's because of it scale down the y axis to tender 1 just to show how big somebody's bigger ones so in squared to the end and ends of In factorial very large if you don imaginary line diagonally through this chart then when you really wanna sheep or is the big notation that are below for a performer now algorithm rather than ones that are above zooming back into 1 1 we can see that there's still a big difference even between order of an order of log it at its eventual that 1st time counts when updating user record on log n it if you've understood everything so far I'm really honored today the had debugger maps we all know this guest start log so what happens when you buy something I promise is the last 1 body so you on this is a dumb question at simple rules at a talk about big omega this is going to be a little bit easier to understand because it's exactly the same as big O except rather than worst-case performance were talking about best-case performance which is why it has the little tails the bottom because it's the lower bound for how fast now written in the tha

10:24

all sort is a nice and simple algorithm so a great place to start jumping in explaining sorting nobody is that for each pair of elements compared if they're in the wrong order swap them the new 1 over and the guy keep doing that in the in the hippy in the set and then start over you don't have to look at the last 1 because the last 1 30 bubbled up to be in the correct position so you can go through an entire iteration and no changes are made then your set is sort of can short circuit power so my volunteers volunteered folks please come over here With the papers are what if the your pi the right the the history run volunteered and say the people goal here to the the you have that OK you can go and say the line over there with the late in your eyes the the the half of the correct what and the self and the and cheat sheet we the these are anemic everybody a little text at 5 . 1 is it out yet the high recall 1 4 1 5 9 2 6 5 3 5 the 2 . 1 8 2 8 1 8 2 8 where like etc. 9 doesn't want it over 9 thousand cell 42 the over here the 9 thousand 1 the the 5 . 1 and the so you just shuffle them great according to go through the bubble sort algorithm the we here I would like so the algorithm is we compare each number to the number 2 in class so 42 is less than 9 thousand 1 so it's in the right place no changes that shows 9 thousand 1 is definitely bigger the 5 . 1 bring a swap positions had already moved so we only to move again 9 thousand 1 is bigger than pi herself places you fiery hot 9 thousand 1 greater than ESA result places again that's the 1st iteration easy we know that 9 thousand 1 is in the right place now because it's been bubbled up all the way right that to 42 42 is greater than 5 . 1 so there is some places 42 grade and by some places 42 greater than a place or places right the pretty easy that OK 42 and 9 thousand 1 both in the right place right rails the version we don't have yet to be a pretty big so can be bigger than by assault places and that would be given a soreness or places the 10 all the way to the end again and again we're not needing to go past but we ready bubbled up so is better than bigger than E not better to stick so result places but it also that's the 2nd last iteration now where to go through this entire set the doesn't have anything comparatives we've made no slots and were sort right through a thank you friends may take your seats on the you going and keep going toward

14:42

this bubble sort works in in squared times for the purposes of sorting of events In is in this length of the set so since bubble sort operates in quadratic time so that means that it we compare each element every other element In the worst case even though we have some optimation optimization so you're not actually comparing every element every other element like skipping the ones that were even bubbled up 1 receding in algorithms complexity we still say in squared because again that's the grow quadratic growth for bubble sort order in squared is also the average case complexity such as on a randomized direct it has a big omega for lower bound best-case time of in which means that awards best-case bubble sort is sorted and returns a sorted set in linear time the so if we had instead of instead of 42 9 thousand 1 5 . 1 i.e. if we had the pi 5 . 1 142 9 thousand 1 then we would've just had to go through each person wants check that they're in the right order and then we would have been done as we saw before in squared is not that great is this red line here and again that's above the imaginary line that we want to avoid it's bad because it means that the number of operations taken is much higher which generally means more time spent in the other we want to be in 1 of these 4 small islands big o of n log n or big o of n or ideally order of login or order of 1 however 1 would only work in a perfect world where every set is already sorted and so the sorting algorithm is returned the sorted set this it is school civilization of how these algorithms work on different heads and topple has this great sort of visualizations that show bubble sort operating over different types the difference sorted sets this cannot be sort of build an intuition about how bubble sort will work on these different types of the red arrows here indicator subjects black arrows are sorted and Gray arose have yet to be so we have random nearly sorted reversed and unique sets of input data this takes quite a bit of new sort of finished but rather watch the be because it takes over man and I'm on a timer

17:13

insertion sort is another simple sorting out it's very efficient at sorting nearly sorted sets and very small sets insertion sort is called the so called because it inserts the sorting the subject element into the set of previously sorted elements in the correct order by comparing it until it's greater than 1 of the position of 1 the previous elements and inserting right after that so the organism

17:38

for each element consider all elements to its left continue until you reach 1 that's smaller than the element or you run out of elements check against the if you found anything smaller move the element just after the place and shift everything also let's cyclic the all stop 1st with this 1 and we're gonna compare to everything that's left this is a pretty easy steps there's nothing to its left sort of there were to consider the next element it's the red were comparing 2 is not bigger than the green subject so we're not gonna move anything here is this subset of already sort on to the next green subject will compare each of these and see both smaller the this was so this 1 and this 1 sort move this to the beginning now the 1st 4 elements are in order will repeat this until the whole set of certain what speed through that the

18:45

of of how hello with we find any relevant model components can only fit to the data presentations never work that's another insider tips and the the great so now we have a sorted sets insertion source upon 1 because it's 1 of the simplest sorting algorithms to

19:25

like bubble sort insertion sort operates in quadratic time and in for the worst case and in quadratic time for the average also like bubble sort and insertion sort has the best case of n squared or in time because the inherent glossiness of big O notation this ignores insertion sort is almost always faster than novels but is simply not a fantastic way to sort a large set it it does work

19:53

very well on nearly sorted arrays 30 finished because it is insertion sort is sometimes used as a finishing step for quicksort which will look at next it shares the benefited bubble sort has of returning an already sorted set in linear time you can see that it's working much better on the reverse set and is generally faster despite having the same complexity representations and bubbles or again the stakes allows 1 not what and

20:22

quicksort often considered the state of the art in comparison sorting out this is because the average case complexity for the soaring organ is very low compared to others in the same class of Allah it'll only different than insertion a bubble sort rather than taking something and using it as a subject and moving it based on how it compares to other elements we're going to take a pivot which is the same thing as the subject but it's different to defer work for quicksort and remove everything else around it based on whether it's larger or smaller so if it's larger than it'll go to the right if it's model that left if it's equal we want do anything they'll stay in the same or the who have of the so quicksort doesn't specify we should use for the pivot but in general it makes the most sense to take either a random or the middle element rather than the 1st relax elements and we'll get into why that is later but let's take a look at the actual the for a star with 8 of 8 and we're gonna compare to everything on its left and right and then we're gonna move cards around so they're in the right or so 8 is greater than 2 so that's the right or is is greater than Jack so Jack needs to move over beyond where it was but with this shift everything down but and go ahead and flip the jack over and the 2 over because we've already looked at bands we'd only be looking for so now I need to compare it to the joker but don't know a jokers are jokers wild so which we use for job but economic preferably 1 of these numbers the have we know 6 6 at its and if right so 8 is 6 is less than a so the jokers mysterious 6 is also less than 8 the so the sixers guess they were at now it's important the note that because the joker in the 6 started joker here and 6 here they're not gonna change that's because in a quick sort is a stable sorting out the which means that for values that are equal they will stay in the initial ordered state the so we 8 here 5 is less than 8 so it's gonna move over and you look at in King is greater than 8 so it's in the right place bases depending on the game is can be lower which really the but right will place clean greater than it generate place sword and all these sorts of them over to and I but nothing that nothing ever works that it the the it will have at 8 and to set it down the that's funny but it's also because aid is in the right place now it's not gonna move again so when not can move this is going to be out of the way Sonora start with the lowest set things that were lower than a and again were in a repeat this process where is going to pick up pivot that where and pick the midpoint rounded down so since there's 4 elements here we're gonna take the 2nd element which is the joker Joker again is 6 so 2 is less than 6 so it's in the right place 6 is equal the set at 6 and so it's not going to move and 5 is less than 6 so moved before the dog and the joker goes down because the jokers in the right place a lot so again we're going to continue this process there's only 2 all in tears terrific the first one of midpoint render down 5 is greater than 2 so it's in the right place we'd be done with still not look at 5 there's nothing to compare 2 survivors and requests now we go the things that were greater than the Joker which is just the sex 6 in the right place really the right now finally we don't really look at things that were greater than the 8 original student work will last time but let's see how does this the gets so in picked that King making is going to be opposite Joker or Jack is less than going so it's correct these witches is high so it's greater than going it's always greater than everything else and queen is going to be less than the games ordered it over great for the king is done not model look at the Deccan queen queens greater than Jack so it seems readers and Jack is done now we look at the Queen nothing compared to to the right place simply it's nothing compared to so can request so now we have an ordered set using quicksort sort of great and I we also so it took forever to do that demo and so you might not be surprised that big o of of quicksort is also in square In the case of coca Weber is very unlikely would actually hit in squared operations to be an squared you'd have to always select the pivot that was not the smallest or largest element In the entire such that the remaining subsets to be quicksort A of size n minus 1 and say 0 to illustrate that cyclic here so we pick the midpoint as the pivot which is going to be the tallest bar so it moves over we've got a set that's everything except for that it's so in minus 1 and a set of size 0 to quicksort if this happened for every single operation every single time through the other and then it would take in squared uh in squared operations to complete and this is why you don't want to use a the 1st or last element necessarily quicksort because you handed a sorted set and it takes the 1st a last element it would always end up quick sorting In this case we've got a set of size 0 and set of size n minus 1 the magic quicksort those that the average case complexity is linearithmic which is a fancy word for n log n time so when your time times logarithmic time linearity the average case here is not just intuition like we said for bubble sort like it's probably the at the end of the following a taken with this lecture several mathematical proofs that show that quicksort runs in 1 year at a time but they're over my head and out of scope stock linearithmic or in log performance is also the best case for quicksort so while at all is not always the fastest algorithm and can be just as slow as insertion a bubble sort with specific types of input data it's average case is the best case and the best case is faster than just about anything else in a any other comparisons worry however for general purposes meaning integers strings whatever this is the green across the that

28:35

said it does have its weaknesses you can see here that it does agree with the reversed set and the nearly sorted set and the random set but it's having trouble with a few unique set the the you can see the same visualizations that we looked at for every each type of other all compared together as a different algorithms work and finish eating get idea that some of them are better suited for specific tasks the random set in the 1st column the does give a fair approximation of the average case and you can see the quicksort works very quickly that it also makes short work of the reversed said and which principle of soaring our insertion sort which very quickly on the nearly sorted set and bubble sort surrogate anything of Digital's right use the on the other hand is very difficult to beat the average case performance for quicksort which is why I that's what Ruby users in it sort implementation of the like to

29:44

think my employer broken for supporting incoming real stuff this year you may have heard about the new automated certificate management offering which let news you free let's encryptor certificates for repay dinos at any tier this video shows how easy it is let's say the

29:59

order of 1 complex the you should check it

30:03

out if you haven't yet

30:06

and if you he sees speak now

30:15

but if you're interested in hearing from other OK and you're welcome to check out the speaker schedule we included in this slide which has the listing apart from John and his next Richard need in me and Stella you give me questions about sorting

30:31

ACM or really anything you open it and the office hours at the OK with in the exposition all on Wednesday and Thursday were older speakers will be hanging out for a bit usually right after the talks but the Excel explore all an open today so John and I will be later so and you can also find me in the whole or ask questions on Twitter is uniformly remember the thank

30:57

you but the there

31:01

so that he reviews of reward

00:00

Demoszene <Programmierung>

Rechenschieber

Hypermedia

Mailing-Liste

Bit

Rechter Winkel

Information

Computeranimation

01:05

Bit

Zahlensystem

Algorithmus

Menge

Cookie <Internet>

Wort <Informatik>

Computerunterstütztes Verfahren

Dämon <Informatik>

Stapelverarbeitung

Quick-Sort

Computeranimation

02:11

Web Site

Mathematisierung

Vorlesung/Konferenz

Informatik

02:42

Subtraktion

Bit

Selbst organisierendes System

Quadratische Gleichung

Selbstrepräsentation

Zahlenbereich

Ungerichteter Graph

Login

Whiteboard

Eins

Datensatz

Zahlensystem

Knotenmenge

Logarithmus

Algorithmus

Minimum

Zeitkomplexität

Figurierte Zahl

Schnitt <Graphentheorie>

Gerade

Touchscreen

Lineares Funktional

Nichtlinearer Operator

Green-Funktion

Schlussregel

Ein-Ausgabe

Mapping <Computergraphik>

Rechenschieber

Quadratzahl

Debugging

Computerunterstützte Übersetzung

Ordnung <Mathematik>

Steuerwerk

Aggregatzustand

10:23

Resultante

Bit

Subtraktion

Ortsoperator

Quadratische Gleichung

Minimierung

Mathematisierung

Klasse <Mathematik>

Versionsverwaltung

Zahlenbereich

Iteration

Zellularer Automat

Baumechanik

Element <Mathematik>

Login

Komplex <Algebra>

Eins

Komplexitätstheorie

Zufallszahlen

Algorithmus

Datentyp

Visualisierung

Zeitrichtung

Zeitkomplexität

Indexberechnung

Quick-Sort

Gerade

Metropolitan area network

Leistung <Physik>

Nichtlinearer Operator

Dicke

Eindeutigkeit

Paarvergleich

Ein-Ausgabe

Ereignishorizont

Quick-Sort

Linearisierung

Menge

Rechter Winkel

Digitaltechnik

Ordnung <Mathematik>

17:12

Teilmenge

Einfügungsdämpfung

Ortsoperator

Menge

Selbst organisierendes System

Element <Mathematik>

Quick-Sort

Ordnung <Mathematik>

Einfügungsdämpfung

Quick-Sort

Verschiebungsoperator

18:40

Zahlensystem

Informationsmodellierung

Einfügungsdämpfung

Algorithmus

Menge

Mittelwert

Quadratische Gleichung

Zusammenhängender Graph

Quellcode

Kombinatorische Gruppentheorie

Quick-Sort

19:51

Sichtbarkeitsverfahren

Einfügungsdämpfung

Demo <Programm>

Prozess <Physik>

Selbst organisierendes System

Mathematisierung

Klasse <Mathematik>

Selbstrepräsentation

t-Test

Zahlenbereich

Element <Mathematik>

Komplex <Algebra>

Informationsmodellierung

Zufallszahlen

Logarithmus

Algorithmus

Reverse Engineering

Spieltheorie

Gruppe <Mathematik>

Datentyp

Volumenvisualisierung

Stützpunkt <Mathematik>

Zeitkomplexität

Quick-Sort

Verschiebungsoperator

Schreib-Lese-Kopf

Array <Informatik>

Umwandlungsenthalpie

Nichtlinearer Operator

Mathematik

Pivot-Operation

Ausnahmebehandlung

Paarvergleich

Ein-Ausgabe

Quick-Sort

Chipkarte

Linearisierung

Teilmenge

Generator <Informatik>

Menge

Ganze Zahl

Rechter Winkel

Beweistheorie

Ablöseblase

Wort <Informatik>

Aggregatzustand

Zeichenkette

28:33

Einfügungsdämpfung

Digitales Zertifikat

Approximation

Freeware

Implementierung

Quick-Sort

Computeranimation

Videokonferenz

Task

Zufallszahlen

Datenmanagement

Algorithmus

Menge

Rechter Winkel

Softwareschwachstelle

Randomisierung

Visualisierung

Zeitkomplexität

Eindeutigkeit

Einfügungsdämpfung

29:58

Rechenschieber

Scheduling

Mailing-Liste

Ordnung <Mathematik>

Computeranimation

Quantisierung <Physik>

Gammafunktion

30:29

Spezialrechner

Algorithmus

Hypermedia

Software

Bit

Twitter <Softwareplattform>

Visualisierung

Schlussregel

Office-Paket

31:01

COM

### Metadaten

#### Formale Metadaten

Titel | Sorting Rubyists |

Serientitel | RailsConf 2017 |

Teil | 53 |

Anzahl der Teile | 86 |

Autor | Thompson, Caleb |

Lizenz |
CC-Namensnennung - Weitergabe unter gleichen Bedingungen 3.0 Unported: Sie dürfen das Werk bzw. den Inhalt zu jedem legalen und nicht-kommerziellen Zweck nutzen, verändern und in unveränderter oder veränderter Form vervielfältigen, verbreiten und öffentlich zugänglich machen, sofern Sie den Namen des Autors/Rechteinhabers in der von ihm festgelegten Weise nennen und das Werk bzw. diesen Inhalt auch in veränderter Form nur unter den Bedingungen dieser Lizenz weitergeben. |

DOI | 10.5446/31284 |

Herausgeber | Confreaks, LLC |

Erscheinungsjahr | 2017 |

Sprache | Englisch |

#### Inhaltliche Metadaten

Fachgebiet | Informatik |

Abstract | Let's take a peek under the hood of the magical "sort" method, learning algorithms... by sorting audience members wearing numbers! Intimidated by the word "algorithm? Not sure what performance means? Confused by "Big O Notation"? Haven't even heard of best-, worst-, and average-case time complexities? No problem: we'll learn together! You can expect to come out knowing new things and with Benny Hill stuck in your head. |