ShmoopTube

00:00

Thank you here's your shmoop du jour loaded with sheet

00:06

because we will in have it any other way All

00:09

right what would be the best possible way to sort

00:10

our sheet They'll be sorted by increasing wool density and

00:15

hear your potential And island all right there are more

00:22

than a handful of sorting algorithms and each has its

00:25

own strengths and weaknesses It's election sorts main strength is

00:29

its simplicity which comes at the price of being usually

00:32

the slowest Well it works like this starting at the

00:35

beginning of an array it passes over every single element

00:37

and finds the smallest value Then it swaps that value

00:41

with whatever's in the front of the line and reverses

00:44

the entire thing again this time starting from the next

00:48

index down What you'll get is a sordid array Eventually

00:53

our insertion sort is also pretty simple It starts at

00:56

the beginning comparing two elements and move the lesson left

00:59

then checks the one immediately left of those two to

01:02

see if that newly moved value is smaller still If

01:05

so it moves to the left again and so on

01:08

Using this mechanism it'll move smaller and smaller values further

01:11

and further left until we're left with assorted array merge

01:15

sort tackle sorting by breaking one big problem into several

01:19

smaller ones Conceptually it divides the unsorted listed this following

01:23

father list until each element is its own list a

01:25

list with one element Is considered properly sorted then those

01:30

properly sorted tiny lists are combined in tow lists of

01:33

two elements which are easy to sort and those lists

01:36

are combined and sorted into larger lists and so on

01:39

until eventually the entire array is once again a single

01:41

list and sorted this time well quick sort is another

01:45

way of dividing a large problem in the smaller ones

01:48

To start an element is selected to be the pivot

01:51

all the other elements air then judges being either less

01:54

than or greater than a pivot element This ship which

01:57

has a wool density of four has had the great

02:00

fortune being selected as the pivot well quick sort would

02:03

then sort every sheep less than four to the left

02:06

and greater than four to the right and those two

02:09

groups that have their own pivots and do the same

02:11

thing And again And when the whole thing is finally

02:13

reconstituted we've got a single big so which one wins

02:18

out Well despite being way more complicated algorithms merge sort

02:22

and quick sort definitely perform their tasks faster than the

02:26

other two with quick sort beating merge sort in most 00:02:29.275 --> [endTime] situations but just barely

Full Transcript