ShmoopTube

Where Monty Python meets your 10th grade teacher.

Search Thousands of Shmoop Videos

AP Computer Science 3.2 Standard Algorithms 173 Views


Share It!


Description:

AP Computer Science 3.2 Standard Algorithms. What is the worst case for insertion sort?

Language:
English Language

Transcript

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

Up Next

AP Computer Science 1.2 GridWorld Case Study and APIs
493 Views

AP Computer Science 1.2 GridWorld Case Study and APIs. What is the direction of the actor?

Related Videos

AP Computer Science 1.4 Standard Algorithms
200 Views

AP Computer Science 1.4 Standard Algorithms. How many times will mystery be called for mystery(n) for n > 1?

AP Computer Science 2.3 Classes and Objects
191 Views

AP Computer Science 2.3 Classes and Objects. Which of the following is correct implementation of the Country class?

AP Computer Science 3.4 Inheritance, Abstraction, and Polymorphism
204 Views

AP Computer Science 3.4 Inheritance, Abstraction, and Polymorphism. Which of the following will satisfy the conditional if statement for boo, str,...

AP Computer Science 4.2 Standard Algorithms
191 Views

AP Computer Science 4.2 Standard Algorithms. What kind of algorithm is the following?