ShmoopTube

00:00

Thank you We sneak and here's your shmoop du jour

00:05

brought to you by algorithms we thought were really cool

00:09

and then turned out to be that's what's the worst

00:13

case for insertion sort story Yeah right This question is

00:18

asking what is the worst possible thing that could happen

00:22

to insertion Sort Basically what type of data will make

00:25

the longest complete let's Think about what insurgents or does

00:30

it goes through each element and then moves it backwards

00:33

Index bite index until there's no number bigger behind so

00:38

unsorted random data won't necessarily make it take the longest

00:42

time possible because numbers will be in random order Not

00:45

every element will take the maximum amount of time to

00:49

sort waken obviously eliminate choice b because this will take

00:53

the shortest amount of time that leaves us with choice

00:55

C is the only viable answer so let's take a

00:57

look if insertions over applied on data that was sorted

01:01

in reverse order meaning the largest elements were in the

01:05

beginning of the array the algorithm would have to move

01:07

every element the maximum number of times it would have

01:12

to move every single element to the opposite position in

01:14

the array meaning first will be last and so on

01:18

This produces a rough run time of squared definitely the

01:23

war's case scenario Next time we'll look at more things 00:01:26.003 --> [endTime] that looked promising Originally like latest transformers movie

Full Transcript