Algorithms and Data Structures Tutorial - Full Course for Beginners

this is a full-length course from

treehouse we at free code camp are

longtime fans of their learning platform

they were kind enough to let our

non-profit make this course freely

available on our youtube channel if you

like this course treehouse has a lot

more courses like this one the link is

in the description

along with time codes to the different

sections in this course

[Music]

hi my name is passan i'm an instructor

here at treehouse and welcome to

introduction to algorithms

whether you are a high school or college

student a developer in the industry or

someone who is learning to code you have

undoubtedly run into the term algorithm

for many people this word is kind of

scary it represents this body of

knowledge that seems just out of reach

only people with computer science

degrees know about algorithms now to

others this brings up feelings of

imposter syndrome

you might already know how to code but

you're not a real developer because you

don't know anything about algorithms

personally it made me frame certain jobs

as above my skill level because the

interview contained algorithm questions

well whatever your reasons are in this

course our goal is to dispel all those

feelings and get you comfortable with

the basics of algorithms

like any other subject i like to start

my courses with what the course is and

is not

in this course we're going to cover the

very basic set of knowledge that you

need as a foundation for learning about

algorithms

this course is less about specific

algorithms and more about the tools you

will need to evaluate algorithms

understand how they perform

compare them to each other and make a

statement about the utility of an

algorithm in a given context

now don't worry none of this will be

theoretical and we will learn these

concepts by using well-known algorithms

in this course we will also be writing

code so i do expect you to have some

programming experience if you intend to

continue with this topic

you can definitely stick around even if

you don't know how to code but you might

want to learn the basics of programming

in the meantime

in this course we will be using the

python programming language python reads

a lot like regular english and is the

language you will most likely encounter

when learning about algorithms these

days

if you don't know how to code or if you

know how to code in a different language

check out the notes section of this

video for links to other content that

might be useful to you

as long as you understand the

fundamentals of programming you should

be able to follow along pretty well

if you're a javascript developer or a

student who's learning javascript for

example chances are good that you'll

still be able to understand the code we

write later i'll be sure to provide

links along the way if you need anything

to follow up on

let's start with something simple

what is an algorithm

an algorithm is a set of steps or

instructions for completing a task

this might sound like an over

simplification but really that's

precisely what an algorithm is

a recipe is an algorithm your morning

routine when you wake up is an algorithm

and the driving directions you follow to

get to a destination is also an

algorithm

in computer science the term algorithm

more specifically means the set of steps

a program takes to finish a task

if you've written code before any code

really generally speaking you have

written an algorithm

given that much of the code we write can

be considered an algorithm what do

people mean when they say you should

know about algorithms

now consider this

let's say i'm a teacher in a classroom

and i tell everyone i have an assignment

for them on their desks they have a

picture of a maze and their task is to

come up with a way to find the quickest

way out of the maze

everyone does their thing and comes up

with a solution

every single one of these solutions is a

viable solution and is a valid example

of an algorithm the steps one needs to

take to get out of the maze but from

being in classrooms or any group of any

sort you know that some people will have

better ideas than others we all have a

diverse array of skill sets

over time our class picks the best of

these solutions and any time we want to

solve a maze we go with one of these

solutions this is what the field of

algorithms is about

there are many problems in computer

science but some of them are pretty

common regardless of what project you're

working on

different people have come up with

different solutions to these common

problems and over time the field of

computer science has identified several

that do the job well for a given task

when we talk of algorithms we're

referring to two points

we're primarily saying there's an

established body of knowledge on how to

solve particular problems well and it's

important to know what the solutions are

now why is it important

if you're unaware that a solution exists

you might try to come up with one

yourself and there's a likelihood that

your solution won't be as good or

efficient whatever that means compared

to those that have been thoroughly

reviewed

but there's a second component to it as

well

part of understanding algorithms is not

just knowing that an algorithm exists

but understanding when to apply it

understanding when to apply an algorithm

requires properly understanding the

problem at hand and this arguably is the

most important part of learning about

algorithms and data structures

as you progress through this content you

should be able to look at a problem and

break it down into distinct steps

when you have a set of steps you should

then be able to identify which algorithm

or data structure is best for the task

at hand

this concept is called algorithmic

thinking and it's something we're going

to try and cultivate together as we work

through our content

lastly learning about algorithms gives

you a deeper understanding about

complexity and efficiency in programming

having a better sense of how your code

will perform in different situations is

something that you'll always want to

develop in hone

algorithmic thinking is why algorithms

also come up in big tech interviews

interviewers don't care as much that you

are able to write a specific algorithm

in code but more about the fact that you

can break a seemingly insurmountable

problem into distinct components and

identify the right tools to solve each

distinct component

and that is what we plan on doing in

this course though we're going to focus

on some of the tools and concepts you'll

need to be aware of before we can dive

into the topic of algorithms if you're

ready let's get started

hey again in this video we're going to

do something unusual we're going to play

a game and by we i mean me and my two

friends here brittany and john

this game is really simple and you may

have played it before it goes something

like this i'm going to think of a number

between 1 and 10 and they have to guess

what the number is easy right

when they guess a number i'll tell them

if their guess is too high or too low

the winner is the one with the fewest

tries all right john let's start with

you i'm thinking of a number between one

and ten what is it

between you and me the answer is three

uh quick question does the range include

one and ten

that is a really good question so what

john did right there was to establish

the bounds of our problem

no solution works on every problem and

an important part of algorithmic

thinking is to clearly define what the

problem set is and clarify what values

count as inputs

yeah 1 and ten are both included is it

one too low is it two too low is it

three correct

okay so that was an easy one it took

john three tries to get the answer let's

switch over to brittany and play another

round using the same number as the

answer okay brittany i'm thinking of a

number between 1 and 10 inclusive so

both 1 and 10 are in the range what

number am i thinking of

is it 5 too high

2 too low

is it 3 correct all right so what we had

there was two very different ways of

playing the same game

somehow with even such a simple game we

saw different approaches to figuring out

a solution

to go back to algorithmic thinking for a

second this means that with any given

problem there's no one best solution

instead what we should try and figure

out is what solution works better for

the current problem

in this first pass at the game they both

took the same amount of turns to find

the answer so it's not obvious who has

the better approach and that's mostly

because the game was easy

let's try this one more time now this

time the answer is 10.

all right john you first is it one too

low is it two still too low is it three

too low is it four too low is it five

still too low is it six too low is it

seven too low is it eight low is it nine

do low is it ten correct you got it okay

so now same thing but with britney this

time

is it five too low

eight too low is it nine still too low

it's ten

all right so here we start to see a

difference between their strategies when

the answer was three they both took the

same number of turns this is important

when the number was larger but not that

much larger 10 in this case we start to

see that britney strategy did better she

took four tries while john took 10.

we've played two rounds so far and we've

seen a different set of results based on

the number they were looking for

if you look at john's way of doing

things then the answer being 10 the

round we just played is his worst case

scenario he will take the maximum number

of turns 10 to guess it

when we picked a random number like

three it was hard to differentiate which

strategy was better because they both

performed exactly the same

but in john's worst case scenario a

clear winner in terms of strategy

emerges

in terms of algorithmic thinking we're

starting to get a sense that the

specific value they're searching for may

not matter as much as where that value

lies in the range that they've been

given

identifying this helps us understand our

problem better

let's do this again for a range of

numbers from one to one hundred we'll

start by picking five as an answer to

trick them

okay so this time we're going to run

through the exercise again this time

from one to one hundred and both one and

one hundred are included is it one at

this point without even having to run

through it we can guess how many tries

john is going to take since he starts at

one and keeps going he's going to take

five tries as we're about to see is it

five cool correct

okay now for brittany's turn

is it 50 too high is it 25 still too

high

is it 13 too high is it seven

too high

is it four too low

is it six too high is it five correct

let's evaluate john took five tries

brittany on the other hand takes seven

tries so john wins this round but again

in determining whose strategy is

preferred there's no clear winner right

now

what this tells us is that it's not

particularly useful to look at the easy

answers where we arrive at the number

fairly quickly because it's at the start

of the range

instead let's try one where we know john

is going to do poorly let's look at his

worst case scenario where the answer is

100 and see how britney performs in such

a scenario

okay john let's do this one more time

one through 100 again

is it one we can fast forward this scene

because well we know what happens john

takes 100 tries

hi brittany you're up

is it 50 too low is it 75 too low 88 too

low

94 too low is it 97 too low

99 too low

100.

okay so that took brittney seven turns

again and this time she is the clear

winner if you compare their individual

performances for the same number set

you'll see that britney's approach

leaves john's in the dust

when the answer was five so right around

the start of the range john took five

turns but when the answer was 100 right

at the end of the range he took 100

tries it took him 20 times the amount of

tries to get that answer compared to

britney

on the other hand if you compare

britney's efforts when the number was 5

she took seven tries but when the number

was 100 she took the same amount of

tries this is pretty impressive if we

pretend that the number of tries is the

number of seconds it takes britney and

john to run through their attempts this

is a good estimate for how fast their

solutions are

ok we've done this a couple times and

brittany and john are getting tired

let's take a break in the next video

we'll talk about the point of this

exercise

in the last video we ran through an

exercise where i had some of my

co-workers guess what number i was

thinking so was the point of that

exercise you might be thinking hey i

thought i was here to learn about

algorithms

the exercise we just did was an example

of a real life situation you will run

into when building websites apps and

writing code

both approaches taken by john and

brittany to find the number i was

thinking of are examples of searching

for a value

it might be weird to think that there's

more than one way to search but as you

saw in the game the speed at which the

result was obtained differed between

john and brittany think about this

problem from the perspective of a

company like facebook

at the time of this recording facebook

has 2.19 billion active users

let's say you're traveling in a

different country and meet someone you

want to add on facebook

you go into the search bar and type out

this person's name

if we simplify how the facebook app

works it has to search across these 2.19

billion records and find the person you

are looking for

the speed at which you find this person

really matters imagine what kind of

experience it would be if when you

search for a friend facebook put up a

spinning activity indicator and said

come back in a couple hours

i don't think we'd use facebook as much

if that was the case

from the company's perspective working

on making search as fast as possible

using different strategies really

matters

now i said that the two strategies

britney and john used were examples of

search

more specifically these are search

algorithms

the strategy john took where he started

at the beginning of the range and just

counted one number after the other is a

type of search called linear search

it is also called sequential search

which is a better description of how it

works or even simple search since it

really is quite simple

but what makes his approach an algorithm

as opposed to just looking for something

remember we said that an algorithm is a

set of steps or instructions to complete

a task

linear search is a search algorithm and

we can define it like this

we start at the beginning of the list or

the range of values

then we compare the current value to the

target

if the current value is the target value

that we're looking for we're done

if it's not we'll move on sequentially

to the next value in the list and then

repeat step 2.

if we reach the end of the list then the

target value is not in the list

this definition has nothing to do with

programming and in fact you can use it

in the real world for example

i could tell you to walk into a

bookstore and find me a particular book

and one of the ways you could do it is

using the linear search algorithm

you could start at the front of the

bookstore and read the cover or the

spine of every book to check that it

matches the book that you're looking for

if it doesn't you go to the next book

and repeat until you find it or run out

of books

what makes this an algorithm is the

specificity of how it is defined

in contrast to just jumping into a

problem and solving it as we go along an

algorithm follows a certain set of

guidelines and we use the same steps to

solve the problem each time we face it

an important first step to defining the

algorithm isn't the algorithm itself but

the problem we're trying to solve

our first guideline is that an algorithm

must have a clear problem statement

it's pretty hard to define an

instruction set when you don't have a

clear idea of what problem you're trying

to solve

in defining the problem we need to

specify how the input is defined and

what the output looks like when the

algorithm has done its job

for linear search the input can be

generally described as a series of

values and the output is a value

matching the one we're looking for

right now we're trying to stay away from

anything code related so this problem

statement definition is pretty generic

but once we get to code we can actually

tighten this up

once we have a problem an algorithm is a

set of steps that solves this problem

given that the next guideline is that an

algorithm definition must contain a

specific set of instructions in a

particular order

we really need to be clear about the

order in which these instructions are

executed

taking our simple definition of linear

search if i switched up the order and

said move sequentially to the next value

before specifying that first comparison

step if the first value were the target

one our algorithm wouldn't find it

because we moved to the second value

before comparing

now you might think okay that's just an

avoidable mistake and kind of common

sense

the thing is computers don't know any of

that and just do exactly as we tell them

so specific order is really important

the third guideline is that each step in

our algorithm definition must not be a

complex one and needs to be explicitly

clear what i mean by that is that you

shouldn't be able to break down any of

the steps into further into additional

subtasks

each step needs to be a distinct one we

can't define linear search as search

until you find this value because that

can be interpreted in many ways and

further broken down into many more steps

it's not clear

next and this one might seem obvious but

algorithms should produce a result

if it didn't how would we know whether

the algorithm works or not

to be able to verify that our algorithm

works correctly we need a result

now when using a search algorithm the

end result can actually be nothing which

indicates that the value wasn't found

but that's perfectly fine

there are several ways to represent

nothing in code and as long as the

algorithm can produce some results we

can understand its behavior

the last guideline is that the algorithm

should actually complete and cannot take

an infinite amount of time

if we let john loose in the world's

largest library and asked him to find a

novel we have no way of knowing whether

he succeeded or not unless he came back

to us with a result

okay so quick recap what makes an

algorithm an algorithm and not just

something you do

one it needs to have a clearly defined

problem statement input and output

when using linear search the input needs

to be just a series of values but to

actually use brittany's strategy there's

one additional precondition so to speak

if you think about her strategy it

required that the numbers be sorted in

ascending order

this means that where the input for john

is just a series of values to solve the

problem the input to brittany's

algorithm needs to be a sorted series of

values

so clearly defined problem statement

clearly defined input and clearly

defined output

second the steps in the algorithm need

to be in a very specific order

the steps also need to be distinct you

should not be able to break it down into

further subtasks

next the algorithm should produce a

result

and finally the algorithm should

complete in a finite amount of time

these guidelines not only help us define

what an algorithm is but also helps us

verify that the algorithm is correct

executing the steps in an algorithm for

a given input must result in the same

output every time

if in the game i played the answer was

50 every time then every single time

john must take 50 turns to find out that

the answer is 50. if somehow he takes 50

turns in one round then 30 the next and

we technically don't have a correct

algorithm

consistent results for the same set of

values is how we know that the algorithm

is correct

i should stress that we're not going to

be designing any algorithms on our own

and we'll start off and spend most of

our time learning the tried and true

algorithms that are known to efficiently

solve problems

the reason for talking about what makes

for a good algorithm though is that the

same set of guidelines makes for good

algorithmic thinking which is one of the

most important skills we want to

cultivate

when we encounter a problem before

rushing in and thinking about solutions

what we want to do is work through the

guidelines

first we break down the problem into any

possible number of smaller problems

where each problem can be clearly

defined in terms of an input and an

output

now that we know how to generally define

an algorithm let's talk about what it

means to have a good algorithm

an important thing to keep in mind is

that there's no one single way to

measure whether an algorithm is the

right solution because it is all about

context

earlier we touched on two concepts

correctness and efficiency

let's define correctness more clearly

because before we can evaluate an

algorithm on efficiency we need to

ensure its correctness

before we define our algorithms we start

by defining our problem

in the definition of that problem we

have a clearly defined input satisfying

any preconditions and a clearly defined

output

an algorithm is deemed correct if on

every run of the algorithm against all

possible values in the input data we

always get the output we expect

part of correctness means that for any

possible input the algorithm should

always terminate or end

if these two are not true then our

algorithm isn't correct

if you were to pick up an algorithm's

textbook and look up correctness you

will run into a bunch of mathematical

theory this is because traditionally

algorithm correctness is proved by

mathematical induction which is a form

of reasoning used in mathematics to

verify that a statement is correct

this approach involves writing what is

called a specification and a correctness

proof

we won't be going into that in this

course

proof through induction is an important

part of designing algorithms but we're

confident that you can understand

algorithms both in terms of how and when

to use them without getting into the

math so if you pick up a textbook and

feel daunted don't worry i do too but we

can still figure things out without it

all right so once we have a correct

algorithm we can start to talk about how

efficient an algorithm is

remember that this efficiency ultimately

matters because they help us solve

problems faster and deliver a better end

user experience in a variety of fields

for example algorithms are used in the

sequencing of dna and more efficient

sequencing algorithms allow us to

research and understand diseases better

and faster but let's not get ahead of

ourselves we'll start simple by

evaluating john's linear search

algorithm in terms of its efficiency

first what do we mean by efficiency

there are two measures of efficiency

when it comes to algorithms time and

space sounds really cool and very sci-fi

huh

efficiency measured by time something

you'll hear called time complexity is a

measure of how long it takes the

algorithm to run

time complexity can be understood

generally outside the context of code

and computers because how long it takes

to complete a job is a universal measure

of efficiency the less time you take the

more efficient you are

the second measure of efficiency is

called space complexity and this is

pretty computer specific

it deals with the amount of memory taken

up on the computer

good algorithms need to balance between

these two measures to be useful

for example you can have a blazingly

fast algorithm but it might not matter

if the algorithm consumes more memory

than you have available

both of these concepts time and space

complexity are measured using the same

metric but it is a very technical

sounding metric so let's build up to it

slowly and start simple

a few videos ago i played a game with

brittany and john where they tried to

guess the number i was thinking of

effectively they were searching for a

value

so how do we figure out how efficient

each algorithm is and which algorithm

was more suited to our purposes

if we consider the number of tries they

took to guess or search for the value as

an indicator of the time they take to

run through the exercise this is a good

indicator of how long the algorithm runs

for a given set of values

this measurement is called the running

time of an algorithm and we'll use it to

define time complexity

in the game we play it four rounds let's

recap those here focusing on john's

performance

in round one we had 10 values the target

was 3 and john took 3 turns

in round 2 we had 10 values the target

was 10 and john took 10 turns

in round 3 we had 100 values the target

was

john took five tries and finally in

round four when the target was 100 given

100 values john took 100 tries

on paper it's hard to gauge anything

about this performance

when it comes to anything with numbers

though i like to put it up on a graph

and compare visually

on the vertical or y-axis let's measure

the number of tries it took john to

guess the answer or the running time of

the algorithm on the horizontal or

x-axis what do we put

for each turn we have a number of values

as well as a target value

we could plot the target value on the

horizontal axis but that leaves some

context and meaning behind it's far more

impressive that john took five tries

when the range went up to 100 then when

he took three tries for a maximum of 10

values

we could plot the maximum range of

values but then we're leaving out the

other half of the picture

there are data points however that

satisfy both requirements

if we only plot the values where the

target the number john was looking for

was the same as the maximum range of

values we have a data point that

includes both the size of the data set

as well as his effort

there's an additional benefit to this

approach as well

there are three ways we can measure how

well john does or in general how well

any algorithm does

first we can check how well john does in

the best case or good scenarios from the

perspective of his strategy

in the range of 100 values the answer

being a low number like three at the

start of the range is a good scenario he

can guess it fairly quickly one is his

best case scenario

or we could check how well he does on

average we could run this game a bunch

of times and average out the running

time

this would give us a much better picture

of john's performance over time but our

estimates would be too high if the value

he was searching for was at the start of

the range or far too low if it was at

the end of the range

let's imagine a scenario where facebook

naively implements linear search when

finding friends

they looked at the latest u.s census saw

that 50 of names start with the letters

a through j which is the first 40 of the

alphabet and thought okay on average

linear search serves us well

but what about the rest of those whose

names start with the letter after j in

the alphabet

searching for my name would take longer

than the average and much longer for

someone whose name starts with the

letter z

so while measuring the run time of an

algorithm on average might seem like a

good strategy it won't necessarily

provide an accurate picture

by picking the maximum in the range

we're measuring how our algorithm does

in the worst case scenario

analyzing the worst case scenario is

quite useful because it indicates that

the algorithm will never perform worse

than we expect there's no room for

surprises

back to our graph we're going to plot

the number of tries a proxy for running

time of the algorithm against the number

of values in the range which will

shorten to n

n here also represents john's worst case

scenario when n is 10 he takes 10 turns

when n is 100 he takes 100 turns

but these two values alone are

insufficient to really get any sort of

visual understanding moreover it's not

realistic

john may take a long time to work

through 100 numbers but a computer can

do that in no time

to evaluate the performance of linear

search in the context of a computer we

should probably throw some harder and

larger ranges of values at it

the nice thing is by evaluating a worst

case scenario we don't actually have to

do that work

we know what the result will be for a

given value of n using linear search it

will take n tries to find the value in

the worst case scenario so let's add a

few values in here to build out this

graph

okay so we have a good picture of what

this is starting to look like as the

values get really large the running time

of the algorithm gets large as well

we sort of already knew that

before we dig into this runtime any

deeper let's switch tracks and evaluate

brittany's work

by having something to compare against

it should become easier to build a

mental model around time complexity

the algorithm john used linear search

seemed familiar to us and you could

understand it because it's how most of

us search for things in real life anyway

brittany's approach on the other hand

got results quickly but it was a bit

harder to understand so let's break it

down

just like john's approach britney

started with a series of values or a

list of numbers as her input

where john just started at the beginning

of the list and searched sequentially

brittany's strategy is to always start

in the middle of the range

from there she asks a comparison

question

is the number in the middle of the range

equal to the answer she's looking for

and if it's not is it greater than or

less than the answer

if it's greater than she can eliminate

all the values less than the one she's

currently evaluating if it's lesser than

the answer she can eliminate all the

values greater than the one she's

currently evaluating

with the range of values that she's left

over with she repeats this process until

she arrives at the answer

let's visualize how she did this by

looking at round three

in round three the number of values in

the range was 100 the answer was 5.

the bar here represents the range of

values one of the left 100 at the right

and this pointer represents the value

britney chooses to evaluate

so she starts in the middle at 50. she

asks is it equal to the answer i say

it's too high so this tells her that the

value she is evaluating is greater than

our target value which means there's no

point in searching any of the values to

the right of 50 that is values greater

than 50 in this range so she can discard

those values altogether

she only has to consider values from 1

to 50 now

the beauty of this strategy and the

reason why britney was able to find the

answer in such few turns is that with

every value she evaluates she can

discard half of the current range

on her second turn she picks the value

in the middle of the current range which

is 25. she asks the same question i say

that the value is too high again and

this tells her that she can discard

everything greater than 25 and the range

of values drops from 1 to 25.

again she evaluates the number in the

middle roughly so that'd be 13 here i

tell her this is still too high she

discards the values greater moves to

value at 7 which is still too high

then she moves to 4 which is now too low

she can discard everything less than 4

which leaves the numbers 4 through 7.

here she picked 6 which was too high

which only leaves one value 5.

this seems like a lot of work but being

able to get rid of half the values with

each turn is what makes this algorithm

much more efficient

now there's one subtlety to using binary

search and you might have caught on to

this

for this search method to work as we've

mentioned the values need to be sorted

with linear search it doesn't matter if

the values are sorted since a linear

search algorithm just progresses

sequentially checking every element in

the list if the target value exists in

the list it will be fouled but let's say

this range of values 100 was unsorted

britney would start at the middle with

something like 14 and ask if this value

was too low or too high i say it's too

high so she discards everything less

than 14.

now this example starts to fall apart

here because well britney knows what

numbers are less than 14 and greater

than one she doesn't need an actual

range of values to solve this a computer

however does need that

remember search algorithms are run

against lists containing all sorts of

data it's not always just a range of

values containing numbers

in a real use case of binary search

which we're going to implement in a bit

the algorithm wouldn't return the target

value because we already know that it's

a search algorithm so we're providing

something to search for instead what it

returns is the position in the list that

the target occupies without the list

being sorted a binary search algorithm

would discard all the values to the left

of 14 which over here could include the

position where our target value is

eventually we'd get a result back saying

the target value doesn't exist in the

list which is inaccurate

earlier when defining linear simple

search i said that the input was a list

of values and the output was the target

value or more specifically the position

of the target value in the list

so with binary search there's also that

precondition the input list must be

sorted so let's formally define binary

search

first the input a sorted list of values

the output the position in the list of

the target value we're searching for or

some sort of values indicate that the

target does not exist in the list

remember our guidelines for defining an

algorithm let me put those up again

really quick

the steps in the algorithm need to be in

a specific order the steps also need to

be very distinct

the algorithms should produce a result

and finally the algorithm should

complete in a finite amount of time

let's use those to define this algorithm

step one we determine the middle

position of the sorted list

step two we compare the element in the

middle position to the target element

step three if the elements match we

return the middle position and end

if they don't match in step 4 we check

whether the element in the middle

position is smaller than the target

element

if it is then we go back to step 2 with

a new list that goes from the middle

position of the current list to the end

of the current list

in step five if the element in the

middle position is greater than the

target element then again we go back to

step two with a new list that goes from

the start of the current list to the

middle position of the current list

we repeat this process until the target

element is found or until a sub list

contains only one element

if that single element sublist does not

match the target element then we end the

algorithm indicating that the element

does not exist in the list

okay so that is the magic behind how

britney managed to solve the round much

faster

in the next video let's talk about the

efficiency of binary search

[Music]

we have a vague understanding that

britney's approach is better in most

cases but just like with linear search

it helps to visualize this

much like we did with linear search when

determining the efficiency of an

algorithm and remember we're still only

looking at efficiency in terms of time

time complexity as it's called we always

want to evaluate how the algorithm

performs in the worst case scenario now

you might be thinking well that doesn't

seem fair because given a series of data

if the target value we're searching for

is somewhere near the front of the list

then linear search may perform just as

well if not slightly better than binary

search and that is totally true

remember a crucial part of learning

algorithms is understanding what works

better in a given context

when measuring efficiency though we

always use the worst case scenarios as a

benchmark because remember it can never

perform worse than the worst case

let's plot these values on the graph we

started earlier with the number of tris

or the runtime of the algorithm on the y

axis and the maximum number of values in

the series or n on the horizontal axis

to represent the worst case scenario we

have two data points when n equals 10

britney took four tries using binary

search and when n equals 100 it took

seven tries

but even side by side these data points

are sort of meaningless

remember that while there is quite a

difference between the run time of

linear search and binary search at an n

value of 100 for a computer that

shouldn't matter

what we should check out is how the

algorithm performs at levels of n that

might actually slow a computer down

as n grows larger and larger how do

these algorithms compare to one another

let's add that to the graph

okay now a picture starts to emerge

as n gets really large the performance

of these two algorithms differs

significantly

the difference is kind of staggering

actually

even with the simple game we saw that

binary search was better but now we have

a much more complete idea of how much

better

for example when n is 1000 the runtime

of linear search measured by the number

of operations or turns is also 1000.

for binary search it takes just 10

operations

now let's look at what happens when we

increase n by factor of 10

at 10 000 linear search takes 10 000

operations while binary search takes 14

operations

and increased by a factor of 10 in

binary search only needs four more

operations to find a value

if we increase it again by a factor of

10 once more to an n value of 100 000

binary search takes only 17 operations

it is blazing fast

what we've done here is plotted on a

graph how the algorithm performs as the

input set it is working on increases

in other words we've plotted the growth

rate of the algorithm also known as the

order of growth

different algorithms grow at different

rates and by evaluating their growth

rates we get a much better picture of

their performance because we know how

the algorithm will hold up as n grows

larger

this is so important in fact it is the

standard way of evaluating an algorithm

and brings us to a concept called big o

you might have heard this word thrown

about and if you found it confusing

don't worry we've already built up a

definition in the past few videos we

just need to bring it all together

let's start with a common statement

you'll see in studies on algorithms

big o is a theoretical definition of the

complexity of an algorithm as a function

of the size

wow what a mouthful this sounds really

intimidating but it's really not let's

break it down

big o is a notation used to describe

complexity and what i mean by notation

is that it simplifies everything we've

talked about down into a single variable

an example of complexity written in

terms of big o looks like this

as you can see it starts with an

uppercase letter o that's why we call it

big o it's literally a big o

the o comes from order of magnitude of

complexity so that's where we get the

big o from now complexity here refers to

the exercise we've been carrying out in

measuring efficiency

if it takes brittany 4 tries when n is

10

how long does the algorithm take when n

is 10 million

when we use big o for this the variable

used which we'll get to distills that

information down so that by reading the

variable you get a big picture view

without having to run through data

points and graphs just like we did

it's important to remember that

complexity is relative

when we evaluate the complexity of the

binary search algorithm we're doing it

relative to other search algorithms not

all algorithms

bigo is a useful notation for

understanding both time and space

complexity but only when comparing

amongst algorithms that solve the same

problem

the last bit in that definition of big o

is a function of the size and all this

means is that big o measures complexity

as the input size grows because it's not

important to understand how an algorithm

performs in a single data set but in all

possible data sets

you will also see big o referred to as

the upper bound of the algorithm and

what that means is that big o measures

how the algorithm performs in the worst

case scenario

so that's all big o is

nothing special it's just a notation

that condenses the data points and

graphs that we've built up down to one

variable okay so what do these variables

look like

for john's strategy linear search we say

that it has a time complexity of big o

and then n so that's again big o with an

n inside parentheses

for britney strategy binary search we

say that it has a time complexity of big

o of log n that's big o with something

called a log and an n inside parentheses

now don't worry if you don't understand

that we'll go into that in more detail

later on in the course

each of these has a special meaning but

it helps to work through all of them to

get a big picture view so over the next

few videos let's examine what are called

common complexities or common values of

big o that you will run into and should

internalize

in our discussions of complexity we made

one assumption that the algorithm as a

whole had a single measure of complexity

that isn't true and we'll get at how we

arrive at these measures for the entire

algorithm at the end of this exercise

but each step in the algorithm has its

own space and time complexity

in linear search for example there are

multiple steps and the algorithm goes

like this

start at the beginning of the list or

range of values compare the current

value to the target if the current value

is the target value that we're looking

for we're done

if it's not we'll move on sequentially

to the next value in the list and repeat

step two

if we reach the end of the list then the

target value is not in the list

let's go back to step two for a second

comparing the current value to the

target

does the size of the data set matter for

this step

when we're at step two we're already at

that position in the list and all we're

doing is reading the value to make a

comparison reading the value is a single

operation and if we were to plot it on a

graph of runtime per operations against

n it looks like this a straight line

that takes constant time regardless of

the size of n since this takes the same

amount of time in any given case we say

that the run time is constant time it

doesn't change

in big o notation we represent this as

big o with a 1 inside parentheses now

when i first started learning all this i

was really confused as to how to read

this even if it was in my own head

should i say big o of one

when you see this written you're going

to read this as constant time so reading

a value in a list is a constant time

operation

this is the most ideal case when it

comes to run times because input size

does not matter and we know that

regardless of the size of n the

algorithm runtime will remain the same

the next step up in complexity so to

speak is the situation we encountered

with the binary search algorithm

traditionally explaining the time

complexity of binary search involves

math i'm going to try to do it both with

and without

when we played the game using binary

search we notice that with every turn we

were able to discard half of the data

but there's another pattern that emerges

that we didn't explore

let's say n equals 10. how long does it

take to find an item at the 10th

position of the list we can write this

out so we go from 10 to 5 to 8 to 9 and

then down to 10.

here it takes us four tries to cut down

the list to just one element and find

the value we're looking for

let's double the value of n to 20 and

see how long it takes for us to find an

item at the 20th position so we start at

20 and then we pick 10 from there we go

to 15 17 19 and finally 20.

so here it takes us five tries

okay let's double it again so that n is

40 and we try to find the item in the

40th position

so when we start at 40 the first

midpoint we're going to pick is 20 from

there we go to 30 then 35 37 39 and then

40.

notice that every time we double the

value of n the number of operations it

takes to reduce the list down to a

single element only increases by 1.

there's a mathematical relationship to

this pattern and it's called a logarithm

of n

you don't really have to know what

logarithms truly are but i know that

some of you like underlying explainers

so i'll give you a quick one

if you've taken algebra classes you may

have learned about exponents here's a

quick refresher

2 times 1 equals 2. now this can be

written as 2 raised to the first power

because it is our base case two times

one is two

now two times two is four this can be

written as two raised to the second

power because we're multiplying two

twice first we multiply two times one

then the result of that times 2.

2 times 2 times 2 is 8 and we can write

this as 2 raised to the 3rd power

because we're multiplying 2 3 times

in 2 raised to 2 and 2 raised to 3 the 2

and 3 there are called exponents and

they define how the number grows

with 2 raised to 3 we start with the

base value and multiply itself 3 times

the inverse of an exponent is called a

logarithm so if i say log to the base 2

of 8 equals 3 i'm basically saying the

opposite of an exponent

instead of saying how many times do i

have to multiply this value i'm asking

how many times do i have to divide 8 by

two to get the value one

this takes three operations

what about the result of log to the base

two of sixteen that evaluates to four

so why does any of this matter

notice that this is sort of how binary

search works

log to the base 2 of 16 is 4.

if n was 16 how many triads does it take

to get to that last element

well we start in the middle at 8 that's

too low so we move to 12 then we move to

14 then to 15 and then to 16 which is 5

tries or log to the base 2 of 16 plus 1.

in general for a given value of n the

number of tries it takes to find the

worst case scenario

is log of n plus one

and because this pattern is overall a

logarithmic pattern we say that the

runtime of such algorithms is

logarithmic

if we plot these data points on our

graph a logarithmic runtime looks like

this

in big o notation we represent a

logarithmic runtime as big o of log n

which is written as big o with log n

inside parentheses or even sometimes as

l n n inside parentheses

when you see this read it as logarithmic

time

as you can see on the graph as n grows

really large the number of operations

grows very slowly and eventually

flattens out

since this line is below the line for a

linear runtime which we'll look at in a

second you might often hear algorithms

with logarithmic runtimes being called

sublinear

logarithmic or sub-linear runtimes are

preferred to linear because they're more

efficient but in practice linear search

has its own set of advantages which

we'll take a look at in the next video

next up let's look at the situation we

encountered with the linear search

algorithm

we saw that in the worst case scenario

whatever the value of n was john took

exactly that many tries to find the

answer

as in linear search when the number of

operations to determine the result in

the worst case scenario is at most the

same as n

we say that the algorithm runs in linear

time

we represent this as big o of n now you

can read that as big o of n like i just

said or you can say linear time which is

more common

when we put that up on a graph against

constant time and logarithmic time we

get a line that looks like this

any algorithm that sequentially reads

the input will have linear time

so remember anytime you know a problem

involves reading every item in a list

that means a linear run time as you saw

from the game we played brittany's

strategy using binary search was clearly

better and we can see that on the graph

so if we had the option why would we use

linear search which runs in linear time

remember that binary search had a

precondition the input set had to be

sorted

while we won't be looking at sorting

algorithms in this course as you learn

more about algorithms you'll find that

sorting algorithms have varying

complexities themselves just like search

does so we have to do additional work

prior to using binary search

for this reason in practice linear

search ends up being more performant up

to a certain value of n because the

combination of sorting first and then

searching using binary search adds up

the next common complexity you will hear

about is when an algorithm runs in

quadratic time if the word quadratic

sounds familiar to you it's because you

might have heard about it in math class

quadratic is a word that means an

operation raised to the second power or

when something is squared

let's say you and your friends are

playing a tower defense game and to

start it off you're going to draw a map

of the terrain

this map is going to be a grid and you

pick a random number to determine how

large this grid is let's set n the size

of the grid to four

next you need to come up with a list of

coordinates so you can place towers and

enemies and stuff on this map so how

would we do this

if we start out horizontally we'd have

coordinate points that go 1 1 1 2 1 3

and 1 4.

then you go up one level vertically and

we have points 2 1 2 2 2 3 and 2 4.

go up one more and you have the points 3

1 3 2 3 3 and 3 4 and on that last row

you have the points 4 1 4 2 4 3 and 4 4.

notice that we have a pattern here

for each row we take the value and then

create a point by adding to that every

column value

the range of values go from 1 to the

value of n

so we can generally think of it this way

for the range of values from 1 to n for

each value in that range we create a

point by combining that value with the

range of values from 1 to n again

doing it this way for each value in the

range of 1 to n we create an n number of

values and we end up with 16 points

which is also n times n or n squared

this is an algorithm with a quadratic

runtime because for any given value of n

we carry out n squared number of

operations

now i picked a relatively easy so to

speak example here because in english at

least we often denote map sizes by

height times width so we would call this

a 4 by 4 grid which is just another way

of saying 4 squared or n squared

in big o notation we would write this as

big o of n squared or say that this is

an algorithm with a quadratic runtime

many search algorithms have a worst case

quadratic runtime which you'll learn

about soon

now in addition to quadratic runtimes

you may also run into cubic runtimes as

you encounter different algorithms in

such an algorithm for a given value of n

the algorithm executes n raised to the

third power number of operations

these aren't as common as quadratic

algorithms though so we won't look at

any examples but i think it's worth

mentioning

thrown up on our graph quadratic and

cubic runtimes look like this

so this is starting to look pretty

expensive computationally as they say we

can see here that for small changes in n

there's a pretty significant change in

the number of operations that we need to

carry out

the next worst case runtime we're going

to look at is one that's called

quasi-linear and a sort of easier to

understand for lack of better word by

starting with the big o notation

quasi-linear runtimes are written out as

big o of n times log n

we learned what log n was right a

logarithmic runtime whereas n grew the

number of operations only increased by a

small factor with a quasi-linear runtime

what we're saying is that for every

value of n we're going to execute a log

n number of operations hence the run

time of n times log n

so you saw earlier with the quadratic

runtime that for each value of n we

conducted n operations it's sort of the

same in that as we go through the range

of values in n we're executing login

operations

in comparison to other runtimes a

quasi-linear algorithm has a runtime

that lies somewhere between a linear

runtime and a quadratic runtime

so where would we expect to see this

kind of runtime in practical use

well sorting algorithms is one place you

will definitely see it

merge sort for example is a sorting

algorithm that has a worst case runtime

of big o of n log n

let's take a look at a quick example

let's say we start off with a list of

numbers that looks like this and we need

to sort it

merge sort starts by splitting this list

into two lists down the middle

it then takes each sub list and splits

that in half down the middle again

it keeps doing this until we end up with

a list of just a single number

when we're down to single numbers we can

do one sort operation and merge these

sub-lists back in the opposite direction

the first part of merge sort cuts those

lists into sub-lists with half the

numbers

this is similar to binary search where

each comparison operation cuts down the

range to half the values

you know the worst case runtime in

binary search is log n so these

splitting operations have the same

runtime big o of log n or logarithmic

but splitting into half isn't the only

thing we need to do with merge sort we

also need to carry out comparison

operations so we can sort those values

and if you look at each step of this

algorithm we carry out an n number of

comparison operations and that brings

the worst case runtime of this algorithm

to n times log n also known as quasi

linear don't worry if you didn't

understand how merge sort works that

wasn't the point of this demonstration

we will be covering merge sorts soon in

a future course

the run times we've looked at so far are

all called polynomial runtimes an

algorithm is considered to have a

polynomial runtime if for a given value

of n its worst case runtime is in the

form of n raised to the k power where k

just means some value so it could be n

squared where k equals 2 for a quadratic

runtime n cubed for a cubic runtime and

so on

all of those are in the form of n raised

to some power

anything that is bounded by this and

what i mean by that is if we had a

hypothetical line on our graph of n

raised to the k power anything that

falls under this graph is considered to

have a polynomial runtime

algorithms with an upper bound or a

runtime with a big o value that is

polynomial are considered efficient

algorithms and are likely to be used in

practice

now the next class of runtimes that

we're going to look at are a runtimes

that we don't consider efficient and

these are called exponential runtimes

with these runtimes as n increases

slightly the number of operations

increases exponentially and as we'll see

in a second these algorithms are far too

expensive to be used

an exponential runtime is an algorithm

with a big o value of some number raised

to the nth power

imagine that you wanted to break into a

locker that had a padlock on it let's

assume you forgot your code

this lock takes a two digit code and the

digit for the code ranges from zero to

nine

you start by setting the dials to zero

and then with the first dial remaining

on zero you change the second dial to

one and try and open it if it doesn't

work you set it to two then try again

you would keep doing this and if you

still haven't succeeded with the second

dial set to 9 then you go back to that

first dial set it to 1 and start the

second dial over

the range of values you'd have to go

through is 0 0 to 9 9 which is 100

values

this can be generalized as 10 to the

second power since there are 10 values

on each dial raised to two dials

searching through each individual value

until you stumble on the right one is a

strategy called brute force and brute

force algorithms have exponential run

times

here there are two dials so n is 2 and

each dial has 10 values so again we can

generalize this algorithm as 10 raised

to n where n represents the number of

dials

the reason that this algorithm is so

inefficient is because with just one

more dial on the lock the number of

operations increases significantly

with three dials the number of

combinations in the worst case scenario

where the correct code is the last digit

in the range is 10 raised to 3 or 1 000

values

with an additional wheel it becomes 10

raised to 4 or 10 000 values

as n increases the number of operations

increases exponentially to a point where

it's unsolvable in a realistic amount of

time

now you might think well any computer

can crack a four digit numerical lock

and that's true because n here is

sufficiently small but this is the same

principle that we use for passwords

in a typical password field implemented

well users are allowed to use letters of

the english alphabet so up to 26

characters numbers from 0 to 9 and a set

of special characters of which there can

be around 33

so typically that means each character

in a password can be one out of 69

values

this means that for a one character

password it takes 69 to the nth power so

1 which equals 69 operations in the

worst case scenario to figure out the

password

just increasing n to 2 increases the

number of operations needed to guess the

password to 69 squared or

4761 operations

now usually on a secure website there

isn't really a limit but in general

passwords are limited to around 20

characters in length

with each character being a possible 69

values and there being 20 characters the

number of operations needed to guess the

password in the worst case scenario is

69 raised to the 20th power or

approximately 6 followed by 36 zeros

number of operations

an intel cpu with five cores can carry

out roughly about 65 000 million

instructions per second that's a funny

number i know to crack our 20-digit

passcode in this very simplistic model

it would take this intel cpu

to race to 20th power years to brute

force the password

so while this algorithm would eventually

produce a result it is so inefficient

that it's pointless

this is one of the reasons why people

recommend you have longer passwords

since brute forcing is exponential in

the worst case each character you add

increases the number of combinations by

an exponent

the next class of exponential algorithms

is best highlighted by a popular problem

known as the traveling salesman

the problem statement goes like this

given a list of cities and the distance

between each pair of cities what is the

shortest possible route that visits each

city and then returns to the origin city

this seems like a simple question but

let's start with a simple case three

cities a b and c

to figure out what the shortest route is

we need to come up with all the possible

routes

with three cities we have six routes in

theory at least some of these routes can

be discarded because abc is the same as

c b a but in the opposite direction

but as we do know sometimes going from a

to c through b may go through a

different route than c to a through b so

we'll stick to the six routes and from

there we could determine the shortest no

big deal

now if we increase this to four cities

we jump to 24 combinations

the mathematical relationship that

defines this is called a factorial and

is written out as n followed by an

exclamation point

factorials are basically n times n minus

one repeated until you reach the number

one so for example the factorial of

three is three times two times one which

is six which is the number of

combinations we came up with for three

cities

the factorial of four is four times

three times two times one or 24 which is

the number of combinations we arrived at

with four cities

in solving the traveling salesman

problem the most efficient algorithm

will have a factorial runtime or a

combinatorial runtime as it's also

called

at low values of n algorithms with a

factorial runtime may be used but with

an n value of say 200 it would take

longer than humans have been alive to

solve the problem

for sake of completeness let's plot a

combinatorial runtime on our graph so

that we can compare

an algorithm such as one that solves the

traveling salesman problem as a worst

case run time of big o of n factorial

studying exponential runtimes like this

are useful for two reasons

first in studying how to make such

algorithms efficient we develop

strategies that are useful across the

board and can potentially be used to

make existing algorithms even more

efficient

second it's important to be aware of

problems that take a long time to solve

knowing right off the bat that a problem

is somewhat unsolvable in a realistic

time means you can focus your efforts on

other aspects of the problem

as beginners though we're going to steer

clear of all this and focus our efforts

on algorithms with polynomial runtimes

since we're much more likely to work

with and learn about such algorithms

now that we know some of the common

complexities in the next video let's

talk about how we determine the

complexity of an algorithm because there

are some nuances

over the last few videos we took a look

at common complexities that we would

encounter in studying algorithms but the

question remains how do we determine

what the worst case complexity of an

algorithm is

earlier i mentioned that even though we

say that an algorithm has a particular

upper bound or worst case runtime each

step in a given algorithm can have

different run times

let's bring up the steps for binary

search again

assuming the list is sorted the first

step is to determine the middle position

of the list

in general this is going to be a

constant time operation

many programming languages hold on to

information about the size of the list

so we don't actually need to walk

through the list to determine the size

now if we didn't have information about

the size of the list we would need to

walk through counting each item one by

one until we reached the end of the list

and this is a linear time operation but

realistically this is a big o of 1 or

constant time

step 2 is to compare the element in the

middle position to the target element

we can assume that in most modern

programming languages this is also a

constant time operation because the

documentation for the language tells us

it is

step 3 is our success case and the

algorithm ends

this is our best case and so far we have

only incurred two constant time

operations

so we would say that the best case run

time of binary search is constant time

which is actually true

but remember that best case is not a

useful metric

step 4 if we don't match is splitting

the list into sub-lists

assuming the worst case scenario the

algorithm would keep splitting into

sub-lists until a single element list is

reached with the value that we're

searching for

the run time for this step is

logarithmic since we discard half the

values each time

so in our algorithm we have a couple

steps that are constant time and one

step that is logarithmic overall

when evaluating the run time for an

algorithm we say that the algorithm has

as its upper bound the same runtime as

the least efficient step in the

algorithm

think of it this way let's say you're

participating in a triathlon which is a

race that has a swimming running and a

cycling component

you could be a phenomenal swimmer and a

really good cyclist but you're a pretty

terrible runner

no matter how fast you are at swimming

or cycling your overall race time is

going to be impacted the most by your

running race time because that's the

part that takes you the longest

if you take an hour 30 to finish the

running component 55 minutes to swim and

38 minutes to bike it won't matter if

you can fine tune your swimming

technique down to finish in 48 minutes

and your cycle time to 35 because you're

still bounded at the top by your running

time which is close to almost double

your bike time

similarly with the binary search

algorithm it doesn't matter how fast we

make the other steps they're already as

fast as they can be

in the worst case scenario the splitting

of the list down to a single element

list is what will impact the overall

running time of your algorithm

this is why we say that the time

complexity or run time of the algorithm

in the worst case is big o of log n or

logarithmic

as i alluded to though your algorithm

may hit a best case runtime and in

between the two best and worst case have

an average run time as well

this is important to understand because

algorithms don't always hit their worst

case but this is getting a bit too

complex for us for now we can safely

ignore average case performances and

focus only on the worst case in the

future if you decide to stick around

we'll circle back and talk about this

more

now that you know about algorithms

complexities and big o let's take a

break from all of that and write code in

the next video

[Music]

so far we've spent a lot of time in

theory and while these things are all

important things to know you get a much

better understanding of how algorithms

work when you start writing some code as

i mentioned earlier we're going to be

writing python code in this and all

subsequent algorithm courses

if you do have programming experience

but in another language check the notes

section of this video for an

implementation in your language

if you don't have any experience i'll

try my best explain as we go along

on the video you're watching right now

you should see a launch workspaces

button

we're going to use a treehouse coding

environment call workspaces to write all

of our code

if you're familiar with using python in

a local environment then feel free to

keep doing so workspaces is an

in-browser coding environment and will

take care of all the setup and

installation so you can focus on just

writing and evaluating code workspaces

is quite straightforward to use on the

left here we have a file navigator pane

which is currently empty since we

haven't created a new file

on the top we have an editor where we

write all our code and then below that

we have a terminal or a command line

prompt where we can execute the scripts

that we write let's add a new file here

so at the top in the editor area we're

going to go to file new file and we'll

name this linear

underscore search

dot pi

in here we're going to define our linear

search algorithm as a standalone

function

we start with the keyword def which

defines a function or a block of code

and then we give it the name linear

underscore search

this function will accept two arguments

first the list we're searching through

and then the target value we're looking

for both of these arguments are enclosed

in a set of parentheses and there's no

space between the name of the function

and the arguments

after that we have a colon

now there might be a bit of confusion

here since we already have this target

value what are we searching for unlike

the game we played at the beginning

where john's job was to find the value

in a true implementation of linear

search we're looking for the position in

the list where the value exists

if the target is in the list then we

return its position

and since this is a list that position

is going to be denoted by an index value

now if the target is not found we're

going to return none the choice of what

to return in the failure case may be

different in other implementations of

linear search

you can return -1 since that isn't

typically an index value

you can also raise an exception which is

python speak for indicating an error

occurred

now i think for us the most

straightforward value we can return here

is none now let's add a comment to

clarify this so hit enter to go to the

next line

and then we're going to add

three

single quotes

and then below that on the next line

we'll say returns

the position or the index

position

of the target

if found

else returns none

and then on the next line we'll close

off those three quotes

this is called a doc string and is a

python convention for documenting your

code the linear search algorithm is a

sequential algorithm that compares each

item in the list until the target is

found

to iterate or loop or walk through our

list sequentially we're going to use a

for loop

now typically when iterating over a list

in python we would use a loop like this

we'd say for item in list

this assigns the value at each index

position to that local variable item

we don't want this though since we

primarily care about the index position

instead we're going to use the range

function in python to create a range of

values that start at 0 and end at the

number of items in the list

so we'll say 4 i i stands for index here

in range

starting at 0 and going all the way up

to the length of the list

we can get the number of items in the

list using the len function

now going back to our talk on complexity

and how individual steps in an algorithm

can have its own run times this is a

line of code that we would have to be

careful about

python keeps track of the length of a

list so this function call here len list

is a constant time operation now if this

were a naive implementation let's say we

wrote the implementation of the list

and we iterate over the list every time

we call this length function then we've

already incurred a linear cost

okay so once we have a range of values

that represent index positions in this

list we're going to iterate over that

using the for loop and assign each index

value to this local variable i using

this index value we can obtain the item

at that position using subscript

notation on the list

now this is also a constant time

operation because the language says so

so we'll do if list so once we have this

value which we'll get by using subscript

notation so we'll say list i

once we have this value we'll check if

it matches the target so if the value at

i

equals target

well if it does then we'll return that

index value because we want the position

and once we hit this return statement

we're going to terminate our function if

the entire for loop is executed and we

don't hit this return statement then the

target does not exist in the list so at

the bottom here we'll say return none

even though all the individual

operations in our algorithm run in

constant time

in the worst case scenario this for loop

here will have to go through the entire

range of values and read every single

element in the list

therefore giving the algorithm a big o

value of n or running in linear time now

if you've written code before you've

definitely written code like this a

number of times and i bet you didn't

know but all along you are implementing

what is essentially a well-known

algorithm

so i hope this goes to show you that

algorithms are pretty approachable topic

like everything else this does get

advanced but as long as you take things

slow there's no reason for it to be

impossible remember that not any block

of code counts as an algorithm to be a

proper implementation of linear search

this block of code must return a value

must complete execution in a finite

amount of time and must output the same

result every time for a given input set

so let's verify this with a small test

let's write a function called verify

that accepts an index value

if the value is not none it prints the

index position if it is none it informs

us that the target was not found in the

list so def verify

and this is going to take an index value

and we'll say if index is not none

then we'll print

target

found at index

oops that's a colon here

index else

that needs to go back

there we go

else we'll say target

not found in list

okay using this function let's define a

range of numbers now so this will be a

list numbers

and we'll just go from 1 to

let's say 10.

now if you've written python code before

you know that i can use a list

comprehension to make this easier but

we'll keep things simple

we can now use our linear search

function to search for the position of a

target value in this list so we can say

result

equal

linear underscore search

and we're going to pass in the numbers

list that's the one we're searching

through and we want to look for the

position where the value 12 exists

and then we'll verify

this result

if our algorithm works correctly the

verify function should inform us that

the target did not exist so make sure

you save the file which you can do by

going up to file and save or hitting

command s

and then below in the terminal

you're going to type out python

linear search or you can hit tab and it

should auto complete linear search dot

pi

as you can see correct the target was

not found in the list so the output of

our script is what we expect

for our second test let's search for the

value 6 in the list so you can copy this

command c to copy and then paste it

again and we'll just change 12 here to 6

and then come back down to the terminal

hit the up arrow to execute the same

command again and hit enter you'll

notice that i forgot to hit save so it

did not account for that new change

we'll try that again

and there you'll see that if it works

correctly which it did the index should

be number five run the program on your

end and make sure everything works as

expected

our algorithm returned a result in each

case it executed in a finite time and

the results were the ones we expect in

the next video let's tackle binary

search

in the last video we left off with an

implementation of linear search

let's do the same for binary search so

that we get an understanding of how this

is represented in code

so we'll do this in a new file back to

file new file

and we'll name this one binary

search

dot

py

like before we're going to start with a

function named binary search so we'll

say def

binary underscore search

that takes a list and a target

if you remember binary search works by

breaking the array or list down into

smaller sets until we find the value

we're looking for

we need a way to keep track of the

position of the list that we're working

with so let's create two variables first

and last to point to the beginning and

end of the array so first equal

zero now if you're new to programming

list positions are represented by index

values that start at zero instead of one

so here we're setting first to zero to

point to the first element in the list

last is going to point to the last

element in the list so we'll say last

equal

len list

minus one now this may be confusing to

you so a quick sidebar to explain what's

going on

let's say we have a list containing 5

elements if we called len on that list

we should get 5 back because there are 5

elements

but remember that because the position

numbers start at 0 the last value is not

at position 5 but at 4. in nearly all

programming languages getting the

position of the last element in the list

is obtained by determining the length of

the list and deducting 1 which is what

we're doing

okay so we know what the first and last

positions are when we start the

algorithm

for our next line of code we're going to

create a while loop

a while loop takes a condition and keeps

executing the code inside the loop until

the condition evaluates to false

for our condition we're going to say to

keep executing this loop until the value

of first is less than or equal to the

value of last

so while first less than or equal to

last

well why you ask why is this our

condition well let's work through this

implementation and then a visualization

should help

inside the while loop we're going to

calculate the midpoint of our list since

that's the first step of binary search

midpoint equal

so we'll say first

plus last

and then we'll use the floor division

double slash here

divided by two

now the two forward slashes here are

what python calls a floor division

operator what it does is it rounds down

to the nearest whole number so if we

have an eight element array first is

zero last is 7 if we divided 0 plus 7

which is 7 by 2 we would get 3.5 now 3.5

is not a valid index position so we

round that down to 3 using the floor

division operator okay so now we have a

midpoint the next step of binary search

is to evaluate whether the value at this

midpoint is the same as the target we're

looking for so say if list

value at midpoint

equals the target

well if it is then we'll go ahead and

return the midpoint

so we'll say return

midpoint

the return statement terminates our

algorithm and over here we're done this

is our best case scenario

next we'll say else if

list at midpoint

or value at midpoint is less than the

target now here if the value is less the

value at midpoint is less than the

target then we don't care about any of

the values lower than the midpoint so we

redefine first

to point to the value after the midpoint

so we'll say midpoint plus 1.

now if the value at the midpoint is

greater than the target then we can

discard the values after the midpoint

and redefine last to point to the value

prior to the midpoint so we'll say else

last equal midpoint

minus 1.

let's visualize this we're going to

start with a list of nine integers

to make this easier to understand let's

specify these integers to be of the same

value as its index position so we have a

range of values from 0 to 8.

our target is the worst case scenario

we're looking for the position of the

value 8. at the start our algorithm sets

first to point to the index 0 and last

to point to the length of the list minus

1 which is 8.

next we hit our while loop the logic of

this loop is going to be executed as

long as the value of first is not

greater than the value of last or as

we've defined it we're going to keep

executing the contents of the loop as

long as first is less than or equal to

last

on the first pass this is true so we

enter the body of the loop

the midpoint is first plus last divided

by two and rounded down so we get a nice

even four the value at this position is

four now this is not equal to the target

so we move to the first else if

four is less than eight so now we

redefine first to point to midpoint plus

one which is five

first is still less than last so we run

through the body of the loop again the

midpoint is now six

six is less than eight so we move first

to point to seven

seven is still less than or equal to

eight so we go for another iteration of

the loop

the midpoint is seven oddly enough and

seven is still less than the target so

we move first to point to eight first is

equal to last now but our condition says

keep the loop going as long as first is

less than or equal to last so this is

our final time through the loop

the midpoint is now 8 which makes the

value at the midpoint equal to the

target and we finally exit our algorithm

and return the position of the target

now what if we had executed all this

code and never hit a case where midpoint

equal the target well that would mean

the list did not contain the target

value so after the while loop at the

bottom

will return

none

we have several operations that make up

our binary search algorithm so let's

look at the runtime of each step we

start by assigning values to first and

last

the value assigned to last involves a

call to the len function to get the size

of the list but we already know this is

a constant time operation in python so

both of these operations run in constant

time

inside the loop we have another value

assignment and this is a simple division

operation so again the runtime is

constant

in the next line of code we're reading a

value from the list and comparing the

midpoint to the target both of these

again are constant time operations the

remainder of the code is just a series

of comparisons and value assignments and

we know that these are all constant time

operations as well

so if all we have are a series of

constant time operations why does this

algorithm have in the worst case a

logarithmic runtime

it's hard to evaluate by just looking at

the code but the while loop is what

causes the run time to grow

even though all we're doing is a

comparison operation by redefining first

and last

over here or rather in the last two

steps over here we're asking the

algorithm to run as many times as it

needs until first is equal or greater

than last

now each time the loop does this the

size of the data set the size of the

list grows smaller by a certain factor

until it approaches a single element

which is what results in the logarithmic

runtime

okay just like with linear search let's

test that our algorithm works so we'll

go back to linear search.hi

and we're going to copy paste

so command c to copy if you're on a mac

then go back to binary search and at the

bottom

oops

we're going to paste in that verify

function

okay we'll also go back and grab this

numbers

you know what let's go ahead and copy

all all of these things so numbers and

the two verify cases we'll paste that in

as well

and the only thing we need to change

here is instead of calling linear search

this is going to call binary search

okay we'll hit command s to save the

file and then i'm going to drag up my

console and we'll run python binary

search dot

and hit enter and you'll see like just

like before we get the same results back

now note that an extremely important

distinction needs to be made here

the numbers list that we've defined

for our test cases

right here

has to be sorted the basic logic of

binary search relies on the fact that if

the target is greater than the midpoint

then our potential values lie to the

left or vice versa since the values are

sorted in ascending order if the values

are unsorted our implementation of

binary search may return none even if

the value exists in the list

and just like that you've written code

to implement two search algorithms how

fun was that

hopefully this course has shown you that

it isn't a topic to be afraid of and

that algorithms like any other topic

with code can be broken down and

understood piece by piece

now we have a working implementation of

binary search but there's actually more

than one way to write it so in the next

video let's write a second version

i'm going to create a new file

as always file new file

and we'll name this recursive

underscore binary underscore search dot

p

y

okay so we're going to add our new

implementation here so that we don't get

rid of that first implementation we

wrote let's call this new function

recursive binary search

unlike our previous implementation this

version is going to behave slightly

differently in that it won't return the

index value of the target element if it

exists

instead it will just return a true value

if it exists and a false if it doesn't

so recursive

underscore binary underscore search

and like before this is going to take a

list it accepts a list and a target to

look for in that list

we'll start the body of the function by

considering what happens if an empty

list is passed in in that case we would

return false so i would say if the

length of the list which is one way to

figure out if it's empty if it's equal

to zero

then we'll return false

now you might be thinking that in the

previous version of binary search we

didn't care if the list was empty well

we actually did but in a roundabout sort

of way so in the previous version of

binary search our function had a loop

and that loop condition was true when

first was less than or equal to last so

as long as it's less than or equal to

last we continue the loop

now if we have an empty list then first

is greater than last and the loop would

never execute and we return none at the

bottom

so this is the same logic we're

implementing here we're just doing it in

a slightly different way if the list is

not empty we'll implement an else clause

now here we'll calculate the midpoint

by dividing the length of the list by 2

and rounding down

again there's no use of first and last

here so we'll say length of list

and then using the floor division

operator we'll divide that by 2.

if the value at the midpoint which we'll

check by saying if list

using

subscript notation we'll say midpoint as

the index now if this value at the

midpoint is the same as the target

then we'll go ahead and return true

so far this is more or less the same

except for the value that we're

returning

let me actually get rid of all that

okay

all right so if this isn't the case

let's implement an else clause now here

we have two situations so first if the

value at the midpoint is less than the

target so if

value at midpoint

is less than the target

then we're going to do something new

we're going to call this function again

this recursive binary search function

that we're in the process of defining

we're going to call that again and we're

going to give it the portion of the list

that we want to focus on in the previous

version of binary search we moved the

first value to point to the value after

the midpoint

now here we're going to create a new

list using what is called a slice

operation and create a sub list that

starts at midpoint plus 1 and goes all

the way to the end

we're going to specify the same target

as a search target and when this

function call is done we'll return the

value so we'll say return the return is

important

then we'll call this function again

recursive

binary search

and this function takes a list and here

we're going to use that subscript

notation to perform a slice operation by

using two indexes a start and an end so

we'll say our new list that we're

passing in needs to start at midpoint

plus one

and then we'll go all the way to the end

and this is a

python syntactic sugar so to speak if i

don't specify an end index python knows

to just go all the way to the end all

right so this is our new list that we're

working with

and we need a target we'll just pass it

through if you're confused bear with me

just like before we'll visualize this at

the end

okay we have another else case here

and this is a scenario where the value

at the midpoint is greater than the

target

which means we only care about the

values in the list from the start going

up to the midpoint now in this case as

well we're going to call the binary

search function again and specify a new

list to work with this time the list is

going to start at the beginning and then

go all the way up to the midpoint so it

looks the same we'll say return

recursive

binary search

we're going to pass in a list here so if

we just put a colon here

without a start index python knows to

start at the beginning and we're going

to go all the way up to the midpoint

the target here is the same

and this is our new binary search

function so let's see if this works

actually

yes

down here we'll make some space

and we'll define a verify function

we're not going to copy paste the

previous one

because we're not returning none or an

integer here so we'll verify the result

that we pass in and we'll say print

target found

and this is just going to say true or

false whether we found it

okay so like before we need a numbers

list

and we'll do something one two three

four all the way up to eight

okay and now let's test this out so

we'll call

our recursive

binary search function

and we'll pass in the numbers list

and the target here is 12.

we're going to verify this

verify the result make sure it works and

then we'll call it again this time

making sure that we give it a target

that is actually in the list so here

we'll say 6

and we'll verify this again

make sure you hit command s to save

and then in the console below we're

going to type out

python recursive binarysearch.pi

run it and you'll see that we've

verified that search works

while we can't verify the index position

of the target value which is a

modification to how our algorithm works

we can guarantee by running across all

valid inputs that search works as

intended

so why write a different search

algorithm here a different binary search

algorithm and what's the difference

between these two implementations anyway

the difference lies in these last four

lines of code that you see here

we did something unusual here now before

we get into this a small word of advice

this is a confusing topic and people get

confused by it all the time

don't worry that doesn't make you any

less of a programmer in fact i have

trouble with it often and always look it

up including when i made this video

this version of binary search is a

recursive binary search

a recursive function is one that calls

itself

this is hard for people to grasp

sometimes because there's few easy

analogies that make sense but you can

think of it and sort this way so let's

say you have this book that contains

answers to multiplication problems

you're working on a problem and you look

up an answer

in the book the answer for your problem

says add 10 to the answer for problem 52

okay so you look up problem 52 and there

it says add 12 to the answer for problem

85

well then you go and look up the answer

to problem 85 and finally instead of

redirecting you somewhere else that

answer says 10. so you take that 10 and

then you go back to problem 52 because

remember the answer for problem 52 was

to add 12 to the answer for problem 85

so you take that 10 and then you now

have the answer to problem 85 so you add

10 to 12 to get 22.

then you go back to your original

problem where it said to add 10 to the

answer for problem 52 so you add 10 to

22 and you get 32 to end up with your

final answer so that's a weird way of

doing it but this is an example of

recursion

the solution to your first lookup in the

book was the value obtained by another

lookup in the same book which was

followed by yet another lookup in the

same book the book told you to check the

book until you arrived at some base

value

our function works in a similar manner

so let's visualize this with an example

of list

like before we have a nine element list

here with values zero through eight

the target we're searching for is the

value eight

we'll check if the list is empty by

calling len on it this list is not empty

so we go to the else clause next we

calculate the midpoint 9 divided by 2 is

4.5 rounded down is 4 so our first

midpoint value is 4.

we'll perform our first check is the

value at the midpoint equal to the

target

not true so we go to our else clause

we'll perform another check here is the

value at the midpoint less than the

target now in our case this is true

earlier when we evaluated this condition

we simply change the value of first

here we're going to call the recursive

binary search function again and give it

a new list to work with

the list starts at midpoint plus 1 so at

index position 5 all the way to the end

notice that this call to recursive

binary search inside of recursive binary

search includes a return statement

this is important and we'll come back to

that in a second

so now we're back at the top

of a new call to recursive binary search

with effectively a new list although

technically just a sub list of the first

one

the list here contains the numbers 6 7

and 8.

starting with the first check the list

is not empty so we move to the else

the midpoint in this case length of the

list 3 divided by 2 rounded down is 1.

is the value of the midpoint equal to

the target well the value at that

position is 7 so no in the else we

perform the first check is the value at

the midpoint less than the target indeed

it is so we call recursive binary search

again and provided a new list

this list starts at midpoint plus 1 and

goes to the end so in this case that's a

single element list

since this is a new call to recursive

binary search we start back up at the

top

is the list empty no the midpoint is

zero

is the value at the midpoint the same as

the target it is so now we can return

true

remember a minute ago i pointed out that

when we call recursive binary search

from inside the function itself it's

preceded by a return statement

that plays a pretty important role here

so back to our visualization

we start at the top and recall binary

search with a new list but because

that's got a return statement before it

what we're saying is hey when you run

binary search on this whatever value you

get back return it to the function that

called you

then at the second level we call binary

search again along with another return

statement like with the first call we're

instructing the function to return a

value back to the code that called it

at this level we find the target so the

function returns true back to the caller

but since this inner function was also

called by a function with instructions

to return it keeps returning that true

value back up until we reach the very

first function that called it going back

to our book of answers recursive binary

search instructs itself to keep working

on the problem until it has a concrete

answer

once it does it works its way backwards

giving the answer to every function that

called it until the original caller has

an answer

now like i said at the beginning this is

pretty complicated so you should not be

concerned if this doesn't click honestly

this is not one thing that you're going

to walk away with knowing fully how to

understand recursion after your first

try i'm really not lying when i say i

have a pretty hard time with recursion

now before we move on i do want to point

out one thing

even though the implementation of

recursion is harder to understand

it is easier in this case to understand

how we arrive at the logarithmic run

time since we keep calling the function

with smaller lists let's take a break

here in the next video let's talk a bit

more about recursion and why it matters

[Music]

in the last video we wrote a version of

binary search that uses a concept called

recursion

recursion might be a new concept for you

so let's formalize how we use it

a recursive function is one that calls

itself

in our example the recursive binary

search function called itself inside the

body of the function

when writing a recursive function you

always need a stopping condition

and typically we start the body of the

recursive function with this stopping

condition it's common to call this

stopping condition the base case

in our recursive binary search function

we had two stopping conditions

the first was what the function should

return if an empty list is passed in

it seems weird to evaluate an empty list

because you wouldn't expect to run

search on an empty list but if you look

at how our function works recursive

binary search keeps calling itself and

with each call to itself the size of the

list is cut in half

if we searched for a target that didn't

exist in the list then the function

would keep halving itself until it got

to an empty list

consider a three element list with

numbers one two three where we're

searching for a target of four

on the first pass the midpoint is 2 so

the function would call itself with the

list 3.

on the next pass the midpoint is 0 and

the target is still greater so the

function would call itself this time

passing in an empty list because an

index of 0 plus 1 in a single element

list doesn't exist

when we have an empty list this means

that after searching through the list

the value wasn't found

this is why we define an empty list as a

stopping condition or a base case that

returns false if it's not an empty list

then we have an entirely different set

of instructions we want to execute

first we obtain the midpoint of the list

once we have the midpoint we can

introduce our next base case or stopping

condition

if the value at the midpoint is the same

as the target then we return true

with these two stopping conditions we've

covered all possible paths of logic

through the search algorithm you can

either find the value or you don't

once you have the base cases the rest of

the implementation of the recursive

function is to call the function on

smaller sub-lists until we hit one of

these base cases going back to our

visualization for a second we see that

recursive binary search calls itself a

first time which then calls itself again

for the initial list we started with the

function only calls itself a few times

before a stopping condition is reached

the number of times a recursive function

calls itself is called recursive depth

now the reason i bring all of this up is

because if after you start learning

about algorithms you decide you want to

go off and do your own research you may

start to see a lot of algorithms

implemented using recursion

the way we implemented binary search the

first time is called an iterative

solution

now when you see the word iterative it

generally means the solution was

implemented using a loop structure of

some kind

a recursive solution on the other hand

is one that involves a set of stopping

conditions and a function that calls

itself computer scientists and computer

science textbooks particularly from back

in the day

favor and are written in what are called

functional languages

in functional languages we try to avoid

changing data that is given to a

function

in our first version of binary search we

created first and last variables using

the list and then modified first and

last as we needed to arrive at a

solution

functional languages don't like to do

this all this modification of variables

and prefer a solution using recursion

a language like python which is what

we're using is the opposite and doesn't

like recursion in fact python has a

maximum recursion depth after which our

function will halt execution python

prefers an iterative solution now i

mentioned all of this for two reasons

if you decide that you want to learn how

to implement the algorithm in a language

of your choice that's not python then

you might see a recursive solution as

the best implementation in that

particular language

i'm an ios developer for example and i

work with a language called swift

swift is different from python in that

it doesn't care about recursion depth

and does some neat tricks where it

doesn't even matter how many times your

function calls itself

so if you want to see this in swift code

then you need to know how recursion

works

well and now you have some idea now the

second reason i bring it up is actually

way more important and to find out on to

the next video

at the beginning of this series i

mentioned that there were two ways of

measuring the efficiency of an algorithm

the first was time complexity or how the

run time of an algorithm grows as n

grows larger

the second is space complexity

we took a pretty long route to build up

this example but now we're in a good

place to discuss space complexity

space complexity is a measure of how

much working storage or extra storage is

needed as a particular algorithm grows

we don't think about it much these days

but every single thing we do on a

computer takes up space in memory in the

early days of computing considering

memory usage was of paramount importance

because memory was limited and really

expensive

these days were spoiled our devices are

rich with memory this is okay when we

write everyday code because most of us

aren't dealing with enormously large

data sets

when we write algorithms however we need

to think about this because we want to

design our algorithms to perform as

efficiently as it can as the size of the

data set n grows really large

like time complexity space complexity is

measured in the worst case scenario

using big-o notation

since you are familiar with the

different kinds of complexities let's

dive right into an example

in our iterative implementation of

binary search the first one we wrote

that uses a while loop let's look at

what happens to our memory usage as n

gets large

let's bring up that function

let's say we start off with a list of 10

elements now inspecting the code we see

that our solution relies heavily on

these two variables first and last

first points to the start of the list

and last to the end

when we eliminate a set of values we

don't actually create a sub list instead

we just redefine first

and last as you see here

to point to a different section of the

list

since the algorithm only considers the

values between first and last when

determining the midpoint

by redefining first and last as the

algorithm proceeds we can find a

solution using just the original list

this means that for any value of n

the space complexity of the iterative

version of binary search is constant or

that the iterative version of binary

search takes constant space

remember that we would write this as big

o of one

this might seem confusing because as n

grows we need more storage to account

for that larger list size

now this is true but that storage is not

what space complexity cares about

measuring

we care about what additional storage is

needed as the algorithm runs and tries

to find a solution

if we assume something simple say that

for a given size of a list represented

by a value n it takes n amount of space

to store it whatever that means

then for the iterative version of binary

search regardless of how large the list

is at the start middle and end of the

algorithm process the amount of storage

required does not get larger than n

and this is why we consider it to run in

constant space

now this is an entirely different story

with the recursive version however in

the recursive version of binary search

we don't make use of variables to keep

track of which portion of the list we're

working with

instead we create new lists every time

with a subset of values or sub-lists

with every recursive function call

let's assume we have a list of size n

and in the worst case scenario the

target element is the last in the list

calling the recursive implementation of

binary search on this list and target

would lead to a scenario like this

the function would call itself and

create a new list that goes from the

midpoint to the end of the list

since we're discarding half the values

the size of the sub list is n by 2.

this function will keep calling itself

creating a new sub list that's half the

size of the current one until it arrives

at a single element list and a stopping

condition

this pattern that you see here where the

size of the sublist is reduced by a

factor on each execution of the

algorithmic logic well we've seen that

pattern before do you remember where

this is exactly how binary search works

it discards half the values every time

until it finds a solution now we know

that because of this pattern the running

time of binary search is logarithmic

in fact the space complexity of the

recursive version of binary search is

the same

if we start out with a memory allocation

of size n that matches the list

on each function call of recursive

binary search we need to allocate

additional memory of size n by 2 n by 4

and so on until we have a sub list that

is either empty or contains a single

value because of this we say that the

recursive version of the binary search

algorithm runs in logarithmic time with

a big o of log n

now there's an important caveat here

this totally depends on the language

remember how i said that a programming

language like swift can do some tricks

to where recursion depth doesn't matter

the same concept applies here if you

care to read more about this concept

it's called tail

optimization it's called tail

optimization because if you think of a

function as having a head and a tail

if the recursive function call is the

last line of code in the function as it

is in our case

we call this tail recursion since it's

the last part of the function that calls

itself

now the trick that swift does to reduce

the amount of space and therefore

computing overhead to keep track of this

recursive calls is called tail call

optimization or tail call elimination

it's one of those things that you'll see

thrown around a loss in algorithm

discussions but may not always be

relevant to you

now what if any of this is relevant to

us well python does not implement tail

call optimization so the recursive

version of binary search takes

logarithmic space

if we had to choose between the two

implementations given that time

complexity or run time of both versions

the iterative and the recursive version

are the same we should definitely go

with the iterative implementation in

python since it runs in constant space

okay that was a lot but all of this with

all of this we've now established two

important ways to distinguish between

algorithms that handle the same task and

determine which one we should use

we've arrived at what i think is a good

spot to take a long break and let all of

these new concepts sink in but before

you go off to the next course let's take

a few minutes to recap everything we've

learned so far

while we did implement two algorithms in

this course in actual code much of what

we learned here was conceptual and will

serve as building blocks for everything

we're going to learn in the future so

let's list all of it out

the first thing we learned about and

arguably the most important was

algorithmic thinking

algorithmic thinking is an approach to

problem solving that involves breaking a

problem down into a clearly defined

input and output along with a distinct

set of steps that solves the problem by

going from input to output

algorithmic thinking is not something

you develop overnight by taking one

course so don't worry if you're thinking

i still don't truly know how to apply

what i learned here

algorithmic thinking sinks in after you

go through several examples in a similar

fashion to what we did today

it also helps to apply these concepts in

the context of a real example which is

another thing we will strive to do

moving forward

regardless it is important to keep in

mind that the main goal here is not to

learn how to implement a specific data

structure or algorithm off the top of

your head i'll be honest i had to look

up a couple code snippets for a few of

the algorithms myself in writing this

course

but in going through this you now know

that binary search exists and can apply

to a problem where you need a faster

search algorithm

unlike most courses where you can

immediately apply what you have learned

to build something cool learning about

algorithms and data structures will pay

off more in the long run

the second thing we learned about is how

to define and implement algorithms we've

gone over these guidelines several times

i won't bore you here again at the end

but i will remind you that if you're

often confused about how to effectively

break down a problem in code to

something more manageable following

those algorithm guidelines is a good

place to start

next we learned about big o and

measuring the time complexity of

algorithms this is a mildly complicated

topic but once you've abstracted the

math away it isn't as hazy a topic as it

seems

now don't get me wrong the math is

pretty important but only for those

designing and analyzing algorithms

our goal is more about how to understand

and evaluate algorithms

we learned about common run times like

constant linear logarithmic and

quadratic runtimes these are all fairly

new concepts but in time you will

immediately be able to distinguish the

runtime of an algorithm based on the

code you write and have an understanding

of where it sits on an efficiency scale

you will also in due time internalize

runtimes of popular algorithms like the

fact that binary search runs in

logarithmic time and constant space

and be able to recommend alternative

algorithms for a given problem

all in all over time the number of tools

in your tool belt will increase

next we learned about two important

search algorithms and the situations in

which we select one over the other

we also implemented these algorithms in

code so that you got a chance to see

them work

we did this in python but if you are

more familiar with a different language

and haven't gotten the chance to check

out the code snippets we've provided you

should try your hand at implementing it

yourself it's a really good exercise to

go through

finally we learned about an important

concept and a way of writing algorithmic

code through recursion recursion is a

tricky thing and depending on the

language you write code with you may run

into it more than others

it is also good to be aware of because

as we saw in our implementation of

binary search

whether recursion was used or not

affected the amount of space we used

don't worry if you don't fully

understand how to write recursive

functions i don't truly know either the

good part is you can always look these

things up and understand how other

people do it

anytime you encounter recursion in our

courses moving forward you'll get a full

explanation of how and why the function

is doing what it's doing

and that brings us to the end of this

course i'll stress again that the goal

of this course was to get you prepared

for learning about more specific

algorithms by introducing you to some of

the tools and concepts you will need

moving forward

so if you're sitting there thinking i

still don't know how to write many

algorithms or how to use algorithmic

thinking that's okay we'll get there

just stick with it

as always have fun and happy coding

[Music]

hi my name is passant i'm an instructor

at treehouse and welcome to the

introduction to data structures course

in this course we're going to answer one

fundamental question why do we need more

data structures than a programming

language provides

before we answer that question some

housekeeping if you will

in this course we're going to rely on

concepts we learned in the introduction

to algorithms course

namely big-o notation space and time

complexity and recursion

if you're unfamiliar with those concepts

or just need a refresher check out the

prerequisites courses listed

in addition this course does assume that

you have some programming experience

we're going to use data structures that

come built into nearly all programming

languages as our point of reference

while we will explain the basics of how

these structures work we won't be going

over how to use them in practice

if you're looking to learn how to

program before digging into this content

check the notes section of this video

for helpful links

if you're good to go then awesome let's

start with an overview of this course

the first thing we're going to do is to

explore a data structure we are somewhat

already familiar with arrays

if you've written code before there's a

high chance you have used an array

in this course we're going to spend some

time understanding how arrays work what

are the common operations on an array

and what are the run times associated

with those operations

once we've done that we're going to

build a data type of our own called a

linked list

in doing so we're going to learn that

there's more than one way to store data

in fact there's way more than just one

way

we're also going to explore what

motivates us to build specific kinds of

structures and look at the pros and cons

of these structures

we'll do that by exploring four common

operations accessing a value searching

for a value inserting a value and

deleting a value

after that we're actually going to

circle back to algorithms and implement

a new one a sorting algorithm

in the introductions to algorithms

course we implemented a binary search

algorithm a precondition to binary

search was that the list needed to be

sorted

we're going to try our hand at sorting a

list and open the door to an entirely

new category of algorithms

we're going to implement our sorting

algorithm on two different data

structures and explore how the

implementation of one algorithm can

differ based on the data structure being

used

we'll also look at how the choice of

data structure potentially influences

the run time of the algorithm

in learning about sorting we're also

going to encounter another general

concept of algorithmic thinking called

divide and conquer

along with recursion dividing conquer

will be a fundamental tool that we will

use to solve complex problems all in due

time in the next video let's talk about

arrays

a common data structure built into

nearly every programming language is the

array

arrays are a fundamental data structure

and can be used to represent a

collection of values but it is much more

than that arrays are also used as

building blocks to create even more

custom data types and structures

in fact in most programming languages

text is represented using the string

type and under the hood strings are just

a bunch of characters stored in a

particular order in an array

before we go further and dig into arrays

what exactly is a data structure

a data structure is a way of storing

data when programming it's not just a

collection of values and the format

they're stored in but the relationship

between the values in the collection as

well as the operations applied on the

data stored in the structure

an array is one of very many data

structures in general an array is a data

structure that stores a collection of

values where each value is referenced

using an index or a key

a common analogy for thinking about

arrays is as a set of train cars

each car has a number and these cars are

ordered sequentially

inside each car the array or the train

in this analogy stores some data

while this is the general representation

of an array it can differ slightly from

one language to another but for the most

part all these fundamentals remain the

same in a language like swift or java

arrays are homogeneous containers which

means they can only contain values of

the same type

if you use an array to store integers in

java it can only store integers

in other languages arrays are

heterogeneous structures that can store

any kind of value in python for example

you can mix numbers and text with no

issues

now regardless of this nuance the

fundamental concept of an array is the

index

this index value is used for every

operation on the array from accessing

values to inserting updating and

deleting

in python the language we're going to be

using for this course it's a tiny bit

confusing

the type that we generally refer to as

an array in most languages is best

represented by the list type in python

python does have a type called array as

well but it's something different so

we're not going to use it

while python calls it a list when we use

a list in this course we'll be talking

about concepts that apply to arrays as

well in other languages so definitely

don't skip any of this there's one more

thing

in computer science a list is actually a

different data structure than an array

and in fact we're going to build a list

later on in this course

generally though this structure is

called a linked list as opposed to just

list so hopefully the terminology isn't

too confusing

to properly understand how arrays work

let's take a peek at how arrays are

stored under the hood

an array is a contiguous data structure

this means that the array is stored in

blocks of memory that are right beside

each other with no gaps

the advantage of doing this is that

retrieving values is very easy

in a non-contiguous data structure we're

going to build one soon the structure

stores a value as well as a reference to

where the next value is

to retrieve that next value the language

has to follow that reference also called

a pointer to the next block of memory

this adds some overhead which as you

will see increases the runtime of common

operations a second ago i mentioned that

depending on the language arrays can

either be homogeneous containing the

same type of value or heterogeneous

where any kind of value can be mixed

this choice also affects the memory

layout of the array

for example in a language like c swift

or java where arrays are homogeneous

when an array is created since the kind

of value is known to the language

compiler and you can think of the

compiler as the brains behind the

language

it can choose a contiguous block of

memory that fits the array size and

values created

if the values were integers assuming an

integer took up space represented by one

of these blocks then for a five item

array the compiler can allocate five

blocks of equally sized memory

in python however this is not the case

we can put any value in a python list

there's no restriction

the way this works is a combination of

contiguous memory and the pointers or

references i mentioned earlier

when we create a list in python there is

no information about what will go into

that array which makes it hard to

allocate contiguous memory of the same

size

there are several advantages to having

contiguous memory

since the values are stored beside each

other accessing the values happens in

almost constant time so this is a

characteristic we want to preserve

the way python gets around this is by

allocating contiguous memory and storing

init not the value we want to store but

a reference or a pointer to the value

that's stored somewhere else in memory

by doing this it can allocate equally

sized contiguous memory since regardless

of the value size the size of the

pointer to that value is always going to

be equal this incurs an additional cost

in that when a value is accessed we need

to follow the pointer to the block of

memory where the value is actually

stored but python has ways of dealing

with these costs that are outside the

scope of this course

now that we know how an array stores its

values let's look at common operations

that we execute on an array

regardless of the kind of data structure

you work with all data structures are

expected to carry out four kinds of

operations at minimum

we need to be able to access and read

values stored in the structure we need

to be able to search for an arbitrary

value

we also need to be able to insert a

value at any point into the structure

and finally we need to be able to delete

structures

let's look at how these operations are

implemented on the array structure in

some detail starting with access

elements in an array are identified

using a value known as an index and we

use this index to access and read the

value

most programming languages follow a

zero-based numbering system when it

comes to arrays and all this means is

that the first index value is equal to

zero not one

generally speaking when an array is

declared a base amount of contiguous

memory is allocated as the array storage

computers refer to memory through the

use of an address but instead of keeping

a reference to all the memory allocated

for an array the array only has to store

the address of the first location

because the memory is contiguous using

the base address the array can calculate

the address of any value by using the

index position of that value as an

offset

if you want to be more specific think of

it this way

let's say we want to create an array of

integers and then each integer takes up

a certain amount of space in memory that

we'll call m

let's also assume that we know how many

elements we're going to create so the

size of the array is some number of

elements we'll call n

the total amount of space that we need

to allocate is n times the space per

item m

if the array keeps track of the location

in memory where the first value is held

so let's label that m0 then it has all

the information it needs to find any

other element in the list

when accessing a value in an array we

use the index

to get the first element in the list we

use the zeroth index to get the second

we use the index value 1 and so on

given that the array knows how much

storage is needed for each element it

can get the address of any element by

starting off with the address for the

first element and adding to that the

index value times the amount of storage

per element

for example to access the second value

we can start with m0 and to that add m

times the index value 1 giving us m1 as

the location in memory for the second

address

this is a very simplified model but

that's more or less how it works

this is only possible because we know

that array memory is contiguous with no

gaps

let's switch over to some code

as i mentioned earlier we're going to be

using python in this course

if you don't know how to code or you're

interested in this content but know a

language other than python check the

notes section of this video for more

information while the code will be in

python the concepts are universal and

more importantly simple enough that you

should have no issue following along in

your favorite programming language

and to get started click on the launch

workspaces button on the video page that

you're watching right now

this should spin up an instance of a

treehouse workspace an in-browser coding

environment right now your workspace

should be empty and that's expected so

let's add a new file in here i'm going

to go to file new file

and we'll call this arrays

dot py pi

creating a list in python is quite

simple so we'll call this new underscore

list

we use a set of square brackets around a

set of values to create a list so one

and we comma separate them so space two

and space three this allocates a base

amount of memory for the array to use or

when i say array know that in python i

mean a list

since this is python the values aren't

stored in memory

instead the values 1 2 and 3 are stored

elsewhere in memory and the array stores

references to each of those objects

to access a value we use a subscript

along with an index value so to get the

first value we use the index 0 and if we

were to assign this to another variable

we would say result

equal new list

we write out new lists since this is the

array that we're accessing the value

from and then a subscript notation which

is a square bracket

and then the index value

as we saw since the array has a

reference to the base location in memory

the position of any element can be

determined pretty easily

we don't have to iterate over the entire

list

all we need to do is a simple

calculation of an offset from the base

memory since we're guaranteed that the

memory is contiguous

for this reason access is a constant

time operation on an array or a python

list

this is also why an array crashes if you

try to access a value using an index

that is out of bounds of what the array

stores

if you've used an array before you've

undoubtedly run into an error or a crash

where you try to access a value using an

index that was larger than the number of

elements in the array since the array

calculates the memory address on the fly

when you access a value with an out of

bounds index as it's called the memory

address returned is not one that's part

of the array structure and therefore

cannot be read by the array now in

python this is represented by an index

error and we can make this happen by

using an index we know our array won't

contain

now i'm writing out my code here inside

of a text editor which obviously doesn't

run the code so let's drag up this

console area here

and i'm going to write python

to bring up the python interpreter

and in here we can do the same thing so

i can say new

list equal one

comma two comma three and now this is an

interpreter so it's actually going to

evaluate our code

all right so now we have a new list if i

type out new list it gets printed out

into the console

okay i can also do new list square

bracket 0 and you'll see that i get the

value 1 which is the value stored at the

zeroth index

now to highlight that index error we can

do new list

and inside the square brackets we can

provide an index that we know our array

doesn't contain so here i'll say index

10

and if i hit enter you'll see it say

index error list index out of range

and those are the basics of how we

create and read values from an array in

the next video let's take a look at

searching

in the last video we learned what

happens under the hood when we create an

array and read a value using an index

in this video we're going to look at how

the remaining data structure operations

work on arrays

if you took the introduction to

algorithms course we spent time learning

about two search algorithms linear

search and binary search

while arrays are really fast at

accessing values they're pretty bad at

searching

taking an array as is the best we can do

is use linear search for a worst case

linear runtime linear search works by

accessing and reading each value in the

list until the element in concern is

found

if the element we're looking for is at

the end of the list then every single

element in the list will have been

accessed and compared

even though accessing and comparing our

constant time operations having to do

this for every element results in an

overall linear time

let's look at how search works in code

in python we can search for an item in

an array in one of two ways

we can use the in operator to check

whether a list contains an item so i can

say if

one in new underscore

list

then print

true

the in operator actually calls a

contains method that is defined on the

list type which runs a linear search

operation

in addition to this we can also use a

for loop to iterate over the list

manually and perform a comparison

operation

so i can say

for

n in new list

if n equals one then print

true

and then after that break out of the

loop

this is more or less the implementation

of linear search

if the array were sorted however we

could use binary search but because sort

operations incur a cost of their own

languages usually stay away from sorting

the list and running binary search since

for smaller arrays linear search on its

own may be faster

now again remember that

since this is an editor this is just a

text file none of these lines of code

are evaluated so you can try that out in

here so we'll copy that we can come down

here and say python and hit enter and

then when it starts up we can paste in

our list

and now we can try what we just did so

if one in new list

print

true

and there you go it prints true now

because we've already learned about

linear and binary search in a previous

course there's nothing new going on here

what's more interesting to look at in my

opinion is inserting and deleting values

in an array let's start with inserting

in general most array implementations

support three types of insert operations

the first is a true insert using an

index value where we can insert an

element anywhere in the list this

operation has a linear runtime imagine

you wanted to insert an item at the

start of the list when we insert into

the first position what happens to the

item that is currently in that spot

well it has to move to the next spot at

index value one what happens to the

second item at index position one

that one moves to the next spot at index

position two

this keeps happening until all elements

have been shifted forward one index

position

so in the worst case scenario inserting

at the zeroth position of an array every

single item in the array has to be

shifted forward and we know that any

operation that involves iterating

through every single value means a

linear runtime

now the second way we can insert an item

into an array is by appending appending

although technically an insert operation

in that it inserts an item into an

existing array doesn't incur the same

runtime cost because appends simply add

the item to the end of the list

we can simplify and say that this is

constant time this is a constant time

operation but it depends on the language

implementation of array

to highlight why that matters let's

consider how lists in python work in

python when we create a list the list

doesn't know anything about the size of

the list and how many elements we're

going to store

creating a new empty list like so so

numbers equal and two empty brackets

so this creates a list and allocates a

space of size n plus one

since n here is zero there are no

elements in this array in this list

space is allocated for a one element

list to start off

because the space allocated for the list

and the space used by the list are not

the same

what do you think happens when we ask

python for the length of this list so i

can say len numbers

we correctly get 0 back

this means that the list doesn't use the

memory allocation as an indicator of its

size because as i mentioned it has

allocated space for a one element list

but it returns zero so it determines it

in other ways

okay so numbers this list currently has

space for one element

let's use the append method defined on

the type to insert a number at the end

of the list so you can say numbers dot

append and i'll pass in 2.

now the memory allocation and the size

of the list are the same since the list

contains one element

now what if i were to do something like

this numbers.append

there needs to be a dot

and i'll add another value 200.

now since the list only has an

allocation for one item at this point

before it can add the new element to the

list it needs to increase the memory

allocation and thereby the size of the

list it does this by calling a list

resize operation list resizing is quite

interesting because it shows the

ingenuity in solving problems like this

python doesn't resize the list to

accommodate just the element we want to

add

instead in this case it would allocate

four blocks of memory to increase the

size to a total of four contiguous

blocks of memory

it does this so that it doesn't have to

resize the list every single time we add

an element but at very specific points

the growth pattern of the list type in

python is 0 4 8 16 25 35 46 and so on

this means that as the list size

approaches these specific values

resize is called again if you look at

when the size of the list is four

this means that when appending four more

values until the size of eight

each of those append operations do not

increase the amount of space taken

at specific points however when resizing

is triggered space required increases as

memory allocation increases

this might signify that the append

method has a non-constant space

complexity but it turns out that because

some operations don't increase space and

others do

when you average all of them out append

operations take constant space

we say that it has an amortized constant

space complexity this also happens with

insert operations

if we had a four element array we would

have four elements and a memory

allocation of four

an insert operation at that point

doesn't matter where it happens on the

list but at that point it would trigger

a resize

inserting is still more expensive though

because after the resize every element

needs to be shifted over one

the last insert operation that is

supported in most languages is the

ability to add one list to another

in python this is called an extend and

looks like this

so i'll say numbers now if you let me

actually clear out the console

oh actually you will let's exit python

we'll clear this out so we're back at

the top and we'll start again

so i'll say numbers

and we'll set it to an empty list and

now we can say numbers dot extend

and as an argument we're going to pass

in a new list entirely so here we'll say

4 comma 5 comma 6

and then once i hit enter if i were to

print out numbers you'll see that it now

contains the values 4 5 and 6.

so extend takes another list to add

extend effectively makes a series of

append calls on each of the elements in

the new list until all of them have been

appended to the original list this

operation has a run time of big o of k

where k represents the number of

elements in the list that we're adding

to our existing list

the last type of operation we need to

consider are delete operations deletes

are similar to inserts in that when a

delete operation occurs the list needs

to maintain correct index values so

where an insert shifts every element to

the right a delete operation shifts

every element to the left

just like an insert as well if we delete

the first element in the list every

single element in the list needs to be

shifted to the left

delete operations have an upper bound of

big o of n also known as a linear

runtime now that we've seen how common

operations work on a data structure that

we're quite familiar with let's switch

tracks and build our own data structure

[Music]

over the next few videos we're going to

build a data structure that you may have

worked with before a linked list

before we get into what a linked list is

let's talk about why we build data

structures instead of just using the

ones that come built into our languages

each data structure solves a particular

problem

we just went over the basics of the

array data structure and looked at the

cost of common operations that we carry

out on arrays

we found that arrays were particularly

good at accessing reading values happens

in constant time but arrays are pretty

bad at inserting and deleting both of

which run in linear time

linked lists on the other hand are

somewhat better at this although there

are some caveats and if we're trying to

solve a problem that involves far more

inserts and deletes than accessing a

linked list can be a better tool than an

array

so what is a linked list

a linked list is a linear data structure

where each element in the list is

contained in a separate object called a

node a node models two pieces of

information an individual item of the

data we want to store and a reference to

the next node in the list

the first node in the linked list is

called the head of the list while the

last node is called the tail

the head and the tail nodes are special

the list only maintains a reference to

the head although in some

implementations it keeps a reference to

the tail as well

this aspect of linked lists is very

important and as you'll see most of the

operations on the list need to be

implemented quite differently compared

to an array

the opposite of the head the tail

denotes the end of the list

every node other than the tail points to

the next node in the list but tail

doesn't point to anything this is

basically how we know it's the end of

the list nodes are what are called

self-referential objects the definition

of a node includes a link to another

node and self-referential here means the

definition of node includes the node

itself linked lists often come in two

forms a singly linked list where each

node stores a reference to the next node

in the list or a doubly linked list

where each node stores a reference to

both the node before and after if an

array is a train with a bunch of cars in

order then a linked list is like a

treasure hunt

when you start the hunt you have a piece

of paper with the location of the first

treasure you go to that location and you

find an item along with a location to

the next item of treasure

when you finally find an item that

doesn't also include a location you know

that the hunt has ended

now that we have a high level view of

what a linked list is let's jump into

code and build one together we'll focus

on building a singly linked list for

this course there are advantages to

having a doubly linked list but we don't

want to get ahead of ourselves

let's start here by creating a new file

we're going to put all our code for our

linked list so we'll call this linked

underscore list

dot pi and first we're going to create a

class to represent a node

say class

node

now node is a simple object in that it

won't model much so first we'll add a

data variable

it's an instance variable here called

data and we'll assign the value none

initially

and then we'll add one more we'll call

this next node and to this we'll assign

none as well so we've created two

instance variables data to hold on to

the data that we're storing and next

node to point to the next node in the

list

now we need to add a constructor to make

this class easy to create so we'll add

an init

method here that takes self and some

data to start off

and all we're going to do is assign

data to that instance variable we

created so that's all we need to model

node

before we do anything else though let's

document this so right after the class

definition let's create a docs string so

three quotes

next line and we'll say an object

for storing

a single

node of a linked list

and then on the next line we'll say

models two attributes

data

and

the link to the next

node in the list

and then we'll close this doc string off

with three more quotation marks okay

using the node class is fairly

straightforward so we can create a new

instance of node with some data to store

now the way we're going to do this is

we're going to bring up the console

and we're going to type out like we've

been typing out before python followed

by the name of the script that we wrote

which is linked list linked underscore

list.pi but before we do that we're

going to pass an argument to the python

command we're going to say dash or

python i and then the name of the script

linked underscore list dot pi so what

this does is this is going to run the

python repl

the read evaluate print loop in the

console but it's going to load the

contents of our file into that so that

we can use it

so i'll hit enter and we have a new

instance going and now we can use the

node in here so we can say n1

equal node

and since we defined that constructor we

can pass it some data so we'll say 10

here

now if we try to inspect this object the

representation returned isn't very

useful

which will make things really hard to

debug as our code grows so for example

if i type out n1 you'll see that

we have a valid instance here but it's

not very helpful the way it's printed

out

so we can customize this by adding a

representation of the object using the

wrapper function now in the terminal

still we'll type out exit

like that hit enter to exit the console

and then down here

let's add in some room

okay and here we'll say def

double underscore

wrapper another set of double

underscores

and then this function takes the

argument self

and in here we can provide a string

representation of what we want printed

to the console when we inspect that

object inside of it inside of a console

so here we'll say return

again

this is a string representation so

inside quotes we'll say

node so this represents a node instance

and the data it contains here we'll say

percent s

which is a python way of substituting

something into a string string

interpolation and outside of the string

we can say percent again

and here we're saying we want to replace

this percent s with

self.data okay

let's hit save and before we move on

let's verify that this works so i'm

going to come in here

type clear to get rid of everything

and then we'll do what we did again and

you can just hit the up arrow a couple

times to get that command

all right so hit enter and now just so

you know every time you run this you

start off you know from scratch so n1

that we created earlier not there

anymore so let's go ahead and create it

n1 equal node

10

and we can type n1 again and hit enter

and you have a much better

representation now so we can see that we

have a node and it contains the data 10.

we can also create another one n2 equal

node that contains the data 20 and now

we can say n1.next n1.nextnode

equal n2 so n1 now points to n2 and if

we say n1.nextnode

you'll see that it points to that node

the node containing 20.

nodes are the building blocks for a list

and now that we have a node object we

can use it to create a singly linked

list so again i'm going to exit out of

this

and then go back to the text editor

and here we'll create a new class so

class

linked

list

the linked list class is going to define

a head and this attribute models the

only node that the list is going to have

a reference to so here we'll say head

and we'll assign none initially and then

like we did earlier let's create a

constructor

so double underscore init double

underscore this takes self

and then inside like before we'll say

self dot head

equal none this is the same

as doing this so we can actually get rid

of that and just use the constructor

okay so again this head attribute models

the only node that the list will have a

reference to since every node points to

the next node to find a particular node

we can go from one node to the next in a

process called list traversal

so in the class constructor here we've

set the default value of head to none so

that new lists created are always empty

again you'll notice here that i didn't

explicitly declare the head attribute at

the top of the class definition

and don't worry that's not an oversight

the self.head in the initializer means

that it's still created okay so that's

all there is to modeling a linked list

now we can add methods that make it

easier to use this data structure

first a really simple docstring to

provide some information

so here we'll to create a docstring

three quotation marks

and then we'll say singly linked list

and then close it off

a common operation carried out on data

structures is checking whether it

contains any data or whether it's empty

at the moment to check if a list is

empty we would need to query these

instance variables head and so on every

time

ideally we would like to not expose the

inner workings of our data structure to

code that uses it

instead let's make this operation more

explicit by defining a method so we'll

say def is empty

and this method takes self as an

argument and here we'll say return

self.head double equal none

all we're doing here is checking to see

if head is none

if it is this condition evaluates to

true which indicates the list is empty

now before we end this video let's add

one more convenience method to calculate

the size of our list the name

convenience method indicates that what

this method is doing is not providing

any additional functionality that our

data structure can't handle right now

but instead making existing

functionality easier to use

we could calculate the size of our

linked list by traversing it every time

using a loop until we hit a tail node

but doing that every time is a hassle

okay so we'll call this method

size and as always it takes self

unlike calling len on a python list not

to be confused with a linked list which

is a constant time operation our size

operation is going to run in linear time

the only way we can count how many items

we have is to visit each node and call

next until we hit the tail node

so we'll start by getting a reference to

the head we'll say current

equal self.head let's also define a

local variable named count with an

initial value of 0 that will increment

every time we visit a node once we hit

the tail count will reflect the size of

that list

next we'll define a while loop that will

keep going until there are no more nodes

so say while current

while current is the same as writing out

while current does not equal none but

it's more succinct so we'll go with this

former

if the ladder is more precise for you

you can go with that

now inside this loop we'll increment the

count value so count plus equal one

plus equal if you haven't encountered it

before is the same as writing count

equal count plus one so if count is zero

initially so it's zero plus one is one

and then we'll assign that back to count

okay so count plus equal one

next we're going to assign the next node

in the list to current so current equal

current dot next

node

this way once we get to the tail and

call next node current will equal none

and the while loop terminates so the end

we can return

count

as you can see we need to visit every

node to determine the size meaning our

algorithm runs in linear time so let's

document this

up in our docs string which we'll add

now to size

we'll say

returns

the number of nodes in the list

takes

linear time

let's take a break here we can now

create lists check if they're empty and

check the size

in the next video let's start

implementing some common operations

at the moment we can create an empty

list but nothing else let's define a

method to add data to our list

technically speaking there are three

ways we can add data to a list

we can add nodes at the head of the list

which means that the most recent node we

created will be the head and the first

node we created will be the tail

or we could flip that around most recent

nodes are the tail of the list and the

first node to be added is the head i

mentioned that one of the advantages of

linked lists over arrays is that

inserting data into the list is much

more efficient than to the array

this is only true if we're inserting at

the head or the tail

technically speaking this isn't an

insert and you'll often see this method

called add prepend if the data is added

to the head or append if it's added to

the tail

a true insert is where you can insert

the data at any point in the list which

is our third way of adding data we're

going to circle back on that if we

wanted to insert at the tail then the

list needs a reference to the tail node

otherwise we would have to start at the

head and walk down the length of the

list or traverse it to find the tail

since our list only keeps a reference to

the head we're going to add new items at

the head of the list

now before we add our new method i

forgot that i didn't show you in the

last video how to actually use the code

we just added and how to check every

time you know when we add new code that

it works correctly

so like before we're gonna bring up the

console and here we're gonna say python

dash i

linked underscore list dot pi which

should load it

load the contents of our file

and now we'll start here by creating a

linked list so l equal linked list

and then we'll use a node so n1 equal

node

with the value 10

and now we can assign n1 to the nodes or

to the linked lists head attribute so l1

dot head equal n1

and then

we can see if size works correctly so if

we call l1 dot size and since this is a

method we need a set of parentheses at

the end

and enter you'll see that we get back

one correctly okay so it works

now let's add our new method which we're

going to call add

add is going to accept some data to add

to the list inside of a node

so we'll say def

add

and every python method takes self as an

argument and then we want to add some

data to this node so we're going to say

data for the second argument

inside the method first we'll create a

new node to hold on to the data so new

underscore node equal

node with the data

before we set the new node as the head

of the list we need to point the new

node's next property at whatever node is

currently at head this way when we set

the new node as the head of the list we

don't lose a reference to the old head

so new underscore node dot next node

equal self.head

now if there was no node at head this

correctly sets next node to none

now we can set the new node as the head

of the node so say self.head equal

new underscore node because the insert

operation is simply a reassignment of

the head and next node properties this

is a constant time operation so let's

add that in as a docs string

first what the method does so it adds a

new node

containing data

at the head of the list

this operation takes

constant time which is our best case

scenario

okay let's test this out so i'm going to

bring the console back up we'll exit out

of

our current reply

and we'll load

the contents of the file again

and now we don't need to create a node

like we did earlier so we can say l

equal linked

list

l.add one

okay let's see if this works we'll call

size

and if it worked

the linked list should now have a size

of one there we go you can also do

l.add2

l.add three

and l dot size should now be three there

we go now if we i were to type l and

just hit print

again what we get in the repel is

nothing useful

so like before we'll implement the

wrapper function for our linked list

now

i'm just going to copy paste this in and

we'll walk through it

okay so this is what our implementation

of wrapper looks like for the linked

list object you can grab this code from

the notes section of this video

okay so at the top you'll see a docs

string where it says it returns a string

representation of the list and like

everything we need to do with a linked

list we need to traverse it so this is

going to take linear time we start by

creating an empty list now i need to

distinguish this is a python list not a

linked list so we create an empty list

called nodes and two nodes we're going

to add strings that have a description

that provide a description of each node

but we're not going to use the

description that we implemented in the

node class because we're going to

customize it a bit here

next we start by assigning self.head to

current so we sort of have a pointer to

the head node as long as current does

not equal none which means we're not at

the tail we're going to implement some

logic

so in the first scenario if the node

assigned to current is the same as the

head

then we're going to append this string

to our nodes list

and the string is simply

going to say that hey this is a head

node and it contains some data which

will extract using current.data

next scenario is if the node assigned to

current's next node is none meaning

we're at the tail node then we'll assign

a different kind of string so it's the

same as earlier except we're saying tail

here and then finally in any other

scenario which means we're not at the

head or not of the tail we'll simply

print the node's value inside and again

we'll extract it using current.data with

every iteration of the loop we'll move

current forward by calling

current.nextnode and reassigning it

and then at the very end when we're done

we'll join all the strings that are

inside the nodes list together using the

python join method and we'll say that

with every join so when you join these

two strings together to make one string

you need to put this set of characters

in between all right so let's see what

this looks like

so i'm going to come down here exit out

of the console again

clear it out

load the contents of the file again and

let's try that so we'll say l equal

linked list

all right so l dot add one l dot add two

l dot add three that seems enough

and then now if i type out l and hit

enter we get a nice string

representation of the list so you can

see that we add every new node to the

head so we added one first one ends up

being the tail because it keeps getting

pushed out

then two and then finally three so three

is at the head

so far we've only implemented a single

method which functions much like the

append method on a python list or an

array

except it adds it to the start of the

linked list it pre-pens it

like append this happens in constant

time in the next video let's add the

ability to search through our list for

the search operation we're going to

define a method that takes a value to

search for and returns either the node

containing the value if the value is

found or none if it isn't

so right after actually you know what

we'll make sure wrapper is the last

function our last method

in our class so we'll add it above it so

here we'll say def search

self

and then key

in the last video we implemented the

wrapper method to provide a string

representation of the list

so we're going to use similar logic here

to implement the search function we'll

start by setting a local variable

current to point to the head of the list

while the value assigned to current is a

valid node that is it isn't none

we'll check if the data on that node

matches the key that we're searching for

so while current

we'll say if

current.data

is the key

then we'll return current

if it does match we'll go ahead and

return it like we've done here but if it

doesn't we'll assign the next node in

the list to current and check again so

say else

current equal current dot next node

once we hit the tail node and haven't

found the key

current gets set to none and the while

loop exits

at this point we know the list doesn't

contain the key so we can return

none

okay that completes the body of our

method

let's add a docs string to document this

so up at the top we'll say search

for the first node

containing data that matches

the key

now this is important because if our

linked list contains more than one node

with the same value it doesn't matter

we're going to return the first one with

this implementation

we'll also say here that it returns the

node or none

if not found

in the worst case scenario we'll need to

check every single node in the list

before we find the key or fail and as a

result this operation runs in linear

time so i'll say takes

o of n or linear time

so far we haven't seen anything that

indicates this data structure has any

advantage over an array or a python list

but we knew that

i mentioned the strength of linked lists

comes in inserts and deletes at specific

positions we'll check that out in the

next video but as always before we end

this one let's make sure everything

works

so we'll load the contents of the file

again

l equal linked

list

and then we'll say l.add 10

l dot add

20 2 doesn't matter l dot add

45 and one more metal dot add

15.

now we can say

l.search and we need to give it a value

so we'll say 45 and this returns a node

or none so we'll say n equal

and then we'll hit enter if this works

n should be a node

okay weirdly n

does not work here

at least it says it's not a node which

means i made a mistake in typing out our

code

and looking at it immediately it's

fairly obvious so this return none needs

to be outside of the while loop okay so

i'm going to hit save now so make sure

it's on the same indentation here which

means it's outside the while loop

and then we'll run through this again

okay so l is linked list

l.add 10

l dot add 2

l.add

45 and what was the last one we did i

believe it was 15

and now we should be able to say

l.search remember we're assigning this

to a node to a variable so l.search

45

and there you go we get that node back

and we can hit l

and we'll see a representation of our

list

okay so again in the next video inserts

and deletes at specific positions

insert operations on linked lists are

quite interesting

unlike arrays where when you insert an

element into the array all elements

after the particular index need to be

shifted with a linked list we just need

to change the references to next on a

few nodes and we're good to go

since each node points to the next one

by swapping out these references we can

insert a node at any point in the list

in constant time

much like binary search though there's a

catch

to find the node at that position we

want to insert we need to traverse the

list and get to that point

we just implemented our search algorithm

for the linked list type and we know

that this runs in linear time so while

actually inserting is fast finding the

position in the list you want to insert

it is not

this is why i mentioned that there were

some caveats to inserting

anyway let's see what this looks like in

code

we'll define a method named insert that

takes data to insert along with an index

position so we'll do this after search

right here

say def

insert

and this takes some data to insert and a

position to insert it at

you may be thinking wait a minute linked

lists don't have index positions right

and you're correct but we can mimic that

behavior by just counting the number of

times we access next node

if the index value passed into this

argument is 0 that means we want to

insert the new node at the head of the

list this is effectively the same

behavior as calling add which means the

logic is the same so we don't need to

repeat it we can call the add method we

wrote earlier so we'll say if

index if index equals 0 or if index is 0

then self dot add

data

if the index is greater than 0 then we

need to traverse the list to find the

current node at that index

so if index is greater than zero

now before we do that we need to create

a new node containing the data we want

to insert so we'll say new equal node

with some data

i'm going to assign index the argument

passed to our function to a local

variable named position and the head of

the list to a variable named current

position

equal index

current equal self.head

every time we call

current.nextnode meaning we're moving to

the next node in the list we'll decrease

the value of position by 1.

when position is zero we'll have arrived

at the node that's currently at the

position we want to insert in

in reality though we don't want to

decrease it all the way to zero

imagine we have a list with five nodes

and we want to insert a node at position

3. to insert a node at position 3 we

need to modify the nodes at positions 2

and 3.

node 2's next node attribute is going to

point to the new node and the new node's

next node attribute will point to node

3.

in this way an insert is a constant time

operation we don't need to shift every

single element we just modify a few next

node references

in a doubly linked list we can use node

3 to carry out both of these operations

node 3 in a doubly linked list would

have a reference to node 2 and we can

use this reference to modify all the

unnecessary links

and a singly linked list though which is

what we have if we kept decreasing

position until we're at 0 we arrive at

node 3.

we can then set the new node's next node

property to point to node 3 but we have

no way of getting a reference to node 2

which we also need

for this reason it's easier to decrease

position to just 1 when it equals 1 and

stop at node 2. so in here we'll say

while

position

is greater than one

now while the position is greater than

one we'll keep calling next node and

reassigning the current node so current

equal node.next

node and at the same time we'll

decrement position so position

equal to position

minus one which you can also succinctly

write as minus equal

one

this way when the position equals one

the loop exits and current will refer to

the node at the position before the

insert point so outside the while loop

we'll say previous equal current

and next equal current dot next

node

to make things more clear what i've done

here is name the node before the new one

previous and the node after the new one

next

all that's left to do now is to insert

the new node between previous and next

so we'll say previous dot next

node

equal

new

and then new dot next node

equal next

now it seems like there's an issue with

variable naming here and i'm most

probably conflicting with some globally

named next variable so actually go ahead

and call this next node

and

previous node so that we don't mess

things up here

previous node

so the dot next node is obviously the

attribute on a node but this is just a

local variable let's document this

method so up at the top

we'll add a docs string and it will say

inserts a new node

containing

data at index

position

insertion takes

constant time

but finding the node

at the insertion point

takes linear

time

let's add this to the next line

there we go

and then we'll say therefore it takes an

overall

linear time

this is why even though we can easily

insert a new node without having to

shift the rest ultimately adding to

either the head or the tail if you have

a reference is much more efficient

we have one more operation to add to our

linked list that will make it a robust

data structure

much like inserts removing a node is

actually quite fast and occurs in

constant time but to actually get to the

node that we want to remove and modify

the next connections we need to traverse

the entire list in our worst case so in

the worst case this takes linear time

let's add this operation to our data

structure

there are two ways we can define the

remove method one where we provide a key

to remove as an argument and one where

we provide an index now in the former

the key refers to the data the node

stores so in order to remove that node

we would first need to search for data

that matches the key i'm going to

implement that first method which we'll

call remove and i'll leave it up to you

to get some practice in and implement a

remove at index method to complete our

data structure so we'll add this after

the insert method right here

remove

is going to accept a key which we'll

need to search for before we can remove

a node earlier we defined a search

method that found a node containing data

that matches a key but we can't use that

method as is for the implementation of

remove when we remove a node much like

the insert operation we need to modify

the next node references

the node before the match needs to point

to the node after the match

if we use the search method we defined

earlier we get the node we want to

remove as a return value but because

this is a singly linked list we can't

obtain a reference to the previous node

like i said earlier if this was a doubly

linked list we could use the search

method since we would have a reference

to that previous node

we'll start here by setting a local

variable named current to point to the

head let's also define a variable named

previous

that will set to none to keep track of

the previous node as we traverse the

list

finally let's declare a variable named

found that we'll set to false

found is going to serve as a stopping

condition for the loop that we'll define

we'll use the loop to keep traversing

the linked list as long as found is

false meaning we haven't found the key

that we're looking for once we've found

it we'll set found to true and the loop

terminates so let's set up our loop so

we'll say while current

and

not

found

here we're defining a while loop that

contains two conditions

first we tell the loop to keep iterating

as long as current does not equal none

when current equals none this means

we've gone past the tail node and the

key doesn't exist

the second condition asks the loop to

keep evaluating as long as not found

equals true now this might be tricky

because it involves a negation here

right now found is set to false so not

found not false equals true this not

operator flips the value

when we find the key and we set found to

true

not true not found we'll equal false

then and the loop will stop

the end in the while loop means that

both conditions current being a valid

node and not found equalling true both

have to be true

if either one of them evaluates to false

then the loop will terminate

now inside the loop there are three

situations that we can run into

first the key matches the current node's

data and current is still at the head of

the list

this is a special case because the head

doesn't have a previous node and it's

the only node being referenced by the

list let's handle this case so we'll say

if current.data

double equals the key and current

is self.head which you can write out as

current equal self.head or current is

self.head

now if we hit this case

we'll indicate that we found the key by

setting found to true

and then this means that on the next

pass

this is going to evaluate to false

because not true will be false

and then the loop terminates once we do

that we want to remove the current node

and since it's the head node all we need

to do is point head to the second node

in the list which we can get by

referencing the next node attribute on

current self.head equal current.nextnode

so when we do this there's nothing

pointing to that first node so it's

automatically removed the next scenario

is when the key matches data in the node

and it's a node that's not the head

so here we'll say else if current dot

data equal key

if the current node contains the key

we're looking for we need to remove it

to remove the current node we need to go

to the previous node and modify its next

node reference to point to the node

after current

but first we'll set found

to true

and then we'll switch out the references

so

previous.nextnode

equal

current.nextnode

so far we haven't written any code to

keep track of the previous node

we'll do that in our else case here

so if we hit the else case it means that

the current node we're evaluating

doesn't contain the data that matches

the key so in this case we'll make

previous point to the current node and

then set current to the next node so

previous equal current

and current equal current.nextnode

and that's it for the implementation of

remove

now we're not doing anything at the

moment with the node we're removing but

it's common for remove operations to

return the value being removed so at the

bottom

outside the while loop

let's return

current

and with that we have a minimal

implementation of a linked list and your

first custom data structure how cool is

that

there's quite a bit we can do here to

improve our data structure particularly

in making it easy to use but this is a

good place to stop

before we move on to the next topic

let's document our method so the top

another docs string

and here we'll say removes node

containing data that matches the key

also it returns the node or none

if the key doesn't exist

and finally this takes

linear time because in the worst case

scenario we need to search the entire

list

if you'd like to get in some additional

practice implementing functionality for

linked lists two methods you can work on

are remove it index and node at index to

allow you to easily delete or read

values in a list at a given index

now that we have a linked list let's

talk about where you can use them the

honest answer is not a lot of places

linked lists are really useful

structures to build for learning

purposes because they're relatively

simple and are a good place to start to

introduce the kinds of operations we

need to implement for various data

structures it is quite rare however that

you will need to implement a linked list

on your own

there are typically much better and by

that i mean much more efficient data

structures that you can use

in addition many languages like java for

example provide an implementation of a

linked list already

now that we have a custom data structure

let's do something with it let's combine

the knowledge we have and look at how a

sorting algorithm can be implemented

across two different data structures

[Music]

now that we've seen two different data

structures let's circle back and apply

what we know about algorithms to these

new concepts

one of the first algorithms you learned

about was binary search and we learned

that with binary search there was one

precondition the data collection needs

to be sorted

over the next few videos let's implement

the merge sort algorithm which is one of

many sorting algorithms on both arrays

or python lists and the singly linked

list we just created

this way we can learn a new sorting

algorithm that has real world use cases

and see how a single algorithm can be

implemented on different data structures

before we get into code let's take a

look at how merge sort works

conceptually and we'll use an array to

work through this

we start with an unsorted array of

integers and our goal is to end up with

an array sorted in ascending order

merge sort works like binary sort by

splitting up the problem into sub

problems but it takes the process one

step further

on the first pass we're going to split

the array into two smaller arrays now in

binary search one of these subarrays

would be discarded but that's not what

happens here

on the second pass we're going to split

each of those subarrays into further

smaller evenly sized arrays and we're

going to keep doing this until we're

down to single element arrays

after that the merge sort algorithm

works backwards repeatedly merging the

single element arrays and sorting them

at the same time

since we start at the bottom by merging

to single element arrays we only need to

make a single comparison to sort the

resulting merge array by starting with

smaller arrays that are sorted as they

grow

merge sort has to execute fewer sort

operations than if it sorted the entire

array at once

solving a problem like this by

recursively breaking down the problem

into subparts until it is easily solved

is an algorithmic strategy known as

divide and conquer but instead of

talking about all of this in the

abstract let's dive into the code this

way we can analyze the runtime as we

implement it

for our first implementation of merge

sort we're going to use an array or a

python list

while the implementation won't be

different conceptually for a linked list

we will have to write more code because

of list traversal and how nodes are

arranged so once we have these concepts

squared away we'll come back to that

let's add a new file here

we'll call this merge underscore sort

dot pi

in our file let's create a new function

named merge sort that takes a list and

remember when i say list unless i

specify linked list i mean a python list

which is the equivalent of an array so

we'll say def

merge underscore sort

and takes a list

in the introduction to algorithms course

we started our study of each algorithm

by defining the specific steps that

comprise the algorithm

let's write that out as a docstring

in here the steps of the algorithm so

that we can refer to it right in our

code

this algorithm is going to sort the

given list in an ascending order so

we'll start by putting that in here as a

simple definition

sorts a list in ascending

order

there are many variations of merge sort

and in the one we're going to implement

we'll create and return a new sorted

list other implementations will sort the

list we pass in and this is less typical

in an operation known as sort in place

but i think that returning a new list

makes it easier to understand the code

now these choices do have implications

though and we'll talk about them as we

write this code

for our next bit of the docs string

let's write down the output of this

algorithm so returns

a new

sorted list

merge sort has three main steps

the first is the divide step where we

find the midpoint of the list so i'll

say divide

find the mid point of the list and

divide

into sub-lists

the second step is the conquer step

where we sort the sub-list that we

created in the divide step so we'll say

recursively

sort the sub-lists created in previous

step

and finally the combine the combined

step where we merge these recursively

sorted sub-lists back into a single list

so merge the sorted sub-lists

created in previous

step

when we learned about algorithms we

learned that a recursive function has a

basic pattern first we start with a base

case that includes a stopping condition

after that we have some logic that

breaks down the problem and recursively

calls itself

our stopping condition is our end goal a

sorted array

now to come up with a stopping condition

or a base case we need to come up with

the simplest condition that satisfies

this end result

so there are two possible values that

fit a single element list or an empty

list

now in both of these situations we don't

have any work to do

if we give the merge sort function an

empty list or a list with one element

it's technically already sorted we call

this naively sorting so let's add that

as our stopping condition we'll say if

len list if the length of the list is

less than or equal to one

then we can return the list

okay so this is a stopping condition

and now that we have a stopping

condition we can proceed with the list

of steps

first we need to divide the list into

sub lists

to make our functions easier to

understand we're going to put our logic

in a couple different functions instead

of one large one so i'll say it left

half

comma right half

equal

split

list so here we're calling a split

function that splits the list we pass in

and returns two lists split at the

midpoint because we're returning two

lists we can capture them in two

variables

now you should know that this split

function is not something that comes

built into python this is a global

function that we're about to write

next is the conquer step where we sort

each sub-list and return a new sorted

sub-list

so we'll say left equal

merge sort

left half

and right equal merge sort

right half

this is the recursive portion of our

function so here we're calling merge

sort on this divided sub list so we

divide the list into two here and then

we call merge sort on it again

this further splits that sublist into

two in the next pass through of merge

sort this is going to be called again

and again and again until we reach our

stopping condition where we have single

element lists or empty lists

when we've subdivided until we cannot

divide any more then we'll end up with a

left and a right half

and we can

start merging backwards so we'll say

return

merge

left and right

that brings us to the combined step

once two sub-lists are sorted and

combined we can return it

now obviously none of these functions

merge merge sort well merge sort is

written but merge and split haven't been

written so all we're going to do here if

we run it is raise an error so in the

next video let's implement the split

operation

the first bit of logic we're going to

write is the divide step of the

algorithm this step is fairly

straightforward and only requires a few

lines of code but is essential to get

the sorting process going

all right so as we saw earlier we're

going to call the function for the

divide step split so we'll say def split

and split is going to take as an

argument a list to split up

let's document how this function works

so we'll say

divide the unsorted list at midpoint

into sub lists and it's always good to

say what we're returning as well so

we'll say returns to sub-lists

left and right

all right so the first step is to

determine the midpoint of this list of

this array

we're going to use the floor division

operator for this

floor division carries out a division

operation and if we get a non-integer

value like 2.5 back it just gets rounded

down to two we'll define the midpoint to

be the length of the list divided by two

and then rounded down

so

lan list

and using the

two forward slashes for the floor

division operator we'll put number two

after it

okay once we have the midpoint we can

use the slicing notation in python to

extract portions of the list we want to

return

for instance we can define left

as the left sub-list that goes all the

way from the start of the list

all the way up to the midpoint without

including the midpoint

now over here we're using the slicing

syntax where it's like using the you

know subscript notation to access a

value from a list but instead we give

two index values as a start and stop

if we don't include a start value as

i've done here python interprets that as

starting from the zeroth index or the

start of the list now similarly we can

define right

[Music]

to be values on the right of the

midpoint so starting at the midpoint and

going all the way up to the end of the

list

so a couple things to note as i said

earlier when you don't include the

starting index it interprets it as to

start at the very beginning of the list

the index you give as the stopping

condition that value is not included in

the slice so over here we're starting at

the very beginning of list and we go all

the way up to midpoint but not including

midpoint and then right starts at

midpoint so it includes that value and

then goes all the way to the end of the

list

now once we have these two sub-lists we

can return them

so we'll return left and right notice

that we're returning two values here and

then in the merge sort function when we

call that split function

we're declaring two variables left half

and right half to assign so that we can

assign these two sub lists to them

okay and that's all there is to the

split function in the next video let's

implement the crucial portion of the

merge sort logic

once we run the split function

recursively over the array we should end

up with several single member or empty

arrays

at this point we need to merge them all

back and sort them in the process which

is what our merge function is for

the merge function is going to take two

arrays or lists as arguments and to

match the naming conventions we used in

the split function we'll call this left

and right as well so we'll say def merge

takes a left and a right list

now like before let's add some

documentation to our function so this

function merges to lists or arrays

sorting them in the process

and then it returns a new merged list

since our function is going to return a

new list let's start by creating one

now in the process of merging we need to

sort the values in both lists

to sort we need to compare values from

each array or each list so next let's

create two local variables to keep track

of index values that we're using for

each list

so the convention here is i and j so

we'll stick to it

so i equals 0 j equals 0.

as we inspect each value in either list

we'll use the variables to keep track of

the indexes of those values so we'll use

i to keep track of indexes in the left

list and j for indexes in the right list

when merging we want to keep sorting the

values until we've worked through both

lists so for our loop let's set up two

conditions with an and operator so we'll

say while

let's just stay up here while i is less

than

while i is less than the length of the

left list

and j

is less than the length

of the right list then we'll keep

executing our loop so here we're

ensuring that as long as i is less than

the length of the left list

and the and is important and j is less

than the length of the right list we're

going to keep executing the code now i

and j are both set to zero initially

which means that our first comparison

operation will be on the first element

of each list respectively so we'll say

if

left i so i zero so this is going to get

the first value out of the left list

is less than right

j

and again here

j is zero so we're going to get the

first value out of the right list now if

the value at index i in the left list is

less than the value at index j in the

right list what do we do well that means

the value being compared in left is less

than the value in the right and can be

placed at position 0 in the new array l

that we created earlier so here we'll

say l dot append

left

i

since we've read and done something with

the value at position i let's increment

that value so we move forward to

evaluate the next item in the left list

i plus one or we can say i plus equal

one okay next is an else statement

and here we'll say

if the value at index i so i don't have

to write out the actual logic because

it's implied so here we're saying that

left the value at left is less than the

value at right now in the else clause if

the value at so i equal

is greater and i haven't written out

that condition because it's implied so

here we're saying if the value in the

left is less than the value in the right

so in the else clause it's going to mean

that the value in the left is either

greater than or equal to the value in

the right but when we hit the else

clause if the value at index i in the

left list is greater

then we place the value at index j from

the right list at the start of the new

one list l

and similarly increment j so here we'll

say l dot append

right

j and then j equal j plus one

doing this doesn't necessarily mean that

in one step we'll have a completely

sorted array but remember that because

we start with single element arrays and

combine with each merge step we will

eventually sort all the values more than

one time and by the time the entire

process is done all the values are

correctly sorted

now this isn't all we need to do in the

merge step however there are two

situations we can run into one where the

left array is larger than the right and

vice versa so this can occur when an

array containing an odd number of

elements needs to be split so how do you

split a three element array or list well

the left can have two elements and the

right can have one or the other way

around

in either case our while loop uses an

and condition

where the variables used to store the

indexes need to be less than the length

of the lists if the left list is shorter

than the right then the first condition

returns false and the entire loop

returns false because it's an and

condition

this means that in such an event when

the while loop terminates not all the

values in the right list will have been

moved over to the new combined list

so to account for this let's add two

more while loops

the first while loop is going to account

for a situation where the right list is

shorter than the left and the previous

loop terminated because we reached the

end of the right list first

so in this case what we're going to do

is simply add the remaining elements in

the left to the new list

we're not going to compare elements

because we're going to assume that

within a list the elements are already

sorted

so while i

is less than length of left

then

it's the same logic l dot append left

i

and i

plus equal one

so the while loop is going to have the

similar condition keep the loop going

until it's at the last index

inside the body we're incrementing the

index with every iteration of the loop

our final loop accounts for the opposite

scenario where the left was shorter than

the right

the only difference here is that we're

going to use the variable j along with

the right list so we'll say while j

is less than length of right

l dot append

right

j

and j plus equal one okay let's stop

here in the next video let's test out

merge sort make sure our code is running

correctly and everything is written well

and then we'll wrap up this stage by

documenting our code and evaluating the

run time of our algorithm in the last

video we completed our implementation

for the merge sort algorithm but we

didn't test it in any way let's define a

new list at the bottom that contains

several numbers

you can put whatever you want in there

but make sure that the numbers are not

in order i'll call mine a list

and in here

we'll say 54

26 or 62 doesn't matter 93 17

77

31

just add enough so that you can make out

that it's sorted okay next we're going

to call the merge sort algorithm

and pass in our list let's assign this

to some variables so we'll say l equal

merge

underscore sort

a list

and then if it works correctly we should

be able to print this list and see what

it looks like so i'm going to hit save

down here in the console we'll tap out

python

merge sort dot pi

and before i hit enter i actually

noticed i made an error in the last

video but i'll hit enter anyway and you

should see the error pop up okay so what

i forgot to do which is a pretty crucial

part of our algorithm is in the merge

function i forgot to return the list

containing the sorted numbers after

carrying out all this logic

so here at the bottom

we'll say return

l

all right we'll save again

and now we'll clear this out and try

that one more time

and there we go

you should see a sorted list printed out

we can write out a more robust function

to test this because with bigger arrays

visually evaluating that printed list

won't always be feasible so bring this

back down

let's get rid of this

and we'll call our

function verify sorted

and this will take a list

first we're going to check inside the

body of the function we'll check the

length of the list

if the list is a single element list or

an empty list we don't need to do any

unnecessary work because remember it is

naively sorted so we'll say if n

equals 0 or

if n equals

1

then we'll return true we've verified

that it's sorted

now to conclude our function we're going

to write out one line of code that will

actually do quite a bit of work

so first we'll say return

list

zero so we'll take the first element out

of the list and we'll compare and see if

that's less than the second element in

the list okay so first we'll check that

the first element in the list is less

than the second element in the list

this returns either true or false so we

can return that directly

but this isn't sufficient if it were we

could trick the verify function by only

sorting the first two elements in the

list

so to this return statement we're going

to use an and operator to add on one

more condition for this condition we're

going to make a recursive function call

back to verify

sorted

and for the argument we're going to pass

in the list

going from the second element all the

way

to the end let's visualize how this

would work

we'll use a five element list as an

example so we'll call verify sorted and

pass in the entire list

this list is not one or zero elements

long so we skip that first if statement

there's only one line of code left in

the function and first we check that the

element at index 0 is less than the

element at index 1. if this is false the

function returns immediately with a

false value

an and operator requires both conditions

to be true for the entire line of code

to return true

since the first condition evaluates to

false we don't need to bother evaluating

the second the second condition is a

recursive call with a sub-list

containing elements from the original

list starting at position 1 and going to

the end

so on the second call again we can skip

that first if statement and proceed to

check whether the value at element 0 is

less than the value at element 1.

remember that because this list is a

sub-list of the original starting at the

element that was the second element in

the original list

by comparing the elements at position 0

and 1 in the sub list we're effectively

comparing the elements at position 1 and

2 in the original list with each

recursive call as we create new sub

lists that start at index position 1

we're able to check the entire list

without having to specify any checks

other than the first two elements

since this is a recursive function it

means we need a stopping condition and

we have it already it's that first if

condition

as we keep making sub lists once we

reach a single element list that element

is already sorted by definition so we

can return true since this recursive

function call is part of an and

condition

it means that every single recursive

call has to return true all the way back

to the beginning for our top level

function to return true and for the

function to say yes this is sorted

now we could have easily done this using

an iterative solution and a for loop but

this way you get another example of

recursion to work through and understand

so let's use this function

at the bottom we'll say print

verify sorted and first we'll pass in a

list

oops we got rid of that didn't we

okay let me write it out again so a list

equal

and i think i have those original

numbers here somewhere so we'll say 54

26 93

okay and then we assigned to l the

result of calling merge

sort

on a list

okay so now here we're going to use the

verify sorted function

and we'll check first that a list is

sorted that should return false and then

we'll check the same call on we'll pass

an l and this should return true

okay so now at the bottom here in the

console

we'll call python merge sort dot pi and

there we go it returned false for a list

meaning it's not sorted but l is sorted

cool so our merge sort function works in

the next video let's talk about the cost

of this algorithm

if we go back to the top level the merge

sort function what is the run time of

this function look like and what about

space complexity how does memory usage

grow as the algorithm runs

to answer those questions let's look at

the individual steps starting with the

split function in the split function all

we're doing is finding the midpoint of

the list and splitting the list at the

midpoint

this seems like a constant time

operation but remember that the split

function isn't called once it's called

as many times as we need it to to go

from the initial list down to a single

element list

now this is a pattern we've seen a

couple times now and we know that

overall this runs in logarithmic time so

let's add that as a comment so here i'll

say

takes

overall

big o of log

n time now there's a caveat here but

we'll come back to that

so next up is the merge step in the

merge step we've broken the original

list down into single element lists and

now we need to make comparison

operations and merge them back in the

reverse order

for a list of size n we will always need

to make an n number of merge operations

to get back from single element lists to

a merge list

this makes our overall runtime big o of

n times log n because that's an n number

of merge steps multiplied by log n

number of splits of the original list

so to our merge step here let's add a

comment we'll say it runs

in overall

oops there we go runs an overall linear

time

right it takes an n number of steps

number of merge steps but now that we

have these two so linear here and

logarithmic here we can multiply these

and say that the merge sort function the

top level function we can conclude that

the runtime of the overall sorting

process is big o of n times log n

now what about that caveat i mentioned

earlier

so if we go back to our split function

here

right here there we go

let's take a look at the way we're

actually splitting the list so we're

using python's list slicing operation

here

and passing in two indexes where the

split occurs

now if you go and poke around the python

documentation which i've done it says

that a slicing operation is not a

constant time operation and in fact has

a runtime of big o of k where k

represents the slice size

this means that in reality our

implementation of split this

implementation of split does not run in

logarithmic time but k times logarithmic

time because there is a slice operation

for each split

this means that our implementation is

much more expensive so

overall

that makes our overall top level merge

sort function not n times log n but k n

times log n which is much more expensive

now let's get rid of all that

to fix this we would need to remove this

slicing operation now we can do that by

using a technique we learned in a

previous course

in the introduction to algorithms course

we looked at two versions of binary

search in python a recursive and an

iterative version

in the recursive one we use list slicing

with every recursion call but we achieve

the same end result using an iterative

approach without using list slicing

over there we declared two variables to

keep track of the starting and ending

positions in the list

we could rewrite merge sort to do the

same but i'll leave that as an exercise

for you if you want some hints if you

want any direction i've included a link

in the notes with an implementation so

that is time complexity now just so we

know before moving on for python here

our

overall run time is not what i've listed

here but this is what the actual run

time of the merge sort algorithm looks

like so the merge step runs in linear

time and the split step takes

logarithmic time for an overall n times

log n and that is how merge sort

actually works

okay so what about space complexity

the merge sort algorithm takes linear

space and this is weird to think about

it first but as always a visualization

helps

so if we start at the top again with our

full list and carry out the split method

until we have single element lists each

of these new lists take up a certain

amount of space

so the second level here we have two

lists where each take up an n by two

amount of space

now this makes it seem that the sum of

all this space is the additional space

needed for merge sort but that's not

actually the case in reality there are

two factors that make a difference

first not every single one of these sub

lists are created simultaneously

at step two we create two n by two size

sub lists

when we move to the next step however we

don't hold on to the n by two sub lists

and then create four n by four size sub

lists for the next split

instead after the four n by four size

sub lists are created the n by two ones

are deleted from memory there's no

reason to hold on to them any longer now

the second point is that our code

doesn't execute every path

simultaneously

think of it this way when we pass our

list to the top level merge sort

function

our implementation calls split

which returns a left half and a right

half

the next line of code then calls merge

sort on the left half again

this runs the function the merge sort

function again with a new list

in that second run of the function split

is called again we get a second left and

right half and then again like before we

call merge sort on this left half as

well what this means is that the code

walks down the left path all the way

down until that initial left half is

sorted and merged back into one array

then it's going to walk all the way down

the right path and sort that until we're

back to that first split with two n by

two sized sublists

essentially we don't run all these paths

of code at once so the algorithm doesn't

need additional space for every sub-list

in fact it is the very last step that

matters

in the last step the two sub-lists are

merged back into the new sorted list and

returned

that sorted list has an equal number of

items as the original unsorted list

and since this is a new list it means

that at most the additional space the

algorithm will require at a given time

is n

yes at different points in the algorithm

we require log n amount of space but log

n is smaller than n and so we consider

the space complexity of merge sort to be

linear because that is the overall

factor

okay that was a lot so let's stop here

don't worry if you've got questions

about merge sort because we're not done

yet

over the next few videos let's wrap up

this course by implementing merge sort

on a linked list

[Music]

over the last few videos we implemented

the merge sort algorithm on the array or

list type in python merge sort is

probably the most complicated algorithm

we've written so far but in doing so we

learned about an important concept

divide and conquer

we also concluded the last video by

figuring out the run time of merge sort

based on our implementation

over the next few videos we're going to

implement merge sort again this time on

the linked list type

in doing so we're going to get a chance

to see how the implementation differs

based on the data structure while still

keeping the fundamentals of the

algorithm the same and we'll also see

how the run time may be affected by the

kinds of operations we need to implement

let's create a new file to put our

second implementation of merge sort in

so file over here new file

and it's going to have a rather long

name we'll call this linked

list

merge sort with underscores everywhere

dot pi

we're going to need the linked list

class that we created earlier so we'll

start at the top by importing the linked

list class from the linkedlist.pi file

the way we do that is we'll say from

linked

list

import linked list

right so that imports the class

uh let's test if this works really quick

we'll just do something like l equal

linked

list

l.add

ten

or one doesn't matter print l

okay and if i hit save

and then down here we'll say python

linked list

merge sword dot pi

okay it works so this is how we get some

of the code how we reuse the code that

we've written in other files into this

current file

and get rid of this now

okay like we did with the first

implementation of merge sort we're going

to split the code up across three

functions

the main function merge sort

a split function and a merge function

now if you were to look up a merge sort

implementation in python both for a

regular list an array or a linked list

you would find much more concise

versions out there but they're kind of

hard to explain so splitting it up into

three will sort of help it you know be

easier to understand so we'll call this

merge sort at the top level and this

time it's going to take a linked list

let's add a dog string to document the

function

so say that this function sorts a linked

list in ascending order

and like before we'll add the steps in

here so we'll say you first recursively

divide the linked list into sub lists

containing

a single

node

then

we repeatedly

merge these sub-lists

to produce sorted sub-lists

until one remains

and then finally this function returns a

sorted

linked list

the implementation of this top level

merge function is nearly identical to

the array or list version we wrote

earlier so first we'll provide a

stopping condition or two if the size of

the list is one or it's an empty list

we'll return the linked list since it's

naively sorted so if linked

list dot size remember that function we

run equal one

then we'll return

linked

list

else if

linked list dot head

is none meaning it's an empty list then

we'll return linked list as well okay

next let's split the linked list into a

left and right half

conceptually this is no different but in

practice we need to actually traverse

the list we'll implement a helper method

to make this easier

but we'll say left half

comma right half

equal split

linked list

now once we have two sub lists like

before we can call merge sort the top

level function on each

so left equal merge sort

left half

and right equal merge sort

on the right half

finally we'll merge these two top-level

sub-lists and return it so merge left

and right

okay nothing new here but in the next

video let's implement the split logic

the next step in the merge sort

algorithm is the divide step or rather

an implementation of the split function

so down here

we'll call this split like before and

this is going to take a linked

list

documenting things is good and we've

been doing it so far so let's add a

docstring

divide the unsorted list at midpoint

into sub-lists

now of course when i say sub-lists here

i mean sub-linked lists but that's a

long word to say

now here's where things start to deviate

from the previous version

with the list type we could rely on the

fact that finding the midpoint using an

index and list slicing to split into two

lists would work even if an empty list

was passed in

since we have no automatic behavior like

that we need to account for this when

using a linked list so our first

condition is if the linked list is none

or if it's empty that is if head is

equal to none

so we'll say if linked list

equal none

or you can write is there it doesn't

matter or linked list dot head is none

well linked list can be none for example

if we call split on a linked list

containing a single node a split on such

a list would mean left would contain the

single node while right would be none

now in either case we're going to assign

the entire list to the left half and

assign none to the right so we'll say

left half

equal linked list

and then right half

equal none

you could also assign the single element

list or none to left and then create a

new empty linked list assigned to the

right half but that's unnecessary work

so now that we've done this we can

return

left half

and right half

so that's our first condition let's add

an else clause to account for non-empty

linked lists first we'll calculate the

size of the list now this is easy

because we've done the work already and

we can just call the size method that

we've defined we'll say size equal

linked underscore list dot size

using this size we can determine the

midpoint so mid equal size and here

we'll use that floor division operator

to divide it by two once we have the

midpoint we need to get the node at that

midpoint

now make sure you hit command s to save

here and we're going to navigate back to

linkedlist.hi

in here we're going to add a convenience

method at the very bottom right before

the wrapper function right here

and this convenience method is going to

return a node at a given index so i'll

call this node

at

index and it's going to take an index

value

this way instead of having to traverse

the list inside of our split function we

can simply call node at index and pass

it the midpoint index we calculated to

give us the node right there so we can

perform the split

okay so this method accepts as an

argument the index we want to get the

node for if this index is zero then

we'll return the head of the list so if

index double equals zero return

self.head

the rest of the implementation involves

traversing the linked list and counting

up to the index as we visit each node

the rest of the implementation involves

traversing the linked list and counting

up to the index as we visit each node so

i'll add an else clause here

and we'll start at the head so we'll say

current equal self.head

let's also declare a variable called

position

to indicate where we are in the list

we can use a while loop to walk down the

list our condition here is as long as

the position is less than the index

value

so i'll say while position

is less than index

inside the loop we'll assign the next

node to current and increment the value

of position by one

so current equal current dot next node

position

plus equal one

once the position value equals the index

value current refers to the node we're

looking for and

we can return it we'll say return

current

let's get rid of all this empty space

there we go now back in linked list

merge sort

dot pi

we can use this method to get at the

node after we've calculated the midpoint

to get the node at the midpoint of the

list

so we'll say mid node

equal

linked

list

dot node at index

and here i'm going to do something

slightly confusing i'm going to do mid

minus 1. remember we're subtracting 1

here

because we used size

to calculate the midpoint and like the

len function size will always return a

value greater than the maximum index

value

so think of a linked list with two nodes

size would return two

the midpoint though and the way we're

calculating the index we always start at

zero which means size is going to be one

greater than that so we're going to

deduct one from it to get the value we

want but we're using the floor division

operator so it's going to round that

down even more no big deal with the node

at the midpoint now that we have this

midnote we can actually split the list

so first we're going to assign the

entire linked list to a variable named

left half so left half

equal linked list

this seems counterintuitive but make

sense in a second

for the right half we're going to assign

a new instance of linked list so right

half equal

linked list

this newly created list is empty but we

can fix that by assigning the node that

comes after the midpoint so after the

midpoint of the original linked list we

can assign the node that comes after

that midpoint node as the head of this

newly created

right linked list

so here we'll say right half

dot head

equal mid node dot

node

once we do that we can assign none to

the next node property on mid node to

effectively sever that connection and

make what was the mid node now the tail

node of the left linked list so i'll say

mid node

dot next node

equal none

if that's confusing here's a quick

visualization of what just happened

we start off with a single linked list

and find the midpoint the node that

comes after the node at midpoint is

assigned to the head of a newly created

linked list and the connection between

the midpoint node and the one after is

removed

we now have two distinct linked lists

split at the midpoint

and with that we can return the two sub

lists so we'll return left half

and right half

in the next video let's tackle our merge

function in the last video we defined an

implementation for the version of the

split function that works on linked

lists it contained a tiny bit more code

than the array or list version that was

expected the merge function is no

different because like with the split

function after we carry out a comparison

operation we also need to swap

references to corresponding nodes all

right let's add our merge function over

here at the bottom below

the split functions we'll call this

merge and it's going to take a left

and right

now because this can get complicated

we're going to document this function

extensively and as always we're going to

start with a doc string

so we'll say that this function merges

two linked lists

sorting

by data in the nodes

and it returns a new

merged list

remember that in the merge step we're

going to compare values across two

linked lists and then return a new

linked list with nodes where the data is

sorted

so first we need to create that new

linked list let's add a comment in here

we'll say create

a new linked list

that contains nodes from

let's add a new line merging left and

right

okay and then create the list so merged

equal

new linked list

to this list we're going to do something

unusual we're going to add a fake head

this is so that when adding sorted nodes

we can reduce the amount of code we have

to write by not worrying about whether

we're at the head of the list once we're

done we can assign the first sorted node

as the head and discard the fake head

now this might not make sense at first

but not having to worry about whether

the new linked list already contains a

head or not makes the code simpler we'll

add another comment

and a fake hand that is discarded

later

we'll say merged dot add zero

like we've been doing so far we'll

declare a variable named current to

point to the head of the list

set current to the head of the linked

list and then current equal

merged dot head

next we'll get a reference to the head

on each of the linked lists left and

right

so we'll say obtain

head nodes

for left and right linked lists

and here's call this left head

equal

left dot head

and right hand equal right dot head

okay so with that setup out of the way

let's start iterating over both lists

so another comment

iterate over left and right

as long

or we'll say until

the

until we reach the tail node

of either

and we'll do that by saying while

left head

or right head

so this is a pattern that we've been

following all along we're going to

iterate until we hit the tail nodes of

both lists and we'll move this pointer

forward every time so that we traverse

the list with every iteration if you

remember the logic behind this from the

earlier version once we hit the tail

note of one list if there are nodes left

over in the other linked list we don't

need to carry out a comparison operation

anymore and we can simply add those

nodes to the merged list

the first scenario we'll consider is if

the head of the left linked list is none

this means we're already past the tail

of left and we can add all the nodes

from the right linked list to the final

merge list so here i'll say if

the head node of left is none

we're past the tail

add the node

from the right from right to merged

linked

list so here we'll say if

left head

is none

current dot next node

remember current points to the head of

the merge list that we're going to

return so here we're setting its next

node reference to the head node on the

right link list so we'll say right head

then when we do that we'll move the

right head forward to the next node so

let's say right

head

equal right hand

dot next node

this terminates the loop on the next

iteration let's look at a visualization

to understand why

let's say we start off with a linked

list containing four nodes so we keep

calling split on it until we have lists

with just a single head single node

linked lists essentially

so let's focus on these two down here

that we'll call left and right

we haven't implemented the logic for

this part yet but here we would compare

the data values and see which one is

less than the other

so we'll assume that left's head is

lesser than right's head so we'll set

this as the next node in the final merge

list

left is now an empty length list so left

dot head equals none on the next pass

through the loop left head is none which

is the situation we just implemented

here we can go ahead and now assign

right head as the next note in the merge

link list we know that right is also a

singly linked list

here's the crucial bit when we move the

pointer forward by calling next node on

the right node there is no node and the

right link the right linked list is also

empty now which means that both left

head and right head are none and either

one of these would cause our loop

condition to terminate

so what we've done here is encoded a

stopping condition for the loop so we

need to document this because it can get

fuzzy so right above that line of code

i'll say call next

on right

to

set loop condition

to false

okay there's another way we can arrive

at this stopping condition and that's in

the opposite direction if we start with

the right head being none so here we'll

say i'm going to add another comment

if oops not there there

if

the head node of right

is none

we're past the tail

then we'll say

add the tail node from left

to merged linked list

and then we'll add that condition we'll

say else if right head

is none

now remember we can enter these even if

left head is none we can still go into

this condition we can still enter this

if statement and execute this logic

because the while loop the loop

condition here is an or statement so

even if left head is false if this

returns true because there's a value

there there's a node there the loop will

keep going

okay now in this case we want to set the

head of the left linked list as the next

node on the merge list so this is simply

the opposite of what we did over here

we'll set current dot next node

equal to left head

and then we'll move so after doing that

we can move the variable pointing to

left head forwards which as we saw

earlier is past the tail node and then

results in the loop terminating so we'll

say left hand

equal

left

head dot next node and we'll add that

comment here as well so we'll say call

next on left to set loop condition

to false

because here right head is none and now

we make left head none these two

conditions we looked at where either the

left head or right head

were at the tail nodes of our respective

lists those are conditions that we run

into when we've reached the bottom of

our split where we have single element

linked lists or empty linked lists let's

account for our final condition where

we're evaluating a node that is neither

the head nor the tail of the list

and this condition we need to reach into

the nodes and actually compare the data

values to one another before we can

decide which node to add first to the

merged list

so here this is an else because we've

arrived at our third condition third and

final

and here we'll say not at either tail

node

obtain

no data to perform

comparison operations so let's get each

of those data values out of the

respective nodes so that we can compare

it so we'll say left

data equal left head dot data

and write data

equal right head righthead.data

okay what do we do next well we compare

but first let's add a comment so we'll

say if data

on left

is less than right

set current to left node and then

move

actually we'll add this in a second so

here we'll say if left data

is less than write data

then current dot next node

equal left head

and then

we'll add a comment and we'll say move

left head to next node

on that list so we'll say left head

equal left head

dot next node

just as our comment says we'll check if

the left data is less than the right

data if it is since we want a list in

ascending order we'll assign the left

node to be the next node in the merged

list we'll also move the left head

forward to traverse down to the next

node in that particular list now if left

is larger than right then we want to do

the opposite so we'll go back to spaces

another comment

if data on left is greater than right

set current

to

right node

okay so else

here we assign the right head to be the

next node in the merge list so

current.nextnode

equal right

head

and then comment

move right head to next node

so right

head equal

right head

dot next

node okay after doing that we move the

right head pointer to reference the next

node in the right list

and finally at the end of each iteration

of the while loop so not here but two

spaces back right make sure we're

indented at the same level as the while

so we got to go yep or not the same

level as the wild but the same outer

scope

and then there we're going to say

move current to next node

so current equal current dot next node

okay don't worry if this is confusing as

always we'll look at a visualization in

just a bit so we'll wrap up this

function by discarding that fake head we

set earlier setting the correct node as

head and returning the linked list so

we'll add a comment

discard fake head

and set

first

merged node as head so here we'll say

head equal

merged dot head dot next

node and then merged dot head equal head

and finally return

merged

okay we wrote a lot of code here a lot

of it was comments but still it's a

bunch let's take a quick break in the

next video we'll test this out evaluate

our results and determine the runtime of

our algorithm

okay first things first let's test out

our code now we'll keep it simple

because writing a robust verify function

would actually take up this entire video

instead i'll leave that up to you to try

as homework

okay so

at the very end

let's create a new linked list

let's add a few notes to this so l add

i'm going to copy paste this

so it makes it easier for me

not to have to retype a bunch so i'll

add 10

uh then set 2

44

15

and something like 200. okay then we'll

go ahead and print l so that we can

inspect this list

next

let's create a declare variable here so

we'll call this sorted linked list

and to this we're going to assign the

result of calling merge sort on l

and then we'll print this

so sorted

linked

list

okay since we've taken care of all the

logic we know that this gets added in as

nodes and then

let's see what this looks like all right

so hit save

and then bring up the console we're

going to type out python

linked

list underscore merge sort dot pi and

then enter okay so we see that linked

list we first created remember that what

we add first right that eventually

becomes a tail or right yeah so 10 is

the tail 200 is the last one so 200 is

the head because i'm calling add it

simply adds each one to the head of the

list so here we have 10 to 44 15 and 200

in the order we added and then the

sorted linked list sorts it out so it's

2 10 15 44 and 200. look at that a

sorted linked list

okay so let's visualize this from the

top

we have a linked list containing five

nodes with integers 10 2 4 15 and 200 as

data respectively our merge sort

function calls split on this list the

split function calls size on the list

and gets back 5 which makes our midpoint

2.

using this midpoint we can split the

list using the node at index method

remember that when doing this we deduct

1 from the value of mid so we're going

to split here using an index value of 1.

effectively this is the same since we're

starting with an index value of 0 1

means we split after node 2. we assign

the entire list to left half

then create a new list and assign that

to right half

we can assign node 3 at index value 2 as

the head of the right list and remove

the references between node two and node

three so far so good right

okay so now we're back in the merge sort

function after having called split and

we have two linked lists

let's focus on just the left half

because if you go back and look at our

code we're going to call merge sort on

the left linked list again

this means the next thing we'll do is

run through that split process since

this is a linked list containing two

nodes this means that split is going to

return a new left and right list each

with one node again we're back in the

merge sort function which means that we

call merge sort on this left list again

since this is a single node linked list

on calling merge sort on it we

immediately return before we split since

we hit that stopping condition so we go

to the next line of code which is

calling merge sort on the right list as

well but again we'll get back

immediately because we hit that stopping

condition now that we have a left and

right that we get back from calling

merge sort we can call merge on them

inside the merge function we start by

creating a new linked list and attaching

a fake head

then we evaluate whether either the left

or the right head is none

since neither condition is true we go to

the final step where we evaluate the

data in each node

in this case the data in the right node

is less than the left node so we assign

the right node as the next node in the

merge link list and move the right head

pointer forward

in the merge link list we move our

current pointer forward to this new node

we've added and that completes one

iteration of the loop

on the next iteration righthead now

points to none since that was a single

node list and we can assign the rest of

the left linked list which is

effectively the single node over to the

merge link list here we discard the fake

head move the next node up to be the

correct head and return the newly merged

sorted linked list remember that at this

point because right head and left head

pointed to none are while loop

terminated

so in this way we recursively split and

repeatedly merge sub-lists until we're

back with one sorted linked list

the merge sort algorithm is a powerful

sorting algorithm but ultimately it

doesn't really do anything complicated

it just breaks the problem down until

it's really simple to solve

remember the technique here which we've

talked about before is called divide and

conquer so i like to think of merge sort

in this way there's a teacher at the

front of the room and she has a bunch of

books that she needs to sort into

alphabetical order instead of doing all

that work herself she splits that pile

into two and hands it to two students at

the front

each of those students split it into two

more and hand it to the four students

seated behind them as each student does

this eventually a bunch of single

students has two books to compare and

they can sort it very easily and hand it

back to the student who gave it to them

in front of them who repeats the process

backwards so ultimately it's really

simple work is just efficiently

delegated

now back to our implementation here

let's talk about runtime so far other

than the node swapping we had to do it

seems like most of our implementation is

the same right in fact it is including

the problems that we ran into in the

list version as well so in the first

implementation of merge sort we thought

we had an algorithm that ran in big o of

n log n but turns out we didn't why well

the python list slicing operation if you

remember actually takes up some amount

of time amounting to big o of k

a true implementation of merge sort runs

in quasi-linear or log linear time that

is n times log n so we almost got there

but we didn't now in our implementation

of merge sort on a linked list we

introduce the same problem so if we go

back up to

the merge or rather the split function

this is where it happens now swapping

node references that's a constant time

operation no big deal comparing values

also constant time

the bottleneck here like list slicing is

in splitting a late list at the midpoint

if we go back to our implementation you

can see here that we use the node at

index method which finds the node we

want by traversing the list

this means that every split operation

incurs a big o of k cost where k here is

the midpoint of the list effectively n

by 2 because we have to walk down the

list counting up the index until we get

to that node

given that overall splits take

logarithmic time our split function just

like the one we wrote earlier

incurs a cost of

big o of

k log n so here we'll say it takes

big o of k times log n

now the merge function also like the one

we wrote earlier takes linear time so

that one is good that one runs in the

expected amount of time so here we'll

say runs in linear

time

and that would bring our overall run

time so up at the merge sort function we

can say this runs in

big o of k n times log

n

it's okay though this is a good start

and one day when we talk about constant

factors and look at ways we can reduce

the cost of these operations using

different strategies we can come back

and re-evaluate our code to improve our

implementation for now as long as you

understand how merge sort works

conceptually what the run time and space

complexities look like and where the

bottlenecks are in your code that's

plenty of stuff

if you're interested in learning more

about how we would solve this problem

check out the notes in the teachers

video in the next video let's wrap this

course up

and with that let's wrap up this course

in the prerequisite to this course

introduction to algorithms we learned

about basic algorithms along with some

concepts like recursion and big o that

set the foundation for learning about

implementing and evaluating algorithms

in this course we learned what a data

structure is and how data structures go

hand in hand with algorithms

we started off by exploring a data

structure that many of us use in our

day-to-day programming arrays or lists

as they are known in python

we take a peek under the hood at how

arrays are created and stored and

examine some of the common operations

carried out on arrays

these are operations that we write and

execute all the time but here we took a

step back and evaluated the run times of

these operations and how they affect the

performance of our code

after that we jumped into an entirely

new world where we wrote our own data

structure a singly linked list

admittedly linked lists aren't used much

in day-to-day problem solving but it is

a good data structure to start off with

because it is fairly straightforward to

understand and not that much different

from an array

we carried out the same exercise as we

did on arrays in that we looked at

common data operations but since this

was a type we defined on our own we

implemented these operations ourselves

and got to examine with a fine-tooth

comb how our code and the structure of

the type affected the runtime of these

operations

the next topic we tackled was

essentially worlds colliding we

implemented a sorting algorithm to sort

two different data structures

here we got to see how all of the

concepts we've learned so far

algorithmic thinking time and space

complexity and data structures all come

together to tackle the problem of

sorting data

this kind of exercise is one we're going

to focus on moving forward as we try to

solve more real-world programming

problems using different data structures

and algorithms

if you've stuck with this content so far

keep up the great work this can be a

complex topic but a really interesting

one and if you take your time with it

you will get a deeper understanding of

programming and problem solving as

always check the notes for more

resources and happy coding

[Music]

you may have heard that algorithms and

computer science are boring or

frustrating they certainly can be hard

to figure out especially the way some

textbooks explain them but once you

understand what's going on algorithms

can seem fascinating clever or even

magical

to help further your understanding of

algorithms this course is going to look

at two categories sorting algorithms and

searching algorithms you could argue

that these are the easiest kinds of

algorithms to learn but in learning how

these algorithms are designed we'll

cover useful concepts like recursion and

divide and conquer that are used in many

other sorts of algorithms and can even

be used to create brand new ones

by the way all the code samples i'm

going to show in the videos will be in

python because it's a popular language

that's relatively easy to read but you

don't need to know python to benefit

from this course you can see the

teacher's notes for each video for info

on implementing these algorithms in your

own favorite language

our goal with this course is to give you

an overview of how sorting and searching

algorithms work but many algorithms have

details that can be handled in different

ways some of these details may distract

from the big picture so we've put them

in the teachers notes instead you don't

need to worry about these when

completing the course for the first time

but if you're going back and referring

to it later be sure to check the

teacher's notes for additional info

suppose we have a list of names it's a

pretty big list a hundred thousand names

long this list could be part of an

address book or social media app

and we need to find the locations of

individual names within the list

possibly to look up additional data

that's connected to the name

let's assume there's no existing

function in our programming language to

do this or that the existing function

doesn't suit our purpose in some way

for an unsorted list our only option may

be to use linear search also known as

sequential search

linear search is covered in more detail

elsewhere on our site check the

teacher's notes for a link if you want

more details

you start at the first element you

compare it to the value you're searching

for if it's a match you return it if not

you go to the next element

you compare that to your target if it's

a match you return it if not you go to

the next element and so on through the

whole list

the problem with this is that you have

to search the entire list every single

time we're not doing anything to narrow

down the search each time we have to

search all of it

if you're searching a big list or

searching it repeatedly this amount of

time can slow your whole lap down to the

point that people may not want to use it

anymore that's why it's much more common

to use a different algorithm for

searching lists binary search

binary search is also covered in more

detail elsewhere on our site check the

teacher's notes for a link

binary search does narrow the search

down for us specifically it lets us get

rid of half the remaining items we need

to search through each time

it does this by requiring that the list

of values be sorted

it looks at the value in the middle of

the list

if the value it finds is greater than

the target value it ignores all values

after the value it's looking at

if the value it finds is less than the

target value it ignores all values

before the value it's looking at

then it takes the set of values that

remain and looks at the value in the

middle of that list again if the value

it finds is greater than the target

value it ignores all values after the

value it's looking at if the value it

finds is less than the target value it

ignores all values before the value it's

looking at

but as we mentioned binary search

requires the list of values you're

searching through to be sorted

if the lists weren't sorted you would

have no idea which half of the values to

ignore because either half could contain

the value you're looking for you'd have

no choice but to use linear search

so before we can use binary search on a

list we need to be able to sort that

list we'll look at how to do that next

our end goal is to sort a list of names

but comparing numbers is a little easier

than comparing strings so we're going to

start by sorting a list of numbers

i'll show you how to modify our examples

to sort strings at the end of the course

to help make clear the importance of

choosing a good sorting algorithm we're

going to start with a bad one it's

called bogosort basically bogosort just

randomizes the order of the list

repeatedly until it's sorted

here's a python code file where we're

going to implement bogosort

it's not important to understand this

code here at the top although we'll have

info on it in the teachers notes if you

really want it all you need to know is

that it takes the name of a file that we

pass on the command line loads it and

returns a python list which is just like

an array in other languages containing

all the numbers that it read from the

file

let me have the program print out the

list of numbers it loads so you can see

it we'll call the print method and we'll

pass it the list of numbers

save that let's run it real quick

with python bogosort.pi

oh whoops and we need to

provide it

the name of the file here on the command

line that we're going to load so it's in

the numbers directory a slash separates

the directory name from the file name

five dot text

and there's our list of numbers that was

loaded from the file

okay let me delete that print statement

and then we'll move on

bogo sort just randomly rearranges the

list of values over and over so the

first thing we're going to need is a

function to detect when the list is

sorted

we'll write an is sorted function that

takes a list of values as a parameter

it'll return true if the list passed in

is sorted or false if it isn't

we'll loop through the numeric index of

each value in the list from 0 to 1 less

than the length of the list like many

languages python list indexes begin at 0

so a list with a length of 5 has indexes

going from 0 through 4.

if the list is sorted then every value

in it will be less than the one that

comes after it so we test to see whether

the current item is greater than the one

that follows it

if it is it means the whole list is not

sorted so we can return false

if we get down here it means the loop

completed without finding any unsorted

values python uses white space to mark

code blocks so unindenting the code like

this marks the end of the loop

since all the values are sorted we can

return true

now we need to write the function that

will actually do the so-called sorting

the bogosort function will also take the

list of values it's working with as a

parameter

we'll call our is sorted function to

test whether the list is sorted we'll

keep looping until is sorted returns

true

python has a ready-made function that

randomizes the order of elements in the

list

since the list isn't sorted we'll call

that function here

and since this is inside the loop it'll

be randomized over and over until our is

sorted function returns true

if the loop exits it means is sorted

returned true and the list is sorted so

we can now return the sorted list

finally we need to call our bogosort

function pass it the list we loaded from

the file and print the sorted list it

returns

okay let's save this and try running it

we do so with python the name of the

script bogosort.pi

and the name of the file we're going to

run it on

numbers directory5.txt

it looks like it's sorting our list

successfully

but how efficient is this let's add some

code to track the number of times it

attempts to sort the list

up here at the top of the bogus sort

function we'll add a variable to track

the number of attempts it's made we'll

name it attempts and we'll set its

initial value to zero since we haven't

made any attempts yet

with each pass through the loop we'll

print the current number of attempts

and then here at the end of the loop

after attempting to shuffle the values

we'll add one to the count of attempts

let's save this and let's try running it

again a couple times

in the console i can just press the up

arrow to bring up the previous command

and re-run it

so it looks like this first run to sort

this five element list took 363 attempts

let's try it again

this time it only took 91 attempts

we're simply randomizing the list with

each attempt so each

run of the program takes a random number

of attempts

now let's try this same program with a

larger number of items

python bogo sort

numbers

i have a list of eight items set up here

in this other file

this time it takes 11 000 attempts

only 487 this time

and this time thirteen thousand you can

see that the trend is increasing

steadily

the problem with bogosort is that it

doesn't make any progress toward a

solution with each pass

it could generate a list where just one

value is out of order but then on the

next attempt it could generate a list

where all the elements are out of order

again

stumbling on a solution is literally a

matter of luck and for lists with more

than a few items it might never happen

up next we'll look at selection sort

it's a sorting algorithm that's still

slow but it's better than bogo's sort

previously we showed you bogo sort a

terrible sorting algorithm that

basically randomizes the order of a list

and then checks to see if it happens to

be sorted

the problem with bogo's sort is that it

doesn't get any closer to a solution

with each operation and so with lists

that have more than a few items it'll

probably never finish sorting them

now we're going to look at an algorithm

named selection sort it's still slow but

at least each pass through the list

brings it a little closer to completion

our implementation of selection sort is

going to use two arrays an unsorted

array and a sorted one some versions

move values around within just one array

but we're using two arrays to keep the

code simpler the sorted list starts out

empty but we'll be moving values from

the unsorted list to the sorted list one

at a time

with each pass we'll look through each

of the values in the unsorted array find

the smallest one and move that to the

end of the sorted array

we'll start with the first value in the

unsorted array and say that's the

minimum or smallest value we've seen so

far

then we'll look at the next value and

see if that's smaller than the current

minimum if it is we'll mark that as the

new minimum

then we'll move to the next value and

compare that to the minimum again if

it's smaller that becomes the new

minimum we continue that way until we

reach the end of the list

at that point we know whatever value we

have marked as the minimum is the

smallest value in the whole list

now here's the part that makes selection

sort better than bogo sort we then move

that minimum value from the unsorted

list to the end of the sorted list

the minimum value isn't part of the

unsorted list anymore so we don't have

to waste time looking at it anymore all

our remaining comparisons will be on the

remaining values in the unsorted list

then we start the process over at this

point our list consists of the numbers 8

5 4 and 7. our first minimum is 8.

we start by comparing the minimum to

five five is smaller than eight so five

becomes the new minimum then we compare

five to four and four becomes the new

minimum four is not smaller than seven

though so four remains the minimum four

gets moved to the end of the sorted

array becoming its second element

the process repeats again eight is the

first minimum but five is smaller so

that becomes the minimum seven is larger

so five stays is the minimum and five is

what gets moved over to the sort of

array and so on until there are no more

items left in the unsorted array and all

we have left is the sorted array

so that's how selection sort works in

general now let's do an actual

implementation of it

this code here at the top is the same as

we saw in the bogo sword example it just

loads a python list of numbers from a

file

let's implement the function that will

do our selection sort we're going to

pass in our python list containing all

the unsorted numbers we'll create an

empty list that will hold all our sorted

values

we'll loop once for each value in the

list

we call a function named index submin

which we're going to write in just a

minute that finds the minimum value in

the unsorted list and returns its index

then we call the pop method on the list

and pass it the index of the minimum

value pop will remove that item from the

list and return it we then add that

value to the end of the sorted list

going up a level of indentation signals

to python that we're ending the loop

after the loop finishes we return the

sorted list

now we need to write the function that

picks out the minimum value we pass in

the list we're going to search

we mark the first value in the list as

the minimum it may or may not be the

actual minimum but it's the smallest

we've seen on this pass through the list

it's also the only value we've seen on

this pass through the list so far

now we loop through the remaining values

in the list after the first

we test whether the value we're

currently looking at is less than the

previously recorded

minimum if it is then we set the current

index as the new index of the minimum

value

after we've looped through all the

values we return the index of the

smallest value we found

lastly we need to actually run our

selection sort method and print the

sorted list it returns

let's save this and now let's try

running it we run the python command and

pass it the name of our script

selectionsort.pi

in the numbers directory i've saved

several data files filled with random

numbers one on each line five dot text

has five lines eight dot text has eight

lines and to help us really measure the

speed of our algorithms ten thousand dot

text has ten thousand lines i've even

created a file with a million numbers

our script takes the path of a file to

load as an argument so i'll give it the

path of our file with five numbers

numbers slash five dot text

the script runs reads the numbers in the

file into a list calls our selection

sort method with that list and then

prints the sorted list

let me add a couple print statements

within the selection sort function so

you can watch the sort happening

don't worry about figuring out the

python formatting string that i use it's

just there to keep the two lists neatly

aligned

i'll add the first print statement

before the loop runs at all

i'll have it print out the unsorted list

and the sorted list

i'll add an identical print statement

within the loop so we can watch values

moving from the unsorted list to the

sorted list

let's save this

and we'll try running the same command

again the output looks like this you can

see the unsorted list on the left and

the sorted list on the right

initially the sorted list is empty on

the first pass it selects the lowest

number 1 and moves it to the sorted list

then it moves the next lowest number

over four

this repeats until all the numbers have

been moved to the sorted list

i have another file with eight different

numbers in it let's try our program with

that

python selection sort dot pi numbers

8.text

you can see the same process at work

here notice that this file had some

duplicate values too that's okay though

because the index of min function only

updates the minimum index if the current

value is less than the previous minimum

if they're equal it just keeps the first

minimum value it found and waits to move

the duplicate value over until the next

pass through the list

so now we know that the selection sort

algorithm works but the data sets we've

been giving it sort are tiny in the real

world algorithms need to work with data

sets of tens of thousands or even

millions of items and do it fast i have

another file with ten thousand random

numbers in it

let's see if selection sort can handle

that

if i run this as it is now though it'll

print out a lot of debug info as it

sorts the list so first i'm going to go

into the program and remove the two

print statements in the selection sort

function

now let's run the program again on the

dot text file and see how long it takes

python selection sort dot pi

numbers

ten thousand dot text

one one thousand two one thousand three

one four one thousand five one thousand

six one thousand seven one thousand

eight one thousand nine one thousand ten

one thousand eleven thousand twelve

thousand thirteen thousand and it prints

out all ten thousand of those numbers

neatly sorted it took a little bit

though how long well counting the time

off vocally isn't very precise and other

programs running on the system can skew

the amount of time your program takes to

complete

let me show you a unix command that's

available here in workspaces which can

help you type time followed by a space

and then the command you want to run

so this command by itself will print the

contents of our 5.txt file cat as in

concatenate numbers 5.text

and this command will do the same thing

but it'll also keep track of how long it

takes the cat program to complete and

report the result time

cat

numbers five dot text

the real row in the results is the

actual amount of time for when the

program started running to when it

completed we can see it finished in a

fraction of a second but as we said

other programs running on the system can

take cpu resources in which case your

program will seem slower than it is so

we generally want to ignore the real

result

the user result is the amount of time

the cpu actually spent running the

program code so this is the total amount

of time the code inside the cat program

took to run

the sys result is the amount of time the

cpu spent running linux kernel calls

that your code made the linux kernel is

responsible for things like network

communications and reading files so

loading the 5.txt file is probably

included in this result

in evaluating code's performance we're

generally going to want to add together

the user and sys results but cad is a

very simple program let's try running

the time command on our code and see if

we get a more interesting result

time python

selection sort dot pi

numbers

ten thousand dot text

this takes much longer to complete

nearly 12 seconds according to the real

time measurement but as we said the real

result is often skewed so let's

disregard that

if we add the user and cis runtimes

together we get about 6 seconds

the time for the program to complete

will vary a little bit each time you run

it but if it's doing the same operations

it usually won't change more than a

fraction of a second if i run our

selection sort script on the same file

you can see it completes in roughly the

same time

now let's try it on another file with 1

million numbers time python selection

sort dot pi numbers

1 million dot text

how long does this one take i don't even

know while designing this course i tried

running this command and my workspace

connection timed out before it completed

so we'll just say that selection sort

takes a very very long time to sort a

million numbers

if we're going to sort a list that big

we're going to need a faster algorithm

we'll look into alternative sorting

algorithms shortly

the next two sorting algorithms we look

at will rely on recursion which is the

ability of a function to call itself so

before we move on we need to show you

how recursion works

recursive functions can be very tricky

to understand imagine a row of dominoes

stood on end where one domino falling

over causes the next domino to fall over

which causes the next domino to fall

over causing a chain reaction it's kind

of like that

let's suppose we need to write a

function that adds together all the

numbers in an array or in the case of

python a list

normally we'd probably use a loop for

this sort of operation

the function takes a list of the numbers

we want to add

the total starts at zero

we loop over every number contained in

the list and we add the current number

to the total

once we're done looping we return the

accumulated total

if we call this sum function with a list

of numbers it'll return the total when

we run this program it'll print out that

return value 19. let's try it real quick

python

recursion.pi oh whoops

mustn't forget to save my work here

and run it and we see the result 19.

to demonstrate how recursion works let's

revise the sum function to use recursion

instead note that recursion is not the

most efficient way to add a list of

numbers together but this is a good

problem to use to demonstrate recursion

because it's so simple one thing before

i show you the recursive version though

this example is going to use the python

slice syntax so i need to take a moment

to explain that for those not familiar

with it

a slice is a way to get a series of

values from a list

let's load up the python repel or read

evaluate print loop so i can demonstrate

we'll start by creating a list of

numbers to work with numbers equals

a list

with 0 1 2 3 and 4

containing those numbers

like arrays in most other languages

python list indexes start at 0 so

numbers

1

will actually get the second item from

the list

with slice notation i can actually get

several items back

it looks just like accessing an

individual index of a list

but then i type a colon

followed by the list index that i want

up to but not including

so numbers 1 colon 4 would get us the

second up to but not including the fifth

items from the list that is it'll get us

the second through the fourth items

now i know what you're thinking and

you're right that up to but not

including rule is a little

counterintuitive but you can just forget

all about it for now because we won't be

using a second index with any of our

python slice operations in this course

here's what we will be using when you

leave the second index off of a python

slice it gives you the items from the

first index up through the end of the

list wherever that is so numbers 1 colon

with no index following it will give us

items from the second index up through

the end of the list

numbers 2 colon will give us items from

the third index up to the end of the

list

you can also leave the first index off

to get everything from the beginning of

the list numbers

colon 3 will get us everything from the

beginning of the list up to but not

including the third index

it's also worth noting that if you take

a list with only one item and you try to

get everything from the non-existent

second item onwards the result will be

an empty list

so if i create a list with just one item

in it

and i try

to access from the second element

onwards the second element doesn't exist

so the result will be an empty list

don't worry too much about remembering

python slice syntax it's not an

essential part of sorting algorithms or

recursion i'm only explaining it to help

you read the code you're about to see

so i'm going to exit the python rebel

now that we've covered recursion we can

convert our sum function to a recursive

function

it'll take the list of numbers to add

just like before

now here's the recursive part we'll have

the sum function call itself we use

slice notation to pass the entire list

of numbers except the first one

then we add the first number in the list

to the result of the recursive function

call and return the result

so if we call sum with four numbers

first it'll call itself with the

remaining three numbers that call to sum

will then call itself with the remaining

two numbers and so on

but if we save this and try to run it

pythonrecursion.pi

well first we get a syntax error it

looks like i accidentally indented

something i shouldn't have so let me go

fix that real quick

there we go that's suggested to python

that there was a loop or something there

when there wasn't

so let's go back to the terminal and try

running this again

there we go now we're getting the error

i was expecting recursion error maximum

recursion depth exceeded

this happens because some gets into an

infinite loop it keeps calling itself

over and over the reason is that when we

get down to a list of just one element

and we take a slice from the

non-existent second element to the end

the result is an empty list that empty

list gets passed to the recursive call

to sum which passes an empty list in its

recursive call to sum and so on until

the python interpreter detects too many

recursive calls and shuts the program

down what we need is to add a base case

to this recursive function a condition

where the recursion stops this will keep

it from getting into an infinite loop

with the sum function the base case is

when there are no elements left in the

list in that case there is nothing left

to add and the recursion can stop

a base case is the alternative to a

recursive case a condition where

recursion should occur for the sum

function the recursive case is when

there are still elements in the list to

add together

let's add a base case at the top of the

function

python treats a list that contains one

or more values as a true value and it

treats a list containing no values as a

false value

so we'll add an if statement that says

if there are no numbers in the list we

should return a sum of zero that way the

function will exit immediately without

making any further recursive calls to

itself

we'll leave the code for the recursive

case unchanged

if there are still numbers in the list

the function will call itself with any

numbers after the first then add the

return value to the first number in the

list

let's save this and try running it again

python recursion dot pi

output the sum of the numbers in the

list 19 but it's still not really clear

how this worked let's add a couple print

statements that will show us what it's

doing

we'll show the recursive call to sum and

what it's being called with

we'll also add a call to print right

before we return showing which of the

calls the sum is returning and what it's

returning

let me save this and resize the console

a bit

and let's try running it again

python recursion.pi

since the print calls are inside the sum

function the first call to sum 1279

isn't shown only the recursive calls are

this first call to sum ignores the first

item in the list 1 and calls itself

recursively it passes the remaining

items from the list 2 7 and 9.

that call to sum again ignores the first

item in the list it receives 2 and again

calls itself recursively it passes the

remaining items in the list 7 and 9.

that call ignores the 7 and calls itself

with a 9

and the last call shown here ignores the

9

and calls itself with an empty list

at this point none of our recursive

calls to sum have returned yet each of

them is waiting on the recursive call it

made to sum to complete

python and other programming languages

use something called a call stack to

keep track of this series of function

calls each function call is added to the

stack along with the place in the code

that it needs to return when it

completes

but now the empty list triggers the base

case causing the recursion to end and

the sum function to return zero

that zero value is returned to its

caller the caller adds the zero to the

first and only value in its list nine

the result is nine

that nine value gets returned to the

caller which adds it to the first value

in the list it received seven

the result is sixteen

that sixteen value is returned to the

caller which adds it to the first value

in the list it received two the result

is 18.

that 18 value is returned to the caller

which adds it to the first value in the

list it received one the result is 19.

that 19 value is returned to the caller

which is not the sum function

recursively calling itself but our main

program this is our final result which

gets printed

it's the same result we got from the

loop-based version of our program the

end

we don't want the print statements in

our final version of the program so let

me just delete those real quick

and there you have it a very simple

recursive function well the function is

simple but as you can see the flow of

control is very complex don't worry if

you didn't understand every detail here

because we won't be using this

particular example again

there are two fundamental mechanisms you

need to remember a recursive function

needs a recursive case that causes it to

call itself

and it also needs to eventually reach a

base case that causes the recursion to

stop

you've seen bogo sort which doesn't make

any progress towards sorting a list with

each pass either it's entirely sorted or

it isn't

you've seen selection sort which moves

one value over to a sorted list with

each pass so that it has fewer items to

compare each time

now let's look at an algorithm that

speeds up the process further by further

reducing the number of comparisons it

makes it's called quick sort

here's some python code where we'll

implement quick sort again you can

ignore these lines at the top we're just

using them to load a file full of

numbers into a list

the quick sort algorithm relies on

recursion to implement it we'll write a

recursive function we'll accept the list

of numbers to sort as a parameter

quicksort is recursive because it keeps

calling itself with smaller and smaller

subsets of the list you're trying to

sort we're going to need a base case

where the recursion stops so it doesn't

enter an infinite loop

lists that are empty don't need to be

sorted and lists with just one element

don't need to be sorted either in both

cases there's nothing to flip around so

we'll make that our base case if there

are zero or one elements in the list

passed to the quick sort function we'll

return the unaltered list to the caller

lastly we need to call our quick sort

function with our list of numbers and

print the list it returns

that takes care of our base case now we

need a recursive case

we're going to rely on a technique

that's common in algorithm design called

divide and conquer basically we're going

to take our problem and split it into

smaller and smaller problems until

they're easy to solve

in this case that means taking our list

and splitting it into smaller lists

viewers a suggestion the process i'm

about to describe is complex there's

just no way around it if you're having

trouble following along remember the

video playback controls feel free to

slow the play back down rewind or pause

the video as needed after you watch this

the first time you may also find it

helpful to rewind and make your own

diagram of the process as we go

okay ready here goes

suppose we load the numbers from our

8.txt file into a list how do we divide

it

it would probably be smart to have our

quicksort function divide the list in a

way that brings it closer to being

sorted let's pick an item from the list

we'll just pick the first item for now

four

we'll call this value we've picked the

pivot like the center of a seesaw on a

playground

we'll break the list into two sublists

the first sub-list will contain all the

items in the original list that are

smaller than the pivot the second

sub-list will contain all the items in

the original list that are greater than

the pivot

the sub list of values less than and

greater than the pivot aren't sorted

but what if they were you could just

join the sub lists and the pivot all

together into one list and the whole

thing would be sorted

so how do we sort the sublist we call

our quick sort function recursively on

them this may seem like magic but it's

not it's the divide and conquer

algorithm design technique at work

if our quick sort function works on the

big list then it will work on the

smaller list too

for our first sub list we take the first

item it's the pivot again

that's three

we break the sub list into two sub lists

one with everything less than the pivot

and one with everything greater than the

pivot

notice that there's a value equal to the

pivot that gets put into the less than

sub-list our finished quicksort function

is actually going to put everything

that's less than or equal to the pivot

in the first sub-list

but i don't want to say less than or

equal to over and over so i'm just

referring to it as the less than pivot

sub-list

also notice that there are no values

greater than the pivot that's okay when

we join the sub-lists back together that

just means nothing will be in the return

list after the pivot

we still have one sub list that's more

than one element long so we call our

quick sort function on that too you and

i can see that it's already sorted but

the computer doesn't know that so it'll

call it anyway just in case

it picks the first element 2 as a pivot

there are no elements less than the

pivot and only one element greater than

the pivot

that's it for the recursive case we've

finally hit the base case for our quick

sort function it'll be called on both

the empty list of elements less than the

pivot and the one item list of elements

greater than the pivot but both of these

lists will be returned as they are

because there's nothing to sort

so now at the level of the call stack

above this the return sorted lists are

used in place of the unsorted sub-list

that's less than the pivot and the

unsorted sub-list that's greater than

the pivot

these are joined together into one

sorted list remember that any empty

lists get discarded

then at the level of the call stack

above that the return sorted lists are

used in place of the unsorted sub-lists

there again they were already sorted but

the quick sort method was called on them

anyway just in case

the sub-lists are joined together into

one sorted list at the level of the call

stack above that the return sorted list

is used in place of the unsorted

sub-list that's less than the pivot so

now everything that's less than or equal

to the pivot is sorted

now we call quick sort on the unsorted

sub-list that's greater than the pivot

and the process repeats for that

sub-list

we pick the first element six is the

pivot we split the sub-list into

sub-lists of elements that are less than

and greater than this pivot and we

recursively call the quicksort function

until those sub-lists are sorted

eventually a sorted sub-list is returned

to our first quick sort function call

we combine the sub-list that's less than

or equal to the pivot the pivot itself

and the sub-list that's greater than the

pivot into a single list and because we

recursively sorted the sub lists the

whole list is sorted

so that's how the quick sort function is

going to work in the next video we'll

show you the actual code

quicksort works by picking a pivot value

then splitting the full list into two

sub-lists the first sub-list has all the

values less than or equal to the pivot

and the second sub-list has all the

values greater than the pivot the quick

sort function recursively calls itself

to sort these sub-lists and then to sort

the sub-lists of those sub-lists until

the full list is sorted

now it's time to actually implement this

in code

we already have the base case written

any list passed in that consists of 0 or

1 values will be returned as is because

there's nothing to sort

now we need to create a list that will

hold all the values less than the pivot

that list will be empty at first we do

the same for values greater than the

pivot

next we need to choose the pivot value

for now we just grab the first item from

the list

then we loop through all the items in

the list following the pivot

we check to see whether the current

value is less than or equal to the pivot

if it is we copy it to the sub-list of

values less than the pivot

otherwise the current value must be

greater than the pivot

so we copy it to the other list

this last line is where the recursive

magic happens we call quick sort

recursively on the sub-list that's less

than the pivot we do the same for the

sub-list that's greater than the pivot

those two calls will return sorted lists

so we combine the sort of values less

than the pivot the pivot itself and the

sort of values greater than the pivot

that gives us a complete sorted list

which we return

this took a lot of prep work are you

ready let's try running it python

quick sort

dot pi

numbers 8.text

it outputs our sorted list

i don't know about you but this whole

thing still seems a little too magical

to me let's add a couple print

statements to the program so we can see

what it's doing

first we'll add a print statement right

before the first call to the quick sort

function so we can see the unsorted list

we'll also add a print right within the

quick sort function right before the

recursive calls again this string

formatting code is just to keep the info

aligned in columns

let's try running this again

and now you can see our new debug output

each time quicksort goes to call itself

recursively it prints out the pivot as

well as the sub list of items less than

or equal to the pivot if any and the sub

list of items greater than the pivot if

any you can see that first it sorts the

sub list of items less than the pivot at

the top level

it goes through a couple levels of

recursion to do that

there are actually additional levels of

recursion but they're from calls to

quick sort with a list of 0 or 1

elements and those calls return before

the print statement is reached

then it starts sorting the second sub

list from the top level with items

greater than the original pivot

you can see a couple levels of recursion

for that sort as well

finally when both sublists are

recursively sorted the original call to

the quicksort function returns and we

get the sorted list back

so we know that it works the next

question is how well does it work let's

go back to our file of ten thousand

numbers and see if it can sort those

first though i'm going to remove our two

debug calls to print so it doesn't

produce unreadable output

a quick note if you try running this on

a file with a lot of repeated values

it's possible you'll get a runtime error

maximum recursion depth exceeded

if you do see the teacher's notes for a

possible solution

now let's try running our quick sort

program against the ten thousand dot

text file python

quick sort dot pi

numbers 10 000 dot text

there we go and it seems pretty fast but

how fast exactly let's run it with the

time command to see how long it takes

time python

quick sort dot pi

numbers 10 000.text

remember we need to ignore the real

result and add the user and sys results

it took less than a second of cpu time

to sort 10 000 numbers with quicksort

remember that selection sort took about

13 seconds

that's a pretty substantial improvement

and with a million numbers selection

sort took so long that it never even

finished successfully let's see if

quicksort performs any better

time python quick sort dot pi

numbers

1 million dot text

not only did quicksort sort a million

numbers successfully it only took about

11 seconds of cpu time

quicksort is clearly much much faster

than selection sort how much faster

that's something we'll discuss in a

later video

what we've shown you here is just one

way to implement quicksort

although the basic algorithm is always

the same the details can vary like how

you pick the pivot see the teacher's

notes for more details

let's review another sorting algorithm

merge sort so that we can compare it

with quick sort merge sort is already

covered elsewhere on the site so we

won't go into as much detail about it

but we'll have more info in the

teacher's notes if you want it

both quicksort and merge sword are

recursive the difference between them is

in the sorting mechanism itself whereas

quicksort sorts a list into two

sub-lists that are less than or greater

than a pivot value

merge sort simply splits the list in

half recursively and then sorts the

halves as it merges them back together

that's why it's called merge sort

you may recognize this code at the top

by now it just loads a file full of

numbers into a list

let's define a recursive merge sort

function as usual it'll take the list or

sub-list that we want it to sort

our base case is the same as with

quicksort if the list has zero or one

values there's nothing to sort so we

return it as is

if we didn't return it means we're in

the recursive case so first we need to

split the list in half we need to know

the index we should split on so we get

the length of the list and divide it by

two so for example if there are eight

items in the list we'll want an index of

four

but what if there were an odd number of

items in the list like seven we can't

have an index of 3.5 so we'll need to

round down in that case since we're

working in python currently we can take

advantage of a special python operator

that divides and rounds the result down

the floor division operator it consists

of a double slash

now we'll use the python slice syntax to

get the left half of the list

we'll pass that list to a recursive call

to the merge sort function

we'll also use slice syntax to get the

right half of the list and pass that to

merge sort as well

now we need to merge the two halves

together and sort them as we do it we'll

create a list to hold the sorted values

and now we get to the complicated part

merging the two halves together and

sorted them as we do it

we'll be moving from left to right

through the left half of the list

copying values over to the sorted values

list as we go this left index variable

will help us keep track of our position

at the same time we'll also be moving

from left to right through the right

half of the list and copying values over

so we need a separate write index