Topic 12 - The Missing Parts 2: Sorting (Lists)

Outline:

• slow but easy sort, qsort is built in
  • insertion sort (of the sorted, where does the next element go?), selection sort (pick the smallest), or bubble sort (compare adjacent pairs, biggest to end, keep doing less each time)
  • in real code, always use a library (qsort example)
  • algorithmic analysis intro - how do we compare these with “average” / “worst case” / “best case” scenarios - how many values will need to be reviewed/compared to sort the list?
• algorithm choice is often about trading time (CPU/GPU/FPGA), space (memory / disk), and complexity (implementation work / correctness)
  • Knuth is the Encyclopedia
  • The Wikipedia visualizations, choose a sort
  • comparison/non-comparison/better sorts - algorithms and data structures course!

Transcript:

uh
[Music]
okay hello everybody uh
we have the enceladus saurus here if i
unmute her
yes okay she's laughing we're all here i
am
i'm a silly guy and i gotta i gotta be a
little less silly because we got some
sorting to do tonight
and sorting there's nothing silly about
sorting but there's something very
silly about comparison key sorting that
we're going to be doing but we'll
find a way to make sorting oh we're
going to make it silly
no chunking it though no no going for
the easy
there will be there will be variable
names i i assure you
oh man all right um so
that's that's what we got in store for
you i'm sorry about last week we had a
major tornado most people in connecticut
lost power
um including yours truly
and it was a lot of fun but we're back
and some of the settings are a little
rough so bear with me please
as usual let us know if the audio levels
are no good
or something isn't showing up right in
your stream just just ping us in the
chat
it's great to see all of you and one
little
item before i forget and we can talk
about it totally
at the end if we want is that we
have emotes
that's right we have our first set of
emotes which
of course are still pending approval but
more importantly we have some sub badges
so
nc who can type a message if she will
can show off one of our emotes there
there's the tau is better than
pi sorry badge i keep saying emotes um
i'm gonna be stuck on that all night but
uh it's it that
that is some badging so we're we're
we're turning into a real stream right
that's
this serious we had to get all the way
through a c course to
finally do that but you know hey here we
are
um so what do we have to do
tonight we have uh let's see we have
some learn stuff
um we have jessie here hopefully on your
displays
and she's got her cool badge and let's
see we've got some topics so we're here
in topic i did a little quick
subdivision of topic 11
and i broke out hashes from sorts that
was a little too crazy from what i was
saying last week
um and uh so tonight we're basically
going to be doing sorts now i'm not
going to be going
deep on data structures so we're going
to be doing like sorting light this is
like enough sorting to get through c
if you have an unsorted list but in
reality
never write your own sorts this is a
public service announcement
never write your own sorts they are
out of sort oh my god i can't believe i
said that okay so don't be out of sort
with me
here or her she's she can be out of sort
but
don't be out of sort do not write your
own sorts so this is for
educational purposes only
we are growing herbs and that's it
okay so this is this do not write your
own sort
always use a library i just i have to
caution that i should have put it like
big bold on the screen do not write your
own sorts okay
so i think we've nailed that let's let's
get down to
business here so we have our multi-user
pad which is open source
and of course we have a little bit extra
on our window because that's fun
and we were just kind of getting warmed
up so i'm going to clear all that
so that we can get ready we were just
taking a quick look at arrays with
integers
and it's been a couple weeks so we
wanted to get uh
fresh and good to go so let's go find
our glove
and let's talk about sorting now
we're not going to assume uh heavy
algorithmic stuff this is really a class
about c
not about algorithms for what i'm
showing you tonight
this is very important also part of why
you should always use a library
these sorts should almost never be used
in production code so even
even if you had an out off the shelf
library that was tested
totally worked worked in every
circumstance stable all the other
properties i'm not going to talk about
don't use these sorts okay these are
these are these are sorts that are
really
more useful for learning about sorting
than they are for actually sorting there
are far
more efficiencies teaching me like the
bad sorts
i'm teaching you the sorts that you
gotta cut your teeth with but these are
not
these are not source you should really
be using or we would
really be out of sorts but
okay um i'm gonna have to get myself a
rim shot so in the meantime
let's go look at the white board and
talk about topic what are we on 12
topic 12. all right so this is sorts
all right well sorting what is sorting
sorting is about
taking a list of stuff and you're going
to put it in order
so data arrives and it's in order it's
not an order we have no idea what order
it's in random order
and we can make no assumption about what
order it's in
so we need to take this collection and
that collection that lists
in c is typically referred to as an
array so we're going to use array
notation for it
and we need to our task is to take this
array of stuff
and put it in order so if we're just
talking about integers here so say we
have
uh a set of integers that are like you
know
7 13 8
i don't know they're what whatever they
are they're just they're not in order
okay um to then
what we want to do and however we want
to accomplish it we want as
quickly as possible and as few steps as
possible
to put this into something that makes
more orderly sense so in this case i
guess it would be two
seven eight and of course i'm cheating
right now
i'm not using the algorithms that we're
going to be talking about i'm just sort
of eyeing it up and saying yeah
it's that two that's going to go over
here and then that's
seven that's going to go over here so i
guess if you had a neural network
trained you could do it the way that i
just did
visually but um normally that i can do
yep that that would be let's just call
the
the neural network version of this uh
overkill
let's let's let's say that we don't need
to actually train
any ai to do this we can we're gonna do
this the old-fashioned way
okay um oh and by the way uh loaf bone
asked
why not teach the ones that'll be used
the reason i'm not going to teach the
ones that will be used is because
they're hundreds sometimes thousands of
lines long
and uh they're they they really
obfuscate
um sort of the the principles of sorting
and you know
getting into sort of the algorithmic
stuff now what i am going to do is i'm
going to show
like kind of the sort basics um and so
we're going to try to pick some
you know kind of straightforward source
that are not super efficient but they're
they're
clear to understand hopefully um so here
those
right like i i kind of understand what
you're saying about
sorting things in sort of numerical
order
but isn't sorting
and maybe i'm just getting a little too
esoteric with it but isn't that
really relative like what order you want
and i have been
so just totally as a caveat i've spent
literally eight to nine hours today
fighting with
uh awful array
stuff in python and so really trying to
pick out what values i want or what
what things i want sorted is so it's
relative because sometimes you don't
want the greatest number you don't want
the smallest number you might be looking
for something else
is absolutely true that is absolutely
true um
so what you're referring to you're
talking about what order
and what order you want is called the
collation order
and yeah i mean i didn't define it here
i just jumped right into what's called a
min sort this is
you know min sword so i'm doing a
minimum
you could say numerical sort so i'm just
taking the lowest number and i'm putting
it towards the beginning highest numbers
towards the end
but i mean we could also do a max sort
i mean and the thing is about sorting
algorithms
it doesn't really matter is the reality
like i need to have
a collation order it doesn't really
matter to the sorting algorithm what the
collation order is it only matters that
it exists
and okay there is a notion of what's
called stable
versus unstable and this is getting a
little bit into the
computer science um theory so i don't
know
how far we should go down this but can
you sustain because i'm sorry that's
really
interesting and and i get what you're
saying about a collation order needing
to be specified is that
a rule that when you're building these
sorts you can kind of specify that
no you have to you have to there you
cannot sort unless you know the
coalition order
you you can't order is not strictly
necessary usually we drop it in speech
we just say like the coalition or
you know you could just refer to it as
the order pick one
but uh you it must be defined
what specific collation you care about
for the particular problem you want so
for example if you wanted um you know
this thing you know in order of least to
greatest
then that's kind of what i just did so i
the collation order i chose was sort of
minimum
numerical is my collation function
um i could flip that and say i no i want
it the other way
you know i i want this thing to be you
know 13
8 7 2.
um and and that's fine right that that's
how i do that in terms of the sorting
algorithm and that i'm gonna just hand
wave instead of defining
but how i do that is different from
what collation i'm using the collation
is really my choice
so okay i get to pick what type of
collation i want
my algorithm that i choose doesn't
really care
what choice i make it just says as long
as there's a definite collation
so it's like colocation neutral
essentially um
not 100 sure but okay so
it's it's it's um it's
the algorithm itself doesn't care what
your collation
is so there aren't like certain sorts
that are are better suited for
min sorting or max sorting or something
like that so they're neutral towards
they they collect almost all of them are
neutral towards the collation in fact
they usually
some of them even specify like a
collation function
so it'll say like how do you want this
collated
you know and i see and by the way the
special class
of sorting algorithms that we're going
to be talking about are called
comparison sorts
and that's important because in order to
do a comparison sorting i'm going to
compare two of these values at a time
now which two and in what order and all
that that kind of gets into which
algorithm we pick
but these are all going to be in involve
some sort of like take this value
compare it to this value
which one according to my collation
function which one
is less or which one is more um
so and so what is the unstable and
stable unstable distinction you
mentioned earlier
that's yeah like i said that that's kind
of getting a little bit esoteric stable
and unstable have to do with when things
are equal
so um this is less relevant so to the
particular example i showed up
up here it actually there's no
difference at all um
because seven is seven is seven right
you know so if i have
what happens if i have two sevens in
this list
you know so it's like seven so which
even though their indices will be unique
the values of those and just at those
indices will be the same
yeah so how do you do they stay in the
same
spot or do they move but it doesn't
matter because they're both the same
value
so in our case we don't care if they
move because they're the same value
now that's not always true like so if
i'm sorting
like dictionary entries i might actually
want them to stay
exactly where they are in the case of
equality like so i might want this seven
to stay here versus that seven
now it's silly in the case of that that
i'm showing right here with numbers
because
um it doesn't really seven seven so
like they're they're totally identical
in all regards but
in in reality sometimes they're not
you know like i might have like records
of like a name
and a time so like say like i'm saying
like when the person came through a gate
so i might want to sort on
time like but that's kind of not a good
example um
i'm just thinking that like you know i
might want to leave it so that like
if i was sorting on name like it would
leave them in the original order
that they occurred in as opposed to
changing their order you know because
the associated data is not the same
right so that's kind of getting a little
bit into what's stable and unstable
means but i'm not so essentially it's
just so with without needing the
specifics it's basically it's a it's a
property or a characteristic of the sort
that has to do with how it handles equal
values
that's generally true yes
um i i like that so we'll we're going to
go with that okay
um and we're going to switch to green
because now we're actually going to
start sorting
so how do we actually go about
sorting these things well i mean there's
different ways you know
you're probably used to this from like
poker you know you can have cards in
your hand
and you know you want to put them like
okay i'm going to put the ace over here
and i'm going to put the
you know the 7 over here you know so
like maybe i want my higher value cards
to go over here maybe i want my lower
ones here
maybe i'm playing bridge and i want the
lower ones to be on my left so that i
can quickly access
again collation is
kind of like the sorting algorithm
doesn't really care um
okay it really just matters like you
need to specify
up front what type of sort you know so
what what collation
um is this visible or is this like a
really dark color
i can see it very well okay um cool
um so funny story really quick small
interjection
it's funny that you bring up poker
because uh poker is such an interesting
game especially from an ai perspective
because it's
an imperfect information game so you
know you don't know what your
opponent has and i know sorry i know
that's not your point but it's no no
it's funny that you bring up poker
because i had to
actually brought up poker and bridge not
accidentally because i chose two very
interesting computational games
and i know like a full house sort of and
i
i know that royal flush or something is
really good but
yeah it's very fascinating because i had
to look up all of this
really interesting like poker strategy
and whatnot for
it was a lot of game theory and whatnot
oh yeah for kind of teaching ai how to
play games where
you're choosing making decisions but
based on imperfect information it's a
very interesting problem
it very much is so um so i mean but
again like so collation sort of depends
on domain right you know like so
in the in the case of cards i've got
these non-numerical things that have
numerical values associated with them
like
you know like ace usually picks up an 11
value like in blackjack
you know but it could also pick up a one
value so which end do i put it on
i mean it's kind of a mess in blackjack
but
or like you know something like a king
or a jack is a king greater than a jack
well it depends on the
game that i'm playing i mean like in
some games these are both 10
in some games like this jack is less
than this king and sometimes like so
again collation is outside of sorting
okay so you need to have your collation
sorted out
my god oh my god seriously okay so
somebody in chat needs to start keeping
track of the number of guy pumps
today there has to be some kind of
penalty like
swears or something so i'm allowed to i
don't know oh man
you got to start i think we're at three
or four three so really bad puns
i'm i'm i'm putting tickets in the
corner i got we need a punt bot
all right you need to have this be like
something i can call and chat
okay i like where your head's at i'm
gonna i'm gonna write that down
all the stuff that i never have time to
build for my own channel yeah well hey
why don't you build it from my chat
because you're coding all right can we
do it in c
we can do it in python if we want to
finish it oh yes
python oh wait till we get the network
so much python in my sleep like
yeah that okay um yes i'm thinking i'm
in c
mode i promise we're gonna we're gonna
talk about pun bot later um semicolon
so anyway um so we have a collation you
pick it it's arbitrary to the sorting
algorithm but it's important that
you have it before you start sorting um
so see i avoided the pun that time you
see that
i want to say you have it sorted out
i'm just gonna strike that okay so
actually can we add well
this might be a yes no but if it's if
it's a longer answer we can add this to
our topics for later
yeah but would you ever consider
teaching like not a python for
beginners because i know you're doing
python for beginners and see as an
additional language and things like that
but would you ever teach kind of like a
i don't know intermediate or advanced
python uh
yeah absolutely okay um all right we
should talk about that
we should because something like sorting
algorithms like if you want to get
really in depth with sorting algorithms
you don't want to be messing around with
memory
so like c is kind of a rough place to be
studying sorting so that's that's part
of the reason we're trying to work with
like
the basic sorting algorithms and not get
into like crazy stuff
but like if you know these things like
you said they're you know they're very
common that you should or you should
you shouldn't build your own you should
get them out of the box yes and
i think i've used a couple thank you for
hearing that warning oh god never use
bubble sword
it's like so i was you know in a in a
job interview
and they part of their
uh sort of coding whiteboardy type
interview
was to build your own sort sorting
algorithm yeah
and it's it's it's amazing how
disconnected those questions are often
yeah from the actual job but we're going
to talk about that at the break
i'm going to get on the soapbox oh yes
so let's let's just let's say
whiteboard coding sorts so i'm going to
ethically oppose and
ethics okay good um
so by the way if you ever do get caught
um having a whiteboard
a sorting algorithm just because
somebody's evil
then you should use one of these sorts
that i'm going through tonight because
they're
relatively easy to get right i mean
no sort is really easy but like like
these are on the easier end of like you
want to aim for
correctness rather than efficiency
because if you're if the
if the question's really efficiency it's
a stupid question because like
import the right library and like it's
like i remember building my own and i
had never done sorting algorithms before
but i was like okay i'm just gonna math
my way through it
yeah and i remember doing it but yeah
yeah yeah but that's
and that is the right place to use a
bubble sort by the way is like you know
that's one that's
pretty easy to get right um also it was
a timed whiteboard interview yeah that's
even worse all right
okay let's see so
all right we're we're back to we're back
to sorting so we're going to talk
about two swords up front and hopefully
i don't confuse them because i always
love to confuse them
and they're they're very close to each
other
and these are the only two that we're
going to be implementing tonight after
that we're going to be using as a reach
goal
we might reach for q sort but we're not
implementing it we're just going to
reach for it okay so i'll get to that a
little bit later
and which is by the way short for the
quick sort
and we're not going to do tim sort even
if nathaniel brings it up i don't know
if nathaniel's here but we're not doing
tim's sword
but one of the funny things about tim
sort is actually and this happens in
java as well
they fall back to insertion sort
for small numbers of items because it
turns out that despite the fact that
insertion sort is not like one of the
best sorting algorithms it's actually
still pretty performant in low amounts
of data
so it turns out that a lot of these
other more advanced sorts they just
require a lot of overhead to kind of get
going
so unless you're working on a very big
list then it's kind of not worth it
um okay so let's talk about these well
you know you spoke and he showed up by
the way daniel we were talking about it
i invoked him nathaniel i'm not doing
tim's sort just just for nathaniel
reference so we're not we're not
i'm just going to head that one off i
don't know what that is but i'm sorry
that you were deprived of
the thing and you've been missing out on
some high
quality puns which might have a
different correlation
with the other person on this call but
anyway so moving on we are going to
talk about uh insurgents okay so
you already did bubble sort you said uh
in a panic at one point okay because it
was easy and straightforward and i just
it is easy and straightforward and you
should never use it
okay except except for whiteboards
except for whiteboards that
there was a whiteboard interview anybody
who's evil enough to ask you a
whiteboard
sorting question should deserve like
efficient and straightforward sorting
algorithm that you just call the panic
sword
that people can use oh no we'll get to
that we can we can talk about the sleep
sort by the way
if you really want to if you want to
talk about some they're they're called
bogo sorts but they're sort of like
ridiculously long runtime ways of
sorting but
they're very funny um anyway so before
we get to that
and some of our favorite silly ones um
if we're gonna get this right and i
don't mix them up so i'm gonna try to
look at my notes
i think selection sort is probably
easier to describe and insertion sort is
easier to get right
so selection sort
is sort of like i select the lowest
number
and that's my next one so going back to
my numbers let's
let's pick a few numbers uh what what do
we have for uh
i don't know i'll pick some numbers
let's see there's seven viewers i don't
know
we talked about it in very brief terms
only
so my my current understanding is that
that is a sort of like
characteristic or property of sorting
algorithms
that has to do with how they handle
values that are equal
and so we didn't go into it much more
than that just because
i guess that's more like computer
science and not as much
so yeah it is it's important but
um nathaniel is right to bring it up uh
so i mean that
i would expect him to keep me honest so
um all right so that
let's just start with this array of
numbers um as sort of our example
um and by the way that's totally fine
ccv in fact i think we should start like
a resistance movement for anybody who
asked for a sorting algorithm on the
board
we should always pick a sort and like
just let
let's let's make up like chunks or and
that's just that's what they're going to
get because you really shouldn't be
asking
don't if you're in an interview do not
ask people to
implement a sword on a whiteboard it's
ridiculous also especially i'm sorry
i'm not a software developer so no
especially to get that for me
i was like uh what
and also yes team chalk okay so sure can
you promise me one thing guys yeah yep
yep
so if i make it all the way through c
and
you know i'm sticking with it and i'm
especially like we've talked projects
and and future goals and everything and
i'm like you know
being a good student everything can you
can you make like a cool
chunk emote yes
yeah i will i will do that um there is
there's one there's one caveat to your
uh request which is that i'm not
eligible for any more emotes
um but i will make it my next one
okay if twitch ever gives me one but
if if if i you know what i can do i can
definitely put it in discord
so i i think there we go i can meet you
there all right that's a good compromise
we'll see if twitch ever decides that
they want to push live coding then we'll
worry about it then
i got it built an operating system
that's what
dennis keeps threatening me with yep
that's pretty cool
um okay so right so we have these
numbers we have to put them in order
now without looking without developing
complex visual stimulus and neural
networks that can just see all the
numbers and
decide on what the right order is how
can we compare
all of these things to each other and
try to get them into the right order
well
so like i was saying before with
selection sort what we do is the the
the gist of it is look at everything
and so we're going to start at the
beginning so we're going to look here
this is location zero this is location
one
two three so we're going to look at
location zero we're going to say well
we we have nothing to compare it to so
let's compare it to
three all right which of these is
smaller
between seven and three yep three
okay so what we can do is we can start
this off by saying with our seven we can
say
smallest is
seven okay so and then we look at the
second one we look at
location one we say three is three
smaller than seven
yes okay so we're gonna we're gonna
strike seven and we're gonna say the
smallest is now three
all right is three smaller than nine
no uh yeah so please three is smaller
than nine i mean sorry three smaller
than
i mean we're not nine is not smaller
than three i mean sorry
my bad oh god all right yeah now i
really don't understand what's no no no
you're right you're right
um so nine is bigger so we're not going
gonna call nine the smallest we're gonna
leave three as the smallest
right so we're gonna make north nine and
then we're gonna look at
eight and we're gonna say are you
smaller than three
so you iterate through once you find the
smallest thing and essentially just and
we found it because we just went through
the whole list
and we said three was the smallest so
put
three at the beginning yep
okay now hold and the way we're gonna do
that is we're gonna swap so we're gonna
do it in place i shouldn't be drawing
this as a separate list
so we're going to take 7 and 3 and
because 7 is in the spot that we want to
put it in right the smallest spot
and we're going to take we're going to
swap them so we're going to say this is
3
and this is 7. okay now we're going to
hold that
we're going to say you're done right
because we know that you're the smallest
one
now next smallest one load up the
smallest again we're going to load it up
with 7
because that's what we're looking at
here right
and we're going to take 7 and we're
going to compare it to 9 is it smaller
yes
is it smaller than 8 yes 7 is your next
smallest number so we're going to leave
it where it is we're just going to move
forward the list
now we're going to take our smallest is
9
and we're gonna compare it to the next
entry which is eight
is nine smaller than eight
no no so we we're going to say no
our smallest is not nine it's really
eight and
now we're gonna take this eight and well
we're done we have nothing else to
compare it to
so the next smallest one needs to be the
eight
so we gotta swap places with what's in
the current
you know the place where we've been
holding so we're gonna swap that
we're gonna swap eight nine
and we have one entry left we have
nothing to compare one entry to other
than itself and we know that it's
not smaller than itself or not bigger
than itself or not anything about itself
we're just not even going to compare
it to itself so we're just going to say
this list is now sorted
3 7 8 9. we did it by successively
taking
the smallest one so we go through the
list each time
of what's not sorted we say okay this is
small three is smallest
then seven is smallest then eight is
smallest and then nine is
smallest and we need to just make sure
that they end up in the right spot so we
just have to be careful about our swaps
makes sense yep yeah i think so
good that's selection sort
so we do it because we select the
smallest one
okay um great
and now the one that i always love to
mix it up with and nathaniel will keep
me honest if i do manage to mix them up
which is the insertion sort all right
so insertion sort
the gist of insertion sort
um of the ones that are sorted
where does the next one go
so if we start our list off you know and
i forgot exactly which numbers we had so
i'll just make up some new numbers do
you want to make up numbers uh
5 11 12 17
21. oh going going big huh
go for it bigger list and and you're
putting two of them in order look at
look at this
okay so um these are oh i guess i should
have i'm gonna swap these just because
yeah
you know what let's let's make this a
little more fun um
in fact you know what let's let's swap
let's add a little more disorder here
we'll leave 12 kind of it's doing the
right thing um
and then we're going to just swap 21 and
17. by the way
thank you the only one matt
i appreciate the follow um so
okay here's our list of numbers so we're
going to forget about this this didn't
happen
don't don't look at that okay um
so this is our unsorted list we're going
to pick a collation order because we
need to do that first
which is going to be hey what's up cam
how you doing
i got power back by the way
cam has been following along i've been
posting on my discord
um i've been building a solar array with
a couple photovoltaic cells
and a charge controller and some
batteries and
i managed to charge phone i tried to
stream off it but it turned out
everybody in the world switched over the
cell network and you could not
stream on it so
paul blart mall cop sup gamers yeah
death ray thanks jess for the
recommendation oh
cool oh you know only one match okay i
don't but okay hi i made a
recommendation
sweet thank you for joining i'm so bad
with names it's not personal i promise
i barely remember my own you're fine
twitch name so
okay so from our original list first
thing we do we pick a collation so we're
going to stay with the same one
and say minimum
we want to do a min sort numerical again
yep you'll notice the only thing that
changed
to turn that into a max would be we just
swipe
we just switch our comparison function
yeah you just exactly
so that's literally the only thing that
changed and that's why i was saying like
it doesn't
the sort algorithm itself doesn't really
care what the
what it is no last smiles no bubbles
apparently
we're anti-bubble sort here oh no we're
anti all of these sorts actually i told
you do not
everybody do not use this in production
code this is just
for learning how sorting works okay
don't i don't want to catch any of you
implementing this in real production
code okay
all right so minimum numerical okay so
we've chosen a collation order we've
said
we're doing this um and yep we're doing
insertion
we just did selection last miles by the
way um
you're doing a pr as we speak really
okay oh boy i had
better paul blart mauld cop i had better
not see a selection or an insertion sort
in that pr
no we're not doing bogo sorts no no that
chat is taking over
they're they're just oh boy okay
so we're doing insertions all right so
how do we do an insertion sort the the
intuition
was of the sorted where does the next
one go
so if we start off with our list how
many are sorted
well we trivially assume that the first
one is sorted
because a list of size one has only one
sort order right
yes like so if i imagine if i just cover
this up and i don't have a good way to
draw that without
crossing it out so if i just pretend
that this part that's boxed is not there
and my entire list is this 11
then i can say that this is sorted on
its own
okay i see what you're saying i mean
it's kind of a little bit of a tautology
but yes
yeah no it is it's very tautological we
just assume blindly that
a list of size one is sorted okay okay
seems like a reasonable assumption okay
no no we're going to do q source don't
don't don't worry
no we're not you're just not going to
implement it i'm not that easy okay
okay um so all right
now i have a list of size one it's
sorted a list of size two
so the goal with insertion is i find the
place where this thing's gonna belong
and i put it there i insert it okay so
i have the five i assume that my
previous list which has only one thing
in it the 11 is sorted and now i want to
grow my list by one entry to two entries
and where am i going to put the five
in this sub list so this sub list which
has currently only one thing in it
where do i put it well i'm going to do
it i'm going to just look
through the list there's only one thing
in the list so i compare 5 to 11
and i realize that 11 sitting in the
spot where five wants to be
right okay so i'm gonna trade them
so let's let's swap this and swap that
so we're gonna do five and eleven and
we're gonna say that that's my whole
list
is the 5 and the 11. is this sorted
right now
yes yes i'm always going to keep this
part of the list sorted
okay now i add a new entry 12
and i say where i'm going to compare the
12 to the 5 is it smaller than that
no is the 12 smaller than the 11
no no so it turns out the 12 is already
in the right spot
so i'm just going to leave it right
there and i'm going to grow my sorted
list
yes okay so i've got 5 11 12 and now
21. this is my previously sorted
so 21
smaller than 5 no smaller than 11
no smaller than 12 no all right turns
out it's actually in the right spot too
so the important thing here is i'm
always keeping
a sub-list that's sorted and i'm growing
it by one entry each time i'm inserting
the next one
okay okay and now my last one up
i got the 17 so i've got 5 11 12
21 17 is going to ruin everything okay
so
i've got my nice sorted sub list and i
take my 17 and i say is it smaller than
five
no okay it's smaller than 11
no nope smaller than 12
nope smaller than 21 yes
okay so what i'm going to need to do is
cut a hole in here
and all of the things that are to the
right of it are going to have to move
sounds very unsee like this is why i
said
that it's easier to describe insertion
than selection but it's harder to get
right
of all the different ways you could do
that in python easily
but then yeah pc is so
restrictive particular maybe
uh that i just just you casually say
something like cutting a hole in this
and just inserting it in
and thinking about that from a c
perspective is like yep
you're right and by the way i just saw
last miles with his
top-notch belgian beer
he wants to see a q sword so mate you
might have
one of my subscribers you might actually
have to do this i mean this
this and by the way last miles you yeah
okay you're you're in for
let's see where we get okay so i don't
know if we're gonna do
clean q sort but we might do some sort
of q summer
okay um so what i need to do to cut a
hole i can't cut a hole in memory right
like you're just intuiting um so what i
need to do is i need to sort of like
take this thing put it on the side
you know i'm going to need to put that
17 somewhere else and then what i need
to do is i need to move
every one of the entries that's in front
of it over
to make space so that there's somewhere
to put that 17 in now in this case i've
only got one entry i have to move over
so no big deal i just take the 21 and
i'm gonna move it here and then i'm
going to take the 17 i'm going to slot
it in there and i end up with a final
list of five i'll
stay sideways 11 12 17
21. okay okay so i end up with a sorted
list
but you'll notice it's just a little bit
messier
than selection in terms of because of
that little
memory like if it was free to have holes
in memory then
this would be a lot prettier i mean you
could just based on the
like the size of the list that you're
starting with you can allocate the right
memory because
it's not like you're that that amount of
memory is going to somehow change
that gets into how much memory do you
want to throw away for your sort
so you can do something which is called
an
in-place sort
which is i'm only going to use the
memory that's given to me by the list
versus like i don't know what you want
to call a non-in place or an out of
place sort
and that's just out of swords
i couldn't resist it okay what are we up
to six one two three four
five six yeah okay that was six bad buns
okay so
um what's the penalty come on there's
just no penalty that's the
penalties okay so
um yeah and an out of place sort is
really
like additional memory so
and that's kind of speaks to what you're
talking about um
which is if i can allocate another array
to store my answers in
then i could be a little bit smarter
about this and i don't have to worry so
much about swapping
but that's kind of the key
takeaway to that oh and i just saw last
miles
there's arguments happening in chat
about coding languages oh
python's fine it's
oh no i i just
love how much you can get done with a
couple lines of python that's that's
one of my real loves of python but
anyway um
you young lady on the other hand
have some very fun times coming up
because you're going to have to get both
of these right
okay so how do you feel high level about
these two algorithms so
i feel fine about the first one uh did i
feel icky about the second one from a c
perspective like
thinking ahead specifically about
implementing it in c
like both of these are sorts that
despite not knowing maybe the specific
name
are sort of things that i've either seen
or casually like
it would be very easy for me to do that
in python because that's just
sort of my native language but thinking
about doing it in c specifically i'm
apprehensive
about the insertion sort okay
well then because you said that let's do
no
let's do the selection sort first i'll
give you hey okay i thought you're gonna
be like no
no no no no sorting's harder sorting is
hard enough to get right so
it's it's like one of those things it's
it just
i got them wrong the first time i
re-implemented them like i'm like
was i off by one damn it okay
so it's just there's plenty of things to
be off now just
chat real quick can i get an f in the
chat for last miles because last miles
is dealing with this
bit of a nightmare with nvidia kernel
module loads
looks like uh he's using the non-open
source nvidia drivers and thank you for
the f's that's that's for
last miles pain um and
i appreciate that i'm gonna i'm gonna
throw an f there too for
for last miles okay so last miles we
hear you
um so but
that is neither here nor there and
jessie does not need to worry about
nvidia drivers right now she's got a lot
oh i have
secrets lots of that no no no no no no
worrying about c
code we're we're worried about c code
not nvidia drivers so
i don't know if that's a good thing or a
bad thing i don't know how i feel about
that all right
let's let's warm this up with um
let's just make uh the integer array uh
let's just uh
i don't know let's let's do like uh five
entries in an integer array
and uh actually make last miles having a
bad day so use a uint
um let's see let's use uint8t
yeah and just just to be a little
helpful i'm gonna give you that library
so
this this one's going out for class
miles um
so yeah just pick an array for that um
and we'll initialize it with some random
numbers you know well
let's use these numbers let's let's
let's use this
example we have 11 5 12 21 17.
okay so before we really get into this
why don't we give ourselves a debugging
routine
um so let's let's have a function and
don't worry about you can copy
stuff on the stack all you want i'm not
we're not we're not worried about memory
efficiency at the moment
um so let's uh let's just have a uh
a quick little display function that's
going to just print out whatever's in
the array right now
so okay
and get off that snake case come on
we're in c
how do you do what what's your what's
give me some
camel case it's actually c goes both
ways but we've been doing camel cases
both camelcase is not wait
thank you all right um okay
uh let's see which by the way
just saying is less accessible for
people with dyslexia
so you should use underscores python's
more accessible so
people who hate python anyway i did not
know that uh yeah
so no nathaniel no screaming camel case
yeah it's that one i'm a big fan of
i'll do that for everything okay
um what am i doing okay so it's gonna
take
uh a an array
uh-huh so so
i can tell you right now that this you
could just
make it the same size it's okay if you
yeah yeah you can
that that's a little messier so why
don't you just make it a pointer like a
you went 8t
pointer so that's just
yeah so oh i know that i'm bringing
pointers up but you know it is c
so we gotta we gotta stay loose with our
pointers
yeah it's gonna be some array and we're
gonna just
for tonight we're gonna just know that
there's only a fixed number in there and
we know what that number is in advance
so that number is going to be
5 for now so
so um
let me think actually so can i i'm going
to have it have two
right because oh yeah you could pass it
in
right yeah but if you're really gonna do
that then you gotta gotta use the right
type
what yeah we we use size t for
at that don't worry about it you you can
the size t is my security blanket
so size t is size t it's
everyone used to just specify like int
you know but they finally said let's
just make a numerical type of integer
which
corresponds to however like array
subscripts
like so and what is the benefit of that
as opposed to just well
it's not platform specific well sorry it
it removes the
platform knowledge that you would need
like is this a 32-bit system or a 64-bit
system
okay it basically says that's none of
your business it's a size t
okay that makes sense yeah we can use
that then
that makes sense it's it's just in our
case it's really just an
unsigned integer but um okay
um so 64-bit systems that's unsigned
long
oh it's been so many weeks
um you would use so if you're doing if
you're doing proper size t
stuff then you would use size t for your
loop iterand as well
really you got to be consistent i'm
totally fine with you
you know what how is that a size though
that makes them that because we're good
because we're going to use it to
subscript the array
right you're going to use it to like
index i see i see what you're saying
okay so fine
i don't care which one you use but you
got to be consistent all right i'm
staying in my my
my happy place yep that's fine okay
um and then until well this is less than
or equal to
good luck class miles i'm crossing the
fingers for you there you go
um
and then okay
the brain is slowing down okay um
we're just gonna get into it
oh no do i have to like because it's a
pointer but but wait no no no hold on
so no we're fine because we're fine
yeah that's fine right because the first
an array is referred to anyway as a
pointer to the first element in the
array
yes no mental violence index code
i believe yep you're right
okay um you are correct
so let's just test that out before we go
anywhere with our
sort stuff okay so
do i have to put a return i can't
remember no it does
no it's void void is your return so
you're not actually okay sweet
all right so let's see let's print bonk
bonk and
so oops
uh and by the way last miles i think you
were one of the early subscribers i
actually have some
subscriber emotes coming shortly we're
just
waiting for twitch approval at the
moment
i think there's a few in there that
you're really going to enjoy though
humor also declaration did you mean
print f i did mean printf what did i do
wrong
well let's take our errors one at a time
so okay
well it hm to me did you mean oh do i
need to put an underscore before the u
oh you know what i gave you the wrong
include because i'm a bad person
i meant to do this okay i was like
what did i do wrong okay just bad guy
um but i did the exact same thing that i
always do
which is ignore that don't look at it
oh that's a nice emote you got there
from
oh that's an awesome ebook beauty
that is that is very nice i've been i've
been stressing about
emotes all weekend i gave up being
good at twitch people show up for what i
do like i want to give no i
i'm with you i'm with you i'm just i'm
trying a little harder
i don't speak artistic language so i was
having a lot of trouble describing what
i wanted but
you know i think i think some of the
ones are you know i think i think the
programmers are going to like them
i feel you so much like i can appreciate
good art and i have enough of like a
knowledge of
of art or music or something to
appreciate when somebody else is
talented at it
yep but nothing infuriates me more than
just the casual way that people
sometimes like
at work for example will just be like
well do the thing like make
make this artistic thing i'm just like
no i'm a numbers person like you want me
to like derive something
i am your human terrible but don't make
me try to think about whether or not it
looks good
i don't care about that like i
one of my best friends is is an
incredibly talented like ui
graphic designer and it's just it's
magic to me it really is
that she could just walk in and just be
like well i don't know if you noticed
but last miles actually just mentioned
who did that wonderful emote
and i am writing it down
because these these artists that's
programmers we're like a dime a dozen
these days but marc esserman isn't an
artist he's like
a chess grandmaster oh i do he's who's
teaching dennis chess
that's awesome oh well i guess i'm
probably not gonna be able to hire mark
esterman
i would not maybe reach out to him for
graphic design okay
all right i was hoping there you know
i can't tell you that the the art that
you're going to see is uh i
i really have a thing for pixel art so
this is uh
mostly pixel art stuff so i i love
pixel art but it's i'm having a lot of
trouble finding pixelers
okay so a good place to ask just let's
see
oh i've been asking i've been dropping
in discord i have dropping your discord
i don't know i'll drop here if anybody
knows
uh great oh look look at this we're
getting we're getting recommendations
okay i feel bad because i'm totally
distracting you from no this is the bad
stuff that's coming
i need better emotes for my channel too
but somebody uh carson drew it okay
loaf bone make note of these people at
the at the moment i
actually am i'm out of emotes so i i
but you know you know that when you need
to find these people they're hard to
find
okay so we know that we can print things
out great now all we have to do is write
a function that's gonna sort stuff
oh boy i can't stop here like i can't
just revolutionize victory i printed
something on
come on you're at the end of your c
class you do you can print this out
piece of cake
a little bit of pointer arithmetic no
problem now listen you don't need to
return up just just to be nice because
i'm trying to be nice
you don't need to return the sorted list
so it's sufficient
for you to just print out at the
beginning of this function that you're
about to write
what the numbers are coming in and then
print out what they are
at the end but don't worry about
returning them so i'm not going to make
you do a little extra point of
arithmetic for right now
ship it it's perfect i care about
making things look good i'm still bad at
it yes
cynic doki i'm i'm with you i
also excellent name really
yeah so it's uh uh hold on
i didn't find it it's it's it's it's a
sassy spelling of uh
i thought it was synecdoche so it's
uh like it's basically where
how to explain it um it's kind of where
you man you're digging deep just to get
out of right in this sword aren't you no
no
it's where like a uh a specific
term is used to refer to a collective so
like um
oh you could say like like a murder of
crows
nvidia uh and or let's actually think of
like riot games uh developed this game
or something or
i'm trying to think of a good example
like where it actually refers to the
team so maybe
like maybe sports so like uh boston won
the latest hockey game which i don't
think they did um that's a shame
so there it's not that boston the city
want it it's synecdoche
so you're like referring to boston the
team the whole of the team is a
collective
using the city where that team resides
oh i did not know that word that's a
great word
and i'm probably just miss i'm very
terrible no but that's a great
pronouncing words that i've only read
but i think that's uh what that means
but
also it's a neck dokey i think that's
what you're
i think that i okay maybe that's just
the link was to be fleece
the key is giving you a little up on the
nathaniel's definition which matches
what you're saying so
i'll buy it but you're you are not me
again lady you're not getting out of
this you're you're writing the sword
algorithm
all right i like to deserve poutine for
this a reward
a delicious reward or motivation okay no
i'm doing this all right so
all right so this is the initial sort
that we talked about
it was like the swappings you could you
could pick you want you want to go with
selection that's right whatever you want
to implement
one of those two any color you want as
long as it's not
and you said well let's i'm gonna i'm
gonna just do this for now so
[Music]
a sassy spelling yes
i sassy spellings i'm all about
wait done it wait dennis are you a
hockey fan i played ice hockey in
college and i am a huge boston bruins
fan
you're not getting out of this you're
not getting out of this
you're not getting out of this i want to
see a sword
any sword you want but i want to see a
sword
but i want to play video games before my
homework
no no no you have to write your video
games before you get to play them so
let's let's get this sort
this is nowhere near as fun as a video
game
you'll be sorting in video games all the
time i guarantee it if you're ever
programming one
so strophe unfortunately we had to pause
our game development lessons but
we did get most of the way through uh
doing pong which was really fun
last miles um hockey am i canadian
well you know i didn't want to assume i
didn't want to stereotype you but we
should talk some time about my very
brief
uh ice hockey cam you're absolutely
right i like that henry
ford quote the hobson's choice i'm a big
fan any color you want as long as it's
black
any sorting algorithm you want as long
as it's one of these two oh and low
phone why do you like the caps again
oh sass okay um all right so
we have an array okay talk talk me
through the intuition first what do you
want to do
so what i am thinking of is that
i'm thinking about doing a for loop and
oh don't get that specific start
with what what is the sort start with
that rephrase
okay so essentially what you do is you
start with the first
member of the array and you go through
and you see if it's the if it's the
smallest
and if it's not you replace the value
with whatever the smallest is
at the end of that run you know that the
zeroth element of your array will be
that value then you take like
one to the end and then you go through
and you iterate
you do that process of like finding the
smallest so we need to know how many
have already been sorted
right because we once we found the
smallest we don't want to re-evaluate
that one so i was thinking you could do
that
via i like the way you just said it
actually the way you just said it
implicitly does it
okay so would you be willing to
just talk to chad for a second and not
look at the code editor i'll talk
try not to okay but i think you're going
to want to start with how do you find
the smallest one so
i would just start with that
i won't look at the code as long as you
focus on that first
oh let's see okay um
and you said there's like no booleans in
c sure there are you got booleans
you said no that's one of the first
things you told me which is
terrible yeah no there's there's no
boolean type but um there's boolean
arithmetic so you have all of the
standard boolean operators if and or not
xor all that stuff um all right you talk
to chat
talk to them about okay people are
wearing pants
please all right um okay all right so
i'll talk to chat chat
how's it going i'm not looking at the
code so there's just me
not looking at it can i really quit can
i can in the sort in the sort can i
know the size of it or the length of it
implicitly you can know the
yes don't don't worry but i don't want
you to over complicate this we'll
we can we can modify our code later
well you're going to have to know how
big yeah go talk to chat yeah
you don't even need to pass it in i'm
making life even easier if you just hard
code that it's 5 i'm fine with that
but okay it's fine i don't i just don't
want you to like juggle more variables
than you need to
like i i want that working brain on one
task which is sorting
i've got this you talked to chat okay
i'm talking to chat
okay hi guy focus here nice paul blart
mold cup
okay so they're basically pjs i don't
count them as pants
i'm not going to touch that one no phone
there i go punting again
trick question what is the difference
between these things
okay
this you're gonna get some bad fomo
because i'm just
i'm gonna get to look at all these
things
all right so that's good i like looking
at
last miles screenshots because then i
don't have to like
see the code okay
so this matching nvidia kernel module
loaded
yeah and because the numbers are
different
driver it's being installed for 18 152
versus 450 57. it's not matched colonel
martin
loaded 418 113 yep you got a mismatch
here
and stuff won't work right
i'm going with that i got you last month
both cases that maybe
okay open an iron cat tab i like i like
your thought
i think i've seen not yes not that cat i
always forget what that's called
let's just there we go that's that's
what i'm looking at
that's this is can i move it i can't
even move it
come on
wow you've dying
look at this beautiful bitmap font going
on here i like i like what's happening
here
see did they use a real font
or is it are they actually doing it no
it is silk screen okay with the fall
back to ma
no nice nice mono space fallback i like
what's happening
oh got an error let's diagnose the error
sound managers not to find come on bass
play that funky music i like how this
person comments
but they're doing a dot accessor on
something that's not there
naughty naughty
[Music]
oh this is hand coated it's not minified
look at this wonder oh god
that end come on
come on you're not talking about me
right no okay all right all right you're
fine you're just like here's like oh god
this is terrible oh my
just thinking god now i'll make it
better in a second okay all right
this no
i don't know no nested for loops
okay i'm putting this in a code wtf this
is this is
epic what we just found i think i have a
choice
i have a choice i don't even have some
fancy function maybe i'll do that
code we need a code wtf channel
what am i thinking nope nope oh i want
to talk to myself okay
um can you mute i'll meet myself first i
can i can mute
what no yeah you do it that way you know
when to unmute
okay your message don't upload it
oh come on the code
it's so bad so for those who don't know
i'm putting this
in my discord which i think the bot is
up
i want to say the bot is up the bot is
up
okay so i just added a code wtf channel
but
clearly we're going to have to do a
little work because it's just
just amazing i
i'm amazed
i i i don't know what to say she's
cursing a lot
nice
okay welcome
yeah there's my wave there's my wave
all right so i don't know how much i
should be talking because if she can
hear me it's probably distracting
it's not helpful
are we supposed to asmr this stream
sort the variables
swap in place don't write a bubble sword
that's not a cat this is a cat
that's that's cat i'm gonna have to go
ahead and agree with last miles on that
one
it's running so it's perfect nice paul
vlart
code judgment that's what we're trying
to avoid don't judge the code that's
rude
i know i shouldn't yeah but you code
wtfs they
they're special they they have to be
recorded
what's that crap copy and paste
i don't know what happened in that code
last miles
oh i let's see so can you do a quick
explanation
what they are doing with all i don't
think you want me to explain this cam
because this this is a bit of a
of a diseased i i don't know why they
wrote this
like this this could be totally just
walls
reasons but um i i have to analyze the
whole program to know
oh man i
so the thing is you you never want to be
in this
this is a bad place to be okay like like
you want
an array you know of of some sort
and you want to just i mean look at all
the opportunities you have here for like
misspelling or like who's going to check
this not to mention like i mean
the code smell right off the bat is when
you when you're past like four indents
something bad happened usually you know
and and this is this isn't just a little
past four and then this is
like indent land this this is
this is the pyramid of hell this is
actually it
uh that let's see if somebody has said
this
better than me
so
i i guess that's a little too generic
that's call back hell the pyramid of
doom
this you don't want this see this this
here's your pyramid here
over here on the you don't want you
don't want to build pyramids
pyramids are bad you want to start
breaking stuff up now
it's usually this this is better right
for
indents you're right i do mention this
on regex licensing
so if you come over here and you see the
anti-pattern
i didn't put on anti-patterns if you go
here first rule of advice
going past four indents bad idea
like that's that's a big code smell
right there
ness flow rudi
nes flarudi thank you for the follow i
appreciate it
um what's this channel about uh uh
just general live coding um
king in king lindtine um
it's this general live coding tonight on
uh tuesdays we do
uh uh c as an additional language so
jessie up there is suffering with a
uh her first uh c sort
she's implementing a sorting algorithm
right now
and wow that's a wall of code a wall of
text just happened
i just had a sick and perverted job
contract where someone wanted me to take
code out of an excel spreadsheet and
turn it into an apache web magic thing
thingy wherein they hit a web page and
enter numbers and then
the computation happens in the js front
end
as well oh no she looks like she's
suffering we should we should check on
her
uh okay no she's she's shaking it off
she's okay all right
so we're gonna okay i she might be happy
uh camera went out of focus nope nope
nope
looking good okay so it happens that in
a js front end as well as on the submit
back-end and my sql data
yeah that's back in the day they were
all like that and it was a terrible time
last miles we
try not to remember that time it's
horrific to unzip
excel files into their xml data pack to
get the formulae
which there were many hundreds this is
why i have all the gray hair
nice one last miles i apprec and i very
much love the emotes wonderful
um we watch nine cat and judge some poor
kids
javascript paul blart i am not
judging that harshly here you you want
to see somebody who just like
harsh just harshed somebody's code like
the worst code review
ever this this was just
like top page i think it was like front
page of reddit
um you know what i'm gonna pull it
because it is
it is really something else
i mean just just the url alone tells a
story
i'm gonna i'm gonna get rid of that and
reviewing
the worst piece of code ever that's
this is it so i i am not harshing anyone
like this
i mean this is this this rough i mean
somebody this this site has been knocked
over it was so popular
okay but anyway you could all check it
out
on your own oh no here it is
that's that this is this is like
everyone's favorite line right here
if true smart quotes too
is equal to true return false
i don't even want to know i i don't even
want to know this
this was actually hard to read anyway
um so
going back to channel you're cyber
bullying at this point no
come on paul blart now there's been some
wildly better code reviews on slashdot
back in the day
slash that's still live and i have 20
year old account if i could recall the
password i still have my slash okay
i plan on writing code like that in my
college class that's cool
wow that is a low numbered slash dot id
hey what's up gene how you doing
jiggity jane showed up um
paul blart by the way i i really don't
generally
care i mean so code quality to me
matters a lot more
when you're working in a team like if
you're just sort of hacking stuff
together like i mean
whatever you know i i really don't care
but like
when you're trying to write stuff like
part of what i was throwing in an advice
is not to be harsh
it's like just a few quick rules that'll
keep you from the dark side like i've
seen some stuff
and this one came about because i was
working on a piece of code
that they had actually gone so far
over that they ran out of space in a
132 column id and they went back
they just dropped the indent all the way
back and went all the way over so it was
actually
like 260 like it was
massive level of indent now
i have to say that that is
not that's bad like you're going past
like for so like a good rule is like you
know i try to keep my functions to like
a page and
i try to keep my indents to like
four but i mean you know like code that
works okay we've let jesse suffer long
enough so jesse
we're gonna have to tune back in we're
gonna we're gonna have to help
that amateur has got to go with the
ultra wide monitor
the ronin i'm on a ultra wide right now
no i haven't wait
no no you don't don't sell torture
yourself source we're
allowed to do this together it's a
pair coding you're muted i'm i'm
shutting up okay she's telling me to
shut up
almost all the linux kernel and openness
only apache http has
max index yeah it last mile that's a
good
practice because i feel like it's not
that i'm such a stickler for like a care
i care that the code is almost
definitely full of errors at that point
because
you're just sort of like you're hurting
human the stuff that i hate the most in
code is the stuff that hurts human
reasoning
like you want code to be readable by
people and i understand that sometimes
you're writing stuff
rushing you're in a hack day you're on a
terrible deadline you're just trying to
get something to work
i get all that and i'm very forgiving to
people about that in code
reviews you know i'll i'll even say to
them like if it's something like really
egregious i'm like just throw it to do
one oh
she's looking happy i got it i think
she's looking happy
i also have to use the bathroom so i'll
be right back okay you go dude you look
at that and it's probably terrible but
it works
so first steps yes and
the last miles that's completely how i
feel about it and that's
it's not about shaming to me it's it's
about like just
just write code saying like because if
you're hurting
everyone's reasoning you're probably
getting it wrong too you're
like it anyway
also it depends on if you're just of
course they say like there's not
there's no permanent there's no more
permanent code than something that's
written as a quick fix
temporary hack are we going to unit test
or code with different set of input yes
nathaniel i think we are um uh
let's see so it isn't every man for
himself no
no cam okay i'm hanging on here having a
pending reboot and another beer yep
this is a good time to get that reboot
out of the way
okay she's getting mad at the yeah i
that i i think there was some great
stuff on the video there
she's almost there you can see it you
can see it nice
okay sorry if i missed some stuff there
in chat uh
history actually last miles
yeah when i i saw that line of codes
like whoa
that's okay
the funny thing was i saw that post and
then i saw the other post i don't know
if you've all seen the meme like
somebody said like um another
i think it was on reddit i got it from a
friend but
they said um
you should it
it was it was something like oh yeah it
was bus factor they were i don't know if
you've heard about bus factor in
software you
actually the experience of you probably
all have heard it but bus factor is like
you know like
if people get hit by a bus like could
you maintain the code base and all that
and so
he he this this guy was attacking that
myth and
he just comes out and says like you know
it's not bus factory you have to worry
about it's netflix
hiring your engineer from under you that
you have to worry about and my first
reaction when i read the article i was
like
do you think we have standards so low
that we just hire anybody
because i had just seen like the
terrible code from that other post
like back to back i'm like you don't
have to all right
anyway hi so this is definitely like
brute force method so i'm not trying to
claim that okay like
that's i just wanted to get it working
that doesn't look like brute force brute
force you would actually write every
single line
like if this one's less than this one
i mean it's kind of like i'm sure
there's more elegant ways of doing it
but like
my first pass whenever i'm writing
something is just get it working and
then i can like that's good
pretty yeah that's good so um okay so
walk me through what are what are we
seeing so it looks like they're sorted
on the left
okay so what i was thinking is that
really what you're talking about
and i'm sure there's better ways to do
it but the way that i was thinking is
when you describe verbally how this sort
works
you actually have two things that you're
looping you have
overall like what what particular ind
index of the array that you're
considering so in the first
pass right we consider the zeroth
element and we want to compare
and then you consider the first element
and then you want to compare
well even in the way that i'm saying it
like element and then
the and then part is the second loop and
so
you pick the first loop just goes
through and selects what item you're
going to be comparing
and the second loop is the one that goes
through and does the compare
okay so in this sort bonk
so that's how you're holding the list of
what's already sorted
yes okay so this is the the first sort
that we talked about not the second one
okay the comparison sort not the
insertion yeah this is the selection
sort no they're both comparisons right
but that that was okay
selection whatever yeah selection you're
selecting
the smallest one yes um
so
all right so where was i right so that
creates whatever element is going to be
compared
that's the first loop so that's the loop
that starts on line 11.
that's just gonna go through every
single member
of this of this array or of this list
and
select basically the next one the one
that we're going to compare
and the next loop which starts on line
15
goes through starting at whatever
element
you've picked so actually to speed this
up
hold on well yeah you don't don't
prematurely optimize it's better to be
ready no okay all right all right
we'll leave it we'll leave it leave it
don't worry about speeding it up yeah
just walk me through it
because i think there's like a like an
extra loop in there that we could cut
but anyway so
it starts at what i want to okay no
i'm focused all right so there probably
should be two loops by the way for this
so
don't okay don't over optimize it i
think
this should start at start plus one not
start
because it self checks for the first one
yeah so that was just
okay a little that that was all so it
was me being
but um so talk me through it so the
first one
the second loop once we've already
selected our picks the first one
yes and then it starts chooses at the
next one
then it starts it it's going to go
through all of these n plus one
okay and then it goes through each of
them comparing it to n
and if it's less it swaps them wait a
minute you just you had it
at star okay so you want to use okay so
you want
bonk is going to be smallest in this
case
ideally that's the that's the goal is to
get bunk to be smallest
okay yes yes okay and so we go through
and you start at the next one right
after bonk and
you iterate through this list or array
or whatever up to the end
okay and if you find an element that is
less
so it's smaller than bonk you create a
placeholder
that is that um yeah that is the value
of that thing and then you just swap
them
now by the way it doesn't really
allocate this every time right you're
just using a convenience syntax right
this is really
this could be it's just on the stack so
like
yeah you you could put this like
up here right yeah
because it's really just one piece of
memory but you're
you're not worried about that you you
scope it to here so that way that's
gonna take more time to like
no no actually the compiler is gonna the
compiler is actually going to unroll it
to be equivalent
but okay it's only going to take one
chunk of memory but the nice thing is
that
putting it in here it doesn't allocate
it every time you loop
every time you hit this if but it does
only
meets the criteria it scopes it to just
this
piece so i can't refer to placeholder
outside so it's really just being used
for the swap operation and what you do
for the swap is you take
funk and you chuck it in placeholder
then you take bonk and you give it what
was in array and then you take array and
you give it what was in placeholder so
you end up effectively swapping the two
and that way you end up with the smaller
one is now back in bunk so bonk is
always holding the smallest one
and then we say here
array start is is so
because all right how to put this so
if you if you imagine that for the list
i wish i could draw on the drawing pad
um if you imagine that our list
right 11 5 12 21 17. if instead
we have 5 11 uh and we're dealing with
12 21 17. so we've already sorted five
and 11.
or let's say we've already sorted five
and we're working with 11.
so the reason why you need to change
array start to bonk is because you're
going to take 11 right you're going to
assume you make the assumption
right and that happens in line 13 you
make the assumption
that this is the smallest element
then you go through and you check and
you might replace it with the smallest
element but because you're doing that
swap that becomes the new
min right like that sort of throwing it
out index
you're disregarding what is there yeah
okay yeah
but we've already swapped but you're
remembering to put it back at the end so
that's okay
exactly okay and when we printed out
it looked good or bad it looked good
okay so i'm gonna just modify your code
a little bit i'm just going to add in
the original the original so that we see
it beforehand and we see it after
and just because we're we're nice people
we're going to throw an extra new line
there
at the end so that they separate
themselves out in the output
okay so if we execute that we see that
we fed it
11 5 12 21 17 which is what we said
and we got back out 5 11 12 17 21.
so it worked for our list of five
numbers therefore it's totally perfect
and we're going to ship it as paul blart
maldcox said there couldn't be anything
wrong with this
algorithm correct oh no i mean i it's
probably plenty of things wrong well it
looks right for our one test case so
therefore it must be perfect right
oh god well that sounds like some logic
i'm having to deal with in
other arenas of my nathaniel you're
you're correct there are some extra
swaps there i'm not are there okay
don't that i'm not worried about that
that is
uh in our case swaps these are
effectively going to be registers so
like any sort of optimizing compiler is
going to probably throw that out
um if swapping is expensive then we care
more
okay but that's okay now
um so let's let's see what happens if we
change the input
okay so let's start off by adding a few
more things
so i don't know 23 and
14 and 297
because we're just about to hit 300
viewers
300 followers but actually we're not
allowed to do that because there's a you
win date so we're going to stay below
that so let's just do like 207
and there's five of these and then
there's 10 of those
and what other numbers are on my screen
does somebody have a number in their
screen name
can we see i'm not seeing any numbers
okay you're all right we have pure name
people you just you have three
that's how old hubble is three okay
let's get a three in there oh 42 should
be in there because
thank you that just should be this
reason okay now before we go too crazy
how many of these are we adding that's
four
four four so we're going to say that
there's 12 of these right
does it match your math
yeah 12. okay so let's change that to
12. let's change
len bonk that you set here to 12. um
and let's we're passing in len box so we
should be all right right
okay so now you'll notice we have one
equality in here so is that going to
spell doom
i don't know probably i didn't write
anything to handle that don't worry
about it
okay so we run this thing and it didn't
crash that's a good sign
that's of course i told you in c you're
lucky when it crashes
ah it's sorted did it soar
look at that yes it did uh-huh yeah it
did
it sorted it that that looks good now
what if we so there you go what if we
have something that we worried about our
last terminal value what if this was an
11
and this was a 42. let's just check that
real quick
and we're going to clear this and that
that
oh okay okay
it's looking good it's looking good
there you go
all right by the way last miles thank
you for the sub
uh you now get a subscriber badge when
you
write something because i finally
updated these things
i'm back with fresh mod and toasty warm
mozilla and a cold belgian
leffe oh i like lafayette's a nice one
beer and even wearing pants the nicey
sword
yay she won she's netflix right she
might be netflix ready that
that unlike the earlier story it kind of
not in c i i feel very confident in
python probably why don't i have a badge
sorry loaf bone you gotta be a
subscriber right
they're subscriber badges ship it
ship it excellent it says it says two
month subscribers so he's got like this
first thing next to his name
so maybe that's why founder oh yeah i've
never
yeah he actually is the first he was the
first subscriber period so he gets a
badge that no one's ever gonna get
oh there you go you will have some
access to a few
cool emotes when they finally get
approved so
you are the foundation sub i appreciate
that last miles heck
yes and by the way king lin-tin
thank you for the follow as well and
that's there's some happiness going on
somebody
does have some emotes okay that was
twitch because it's pride but
yeah cheers cheers is later okay all
right yes i'm focused
so i recognize that like like i said
if if this were me coding
for something that was not where people
were watching
that would be first pass and then i kind
of iterate on it and make it better and
catch
things and whatnot and i go through it
so like this was definitely like the
rough
draft this is this is better than a
rough draft it's correct
and actually you should always aim for
correct first do not prematurely
optimize
premature optimization is the root of
all evil remember canoes
i definitely don't do that so that that
oh it's got to work first before i start
of course you don't you're programming
python
um technically speaking my first
programming language i think is matlab
okay my high school was the only high
school in the country at the time that
taught matlab matlab is an expensive
site license so i like your
high school it was a bunch of rich
snooty private school kids and then
scholarship kids woohoo
so all right well this is looking pretty
good
um we could torture your algorithm a
little bit and give it some pathological
cases like
what if the length was one okay
uh i don't want to find out what's going
to happen so like you know you could
check all of the
bounds cases and you'd be fine the other
some of the other sorts that we we could
talk about is like what happens if all
of these things are already sorted
and you know it was already in order
does it leave it undisturbed
is it faster or slower um and uh
is it if it's in reverse order same time
that it would be
almost useful to have like an is sorted
function if we were to write that and it
would check
and so that could be really useful just
as a check in the beginning so you could
write
even run you could like that that failed
initial check we got we got a timeline
now we got we got stuff to get through
i'm just saying i was having enough
trouble getting you to write the sword
and look at that you knocked it out no
problem
no magic happens so i seriously
the magic happens if i take off my
headphones i mute myself so i can talk
to myself like a total weirdo yeah you
don't need to hear me talking to you
i get my my awesome headphones that are
noise cancelling and i blast obnoxious
music
then it's like i'm the best coder ever
it's amazing good work
like well before before we go saying
that before we go see the best code or
ever no no no no
i was being facetious um it is amazing
how much music does help
it is good to get a sort right it does
it does it feels good doesn't it
doesn't feel it doesn't feel all right
it feels good to get anything right you
went from algorithm to implementation
right there
beautiful well you know what if i write
c code and it works i feel great
i'm going to give you a choice so this
is this is your decision point
um okay you're we probably don't have
enough time to do
both so would you like to take a crack
at insertion sort and implement it
or would you like to take a look at
quicksort which is going to be a library
routine which we're not going to
implement
and take a look at some of the other
stuff talk a little bit about
algorithmic complexity in the other
topics
um probably so conceptually i know we're
still working through like
how i can work on stuff on my own time
um
but i would love to learn more of the
the latter
because i agree and i would say that
like the other stuff is probably better
as like homework than it is as like
because i think i think once you got the
idea behind a key sort any of them
bubble sword selection sort and search
and sort
it's just a matter of kind of getting
the code right which is a good exercise
but it's not necessarily something we
need to do
like now i think you'll get more out of
if we talk about the other stuff so
let's let's let's do that okay
um so unlike last miles who's really
raring to go on q sort and i'm
not willing to torture you that much
like i said i've spent all day with like
q values and stuff like that
so q sword just oh i'm like no no more
cues
no no more cues okay now they're also
mentioning some
oh notation in there yes i'm going to
guess that you haven't
probably oh no much of this yes no wait
have or have not have i'm going to guess
you have not
so i am familiar with
like i i know what it means and i know
when
especially so i i've had a lot of work
projects on big data
and so you know uh your your
big o notation or however you want to
say it becomes really important in terms
of
your run time and so yeah it is it's all
about the concept
we're gonna talk briefly about that but
um i am gonna say that before
uh he runs cam is working on the ben
eater
build a 6502 computer from scratch they
have it
ben eater has a breadboard kit that you
can get and uh he's been
doing a little bit of hardware and
assembly which i think is also kind of a
fun
um tacos sound awesome also so and tacos
of course
sounds enjoyable so that's his e-prom
and that's kind of what he's doing over
there
um so who is also computers oh that's
interesting last miles uh thank you for
the cheer as well i think
you really gotta cheer enceladosaurus
for that one i feel like she
she nailed it okay so let's talk a
little bit about
run time yeah ben eater i just recently
cam mentioned ben eater and i
just recently resaw when cam mentioned
with the 6502k
6502 by the way is a processor it's
really cool it's
old school it runs in it was very
popular it's from moss
which was a anyway getting getting far
far feel that this is really a
discussion topic
if we want to get into the 6502 and why
it's so cool
um so i'll just drop that on as a just
in case
okay actually we have a lot of
discussion topics so we need to just
move right along
okay um so but i do appreciate that
thank you so for the big o stuff i feel
very good about that
so okay well then i'm not going to go
into too much detail but basically
uh the the gist of it is like how many
comparisons did you have to make in
order to sort an array of a given size
so if the array is like n entries
like how many times did you have to look
at every key in order to be able to get
it right
and it's it's order of magnitude so
we're not
specifically worried about whatever
coefficient might be in front of it you
know it's going to be some coefficient
times
n we're really worried about what sort
of power it is
and that's we're not worried about this
thing
so we that's the super short version of
that we're going to get into that more
in the algorithms class
so we'll we'll do that if we go on
to data structures and algorithms okay
so
i'm not going to get too specific but
these sorts that you're studying right
now these basic sorts they're all
n squared algorithms so this is big o of
n squared
this is important because it means that
for a list of size n you could look at
n times n entries in order to be able to
get it into order
and in reality it's always gonna be a
little bit worse because it's however
many swaps and other stuff that you're
doing in there which is
part of why nathaniel was worried about
it up front but um order magnitude
of this when it's sort of optimally
implemented is
n squared so both selection
that we just mentioned that you just
implemented
insertion and bubble sort incidentally
are all in this class so
these are all n squared and by the way i
forgot to cut over to the whiteboard so
i'm going to do that
so these are all n times n or n squared
algorithms
now you should really there's no excuse
ever for you to use this in production
code because
there are better versions of comparison
sorts and some of the best ones are
approximately
n log n so
they're a little this login is obviously
going to be less than
a full n because it's the log of n so
this would be a more optimal version of
it um so
n log n is you know less than n squared
so we you should really never be using
one of these
outside of like you're just focusing on
learning about sorting and stuff like
that
but so don't ever use an n squared
algorithm there's always
a n log n algorithm and the one
exception of that which i will allow
is the quick sort and the the quick sort
is a little bit
funny because it's a very popular
sorting algorithm
um and it involves partitioning the
space
so basically what you do is you take you
take the stuff
you split it some arbitrary place it
doesn't really matter where you went
that's called the pivot
i'm not explaining this very well
because i don't really want you to
implement it
all you really need to know is that it
starts with the word quick
okay which is important so we pick an
arbitrary i should
you know just to just to make this clear
you can pick an arbitrary pivot pivot
does not need to be in the middle it's
not a buy section
um so wherever you happen to pick the
pivot you compare all of the entries to
the pivot
and well actually usually you start with
a sublet
there's there's different spins on how
you do this but you're kind of like
saying okay are things
is is each entry bigger or smaller than
the pivot does it go on
the left side or does it go on the right
side and we're going to
kind of put them in the right place and
then what we do is we sort of keep
subdividing our list so
you can you can say okay this list now
we're going to kind of like pivot that
and you know anyway i'm doing the really
hand
wavy version of the quicksort in reality
the pivot you generally choose is
typically the first one that suffers
from
uh worst case n squared if you give it
what's called pathological input
so if you hand it a already sorted list
then it'll always pick the worst pivot
and and bad stuff happens and
nice i will give you a directory listing
last miles if
if you want one in here um also also
yes can i tell you how many freaking
times in like
work slack awkward like group chats that
maybe that that isn't the best place
i've
i've done like ls or whatever it was i
was meaning to type in the terminal and
then you click it and you just feel like
a complete
even better is when you type this
command the who am i command
because you're say checking which user
you're logged in to be doing
something and then that's really awkward
in the modern era
you know you're just like who am i you
know people like i'm not gonna get into
that guy
you know that's just that that's a
question you're gonna need to answer
how how awkward and sort of like i don't
know newbie-ish i feel
with with c similarly i've had to
um my development environment for one
project requires windows
and i literally pulled up the
command prompt or whatever it's called
and
i have never felt more incompetent in my
life
i've been on unix for so many years at
this point that i was just like so many
astrophysics software require unix
and so i pulled it up and i was just
like ls it was like
nope what's that and i literally was i
just
all you know confidence and and and self
awesomeness sort of drained away slowly
that's okay because you know what i'm
learning c and similarly i
unfortunately am this is from a group of
people that flipped the
front slash to being a backslash just to
be different just to be jerks
because that's really annoying it was it
was and it was done on purpose anyway so
we're not going to get into that
and okay let's add that to the drinking
time if we if we want to open the
haterade on
on das then i'm i'm all for that but
that is like we can open the haterade on
windows
we can open the haterade on that so
let's do that okay
anyway yes quick sort hand wavy okay so
quick sort we're doing a real big hand
wave
so i guess i guess the right way to do
that is we're just gonna
and i'm gonna give you a few wave things
all right so that's that's the hand wave
that's the big hand wave okay
um okay we're gonna we're gonna get rid
of that because it really looks like i'm
flipping you off okay so
um anyway we're back to quick sorting
and this is
sort of a very useful algorithm it's not
the
important thing and i'm sort of hand
waving this the runtime is
generally o of n log n in its average
case
it depends on the input in its worst
case it's an n squared algorithm so
it in its worst case and you really same
as the other ones
you have to rig the input to do it but
in its worst case it actually is an n
squared so this is sort of a trick
question that shows up on
interviews sometimes like oh well what's
the run time of of quicksort well it
turns out
a lot for a lot of them there's best
case worst case yeah well that's what
yeah i mean like versus like the
algorithms that you were doing which
basically
they're going to be n squared every time
like pretty much guaranteed but
like this this one typically is n log n
and that's pretty good
for a lot of data sets now you have a
few other options
um you can have an algorithm that's
guaranteed to be
n login okay and
part of the problem with it there isn't
like a great one because
typically you have to throw away n
squared memory
so you know you you can have cpu
as n log n and you can have n squared
memory and this this okay or you can
you know there's typically a trade that
you're gonna make somewhere
there's no perfect one-size-fits-all
sorting algorithm
tim sort that nathaniel has mentioned is
actually
pretty damn good um if you don't know
what the input is gonna be if you don't
know what you're going to be
sorting and all that other stuff this is
one of the best ones out there and
that's why it's built into
things like python and other languages
but um
so when you're actually typing sort
you're you're getting this
under the hood um and this
a lot of these algorithms they sort of
fall they're hybrids you know so they
they involve a bit more set up so like
you might have something that like
you know it'll do something like merge
sort and i'm gonna type that better so
there's there's merge sort which is
really easy to describe i'm really
getting this is the algorithms class
that's why i'm
sort of hand waving a lot of this stuff
but um merge sword is sort of like a
process of like if i subscribe and
follow for more classes
yeah yeah we'll be doing that in the no
not like we really want to know what's
going on you're really right yeah let's
see i'm totally selling this wrong you
are absolutely if you want to know
out there yeah i mean i want to know
everything then you're going to want to
show up for
level two okay no but um a really fast
version of it for merge sort is you
basically just cut it in half
and you sort each of the pieces
okay and then you cut that in half
and you sort each of the pieces
and sooner or later if you do this
enough times
you're gonna end up in a pathological
merge sort which is almost never
implemented that way
then you're gonna end up with entry size
of one
and we know that entry size of one is
trivially sorted
so if i if i split this enough times and
by the way you have to deal with like
odd cases like this is why you never
want to whiteboard something like this
because because like what happens if
there's like an odd number of interests
don't look behind me then
don't don't look at it well it's not a
sort but like don't don't look at the
grossness that's on my whiteboard right
now
okay so basically um and then what you
can do is you can sort of like
keep combining them back up so first you
split them down
you sort each of the pieces and then you
sort to you merge
them back together and you sort the
merge and then you can sort the merge
and sort the merge and sort the merge
and then you can bring those up to the
next level
and basically if you just kind of like
go back up and keep sorting the pieces
you'll eventually end up with one sorted
algorithm this is really nice because
it's n log n
guaranteed now it's also
a hot mess in memory so
recursion usually is it depends like you
know how much your stack
how big your stack is or your stack
anyway um so
far afield moral of the story one way we
can compare these things is to know
about their big o notation
which we're hand waving a little bit in
this class but
there's no excuse to be using an
n-squared algorithm generally unless
it's the worst case and i'll give you a
bio
on quick sort um but never implement
quicksort and why should you never
implement quicksort because guess what's
built into the c library
not quicksort this wonderful function
that we're going to use right now oh you
mean like don't build it yourself
don't build it yourself because it's
literally built right there
and it's totally correct
oh yeah if we go we look at the man page
for this which we can pull up the manual
page
um i guess i'll just do it on a web page
so the cue sort man page
what what section is that section three
of the manual
and another look on my local um yep
section three
uh so you get this
basically and i'm gonna just drop this
in the channel so that everyone can do
this
um you get this basically for free
uh if you just use it
so it is one of those things that we're
gonna just
use it so um if we if we look at these
calling parameters and of course we have
all this
nonsense stuff going on but uh
if we look up here at our calling
parameters
then i guess you know what i can do i
don't need to
live in this world i can just i can just
show my terminal
because it's built in
so um yeah if if you just look at the
cue sort man page then
um you'll see that you need to pull in
standard lib
so you got to make sure that that's
there and then this is going to take a
couple entries it's going to say
a base so this is basically your array
that you're going to be sorting
it's going to take how many members are
there
you know so that's how big is your array
just like you were or
yeah just like you were passing around
what is the size of each entry so it
doesn't really care if it's an int or a
float or a
long or a care or whatever all you need
to do is tell it how big each one is
okay and then the one messy parameter
which is a function pointer and i know
how much you love
function pointers but you do need to
pass in a function pointer because this
is exactly what i was talking about
before when i said
the sorting algorithm itself does not
care about your collation
so uh you get to specify
your own function to compare things with
this and the
rules of this function are described
down below they basically yeah they say
here the comparison function
um third paragraph um is
basically saying that you have to return
less than
equal to or greater than zero
when the first argument you're going to
be past two arguments and when the first
one's smaller than the
second one you return less than zero
when it's equal you return
zero and when it's greater than you
return something that's bigger than zero
so that's all your function needs to do
so to get this to work
you just need to build a function that
you can pass as a parameter
so that we can send it into this thing
and we need to just
specify very trivially that i mean
if it's if parameter one is less than
parameter two we've returned less than
zero and
so on so forth okay so let's write that
first do you want to
use this or is it good enough that you
just saw the manual page
i think i got got it from the manual
okay
so i can tell you that basically
whatever your
length of implementation of this
function pointer is
and i know we probably need a little bit
of practice with these
this is a
this this is most of your implementation
because this is going to be one line
and by the way i'm accidentally pointing
out the q sort actually i'm not pointing
it out at all because i'm
on the different scene but this that
there's two functions here there's q
sort and there's q sort r r standing for
re-entrance so don't worry about the
re-entrant version that gets into
threading and other stuff we haven't
talked about yet
but the top one is the one that you're
going to be worried about
um and that basically you just need to
pass in what the array of stuff to sort
how big is the entire how many entries
are there on the array how big is each
entry and how do i compare the two
and if i pass those things in on one
line i get back magically a sorted array
it's not returned to me because that
would be a stack copy so we don't want
to do that
instead it just operates on base
directly so it'll just
in place put them into the right order
so like i said
never implement this for real like so in
real code
in real actual code never implement a
sorting algorithm if you need to use q
sort you've always
got it if you want some of the other
stuff they're available in libraries
sometimes they're there sometimes
they're not never implement one
never implement one unless you're just
learning how the algorithm works which
is totally fine
gotcha okay getting off the soapbox so
that
is q sort um the one other thing that
i'm going to mention to you
is knuth so we've talked about knuth i
don't know if you've ever seen knuth
knuth the art of computer programming
this is basically this is it right here
this is knuth
this is the book on searching sorting
hashing and all these kind of algorithms
it's it's typically i think it's three
or four volumes i don't know
how big it is oh he's planned more okay
so anyway knuth is just referred to
as knuth like this is like i don't know
grey's anatomy this is gray
this knuth is knut so canoes says this
is the right
implementation you know he used to write
it in mix i don't know i haven't seen an
updated copy of
canoe so mix is this archaic
sort of assembly language but it's it's
really simple to understand and you can
always see like what's happening in
terms of like raw memory and stuff like
that
okay so oh and sorry i missed um
kinglyn tines question earlier how
important is computation structures
and computer systems engineering for
software engineering i would say it's
very important
but i think the place where most people
get tortured with it is whiteboard
interviews
um just which is naughty uh
are we at the drinking portion yeah we
are totally i think at the time
let me just let me just check the notes
whiteboard interviews just give me that
yeah that's that's a topic pavlovian
response we're gonna talk about that
um let's see okay so algorithm choices
so we can always trade size space
whatever
uh knuth we look it up if we have to we
use a library
because using libraries is better than
torturing yourself and implementing
these things
i will drop in the chat there's a really
nice comparison of sorting algorithms
from the wikipedia
there's some nice visual things you can
see the sorts like happening visually
with sticks which is kind of cool
and there's some websites i actually
found one which
i don't have here but i had a really
nice
website that that could compare them
really visually and very quickly and it
was kind of nice
i'll have to dig it up anyway um there
is one last thing which is to say that
as fast as you can get with a comparison
sort
is n log n but
there are non-comparison sorts yes
so if you're willing to sacrifice insane
amounts of memory
you can kind of misuse a hack a hash
function you can use a radix sort
and you could basically just read each
entry once and put it into the right
spot in memory and that's it
like that's it's just
takes a disgusting amount of memory so
if you don't care
there are faster than n log login i mean
it's the trade-off that happens with
pretty much i feel like
everything yeah which is speed memory
like you're going to be sacrificing
something so
and that's great news cam i'm glad you
found the 74 the ttl logic to be able to
do
your eeprom programmer okay
so with that said do you have any
questions
nope that's