ShmoopTube

Where Monty Python meets your 10th grade teacher.

Search Thousands of Shmoop Videos


Standard Algorithms Videos 20 videos

AP Computer Science 2.1 Standard Algorithms
432 Views

APCS: Standard Algorithms Drill 2, Problem 1. How much slower is InefficientSum than EfficientSum in the best case for an array of n elements?

AP Computer Science 2.5 Standard Algorithms
176 Views

In this computer science drill question, figure out which implementation will copy one array over to another.

AP Computer Science 3.3 Standard Algorithms
175 Views

AP Computer Science: Standard Algorithms Drill 3, Problem 3. What should go in "expression 1" to satisfy the conditional statement?

See All

AP Computer Science 2.3 Standard Algorithms 169 Views


Share It!


Description:

AP Computer Science 2.3 Standard Algorithms. What would be the best possible way to sort our sheep?

Language:
English Language

Transcript

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

Related Videos

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?

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?