Programming BASIC and Sorting - Computerphile
Summary
TLDRThis script explores the auditory and visual representation of sorting algorithms, focusing on the BBC Micro's A5000 computer. It discusses the use of BBC Basic to create a program that visually and audibly sorts elements, playing sounds to represent the values during the sorting process. The script compares various sorting algorithms like Bubble Sort, Quick Sort, and Heap Sort, demonstrating their efficiency and differences. It also touches on the use of libraries and the challenges of implementing certain algorithms due to outdated dependencies.
Takeaways
- 🔊 The script describes a sorting algorithm visualization where elements are swapped with accompanying sounds to represent their values.
- 📈 It was suggested to sort 100 elements side by side to visually compare different sorting algorithms.
- 💻 The BBC Micro and its descendant, the A5000, are discussed as early computers that introduced people to programming with BASIC.
- 🎵 The Acorn A5000 computer is highlighted for its built-in BBC BASIC interpreter and its ability to quickly boot into a GUI with an icon bar and hard drive.
- 👀 A program written in C++ for visualizing sorting algorithms was mentioned, which inspired the speaker to create their own implementation.
- 🛠️ The speaker discusses the use of libraries in programming, which are collections of code that perform specific tasks, often used for reliability.
- 📚 Reference is made to a book titled 'Games for your BBC Micro' which provided insights on how to use sound in programming.
- 🔢 A demonstration of the 'Doctor Audio' game from the book is given, explaining how sound is used to provide feedback based on the proximity of a guess to a number.
- 📉 The script covers various sorting algorithms, including Bubble Sort, Quick Sort, Selection Sort, and Heapsort, noting their complexities and performance.
- ⏱️ Performance metrics such as time taken, number of comparisons, and swaps are highlighted as important factors in evaluating sorting algorithms.
- 📊 A visual comparison of sorting algorithms is conducted with 100 elements to demonstrate the differences in speed and efficiency.
Q & A
What is the purpose of the sound played when swapping elements in a sorting algorithm?
-The sound is played to provide an auditory cue that a swap has occurred, with the pitch of the sound indicating the values of the elements being swapped.
Why was the BBC Micro commissioned and by whom?
-The BBC Micro was commissioned by the BBC to introduce people to computers and programming as part of their educational project.
What is the significance of the ARM chip in the Acorn A5000?
-The ARM chip is significant as it was a feature not present in the original BBC Micro, indicating an advancement in technology and performance.
What is the difference between the BBC Micro and the Acorn A5000 in terms of boot-up time?
-The Acorn A5000 boots up more quickly than the BBC Micro because its operating system is stored in ROM, allowing for a faster start-up process.
What is the role of the 'Icon Bar' in the Acorn A5000's GUI?
-The Icon Bar in the Acorn A5000's GUI provides quick access to various applications and system functions, similar to taskbars in modern operating systems.
How does the 'Doctor Audio' game provide feedback on the player's guess?
-In 'Doctor Audio', feedback is given as a tone, with the pitch of the note varying according to how close the player's guess is to the computer's number.
What is the role of the 'rem' command in BBC Basic?
-The 'rem' command in BBC Basic is used to insert comments or reminders in the code, which are ignored during execution.
What is the time complexity of Bubble Sort and why is it considered inefficient for large datasets?
-Bubble Sort has a time complexity of O(n^2), making it inefficient for large datasets because the number of comparisons and swaps grows quadratically with the size of the input.
How does Quick Sort differ from Bubble Sort in terms of efficiency?
-Quick Sort has a time complexity of O(n log n), making it significantly faster than Bubble Sort for larger datasets due to its divide-and-conquer approach.
What is the concept of a 'heap' in the context of Heap Sort?
-A 'heap' in Heap Sort is a specialized tree-based data structure where every parent node is larger than its children, allowing for efficient extraction of the largest element.
How does the Selection Sort algorithm find the smallest element in an unsorted list?
-Selection Sort works by repeatedly scanning the unsorted section of the list to find the smallest element and then swapping it with the first unsorted element, moving the boundary of the sorted and unsorted sections each time.
Outlines
🔍 Interactive Sound Visualization in Sorting Algorithms
This paragraph discusses an interactive program that uses sound to represent the process of sorting algorithms. When elements are swapped, the program plays a sound, allowing users to hear fluctuating pitches that correspond to the values being sorted. The creator of the video script reflects on previous videos about sorting algorithms and mentions the BBC Micro, a computer designed to introduce people to programming. The script also touches on the use of BBC Basic, an interpreter built into the Acorn A5000 computer, which is used to demonstrate the sorting process visually and audibly. The video script includes the source code for a program that generates random colors and sounds, and discusses the limitations of using certain libraries for programming.
🎮 Implementing Audio Feedback in Sorting Algorithms
The script describes a game called 'Doctor Audio,' which is a variation of 'Dr. Watson,' using tones to provide feedback on the user's guess of a number. The tone's pitch varies based on the proximity of the guess to the correct number, with the sound parameters explained in detail. The paragraph also covers the process of transferring data from a book to a computer, which involves typing in the code manually. The speaker then transitions to discussing the implementation of visual sorting programs, starting with bubble sort, which is demonstrated with 30 elements. The script provides specific details on the time taken, comparisons, and swaps for bubble sort, and how these metrics change when the number of elements is increased to 60.
📉 Comparing Sorting Algorithms and Their Performance
This paragraph compares different sorting algorithms, including bubble sort, quick sort, selection sort, and heapsort. It explains that bubble sort and selection sort are slow due to their time complexity of n squared, while quick sort and heapsort are more efficient with a time complexity of n log n. The script provides a visual demonstration of quick sort, showing how it partitions the list and sorts it more quickly than bubble sort. Selection sort is also discussed, with its process of finding the smallest element in the unsorted list and placing it in the sorted list. The paragraph concludes with a brief introduction to heapsort, explaining the concept of a heap and how it is used in the sorting algorithm, followed by a demonstration of heapsort sorting 100 elements.
Mindmap
Keywords
💡Sorting Algorithm
💡Bubble Sort
💡Quick Sort
💡Heap Sort
💡BBC Micro
💡Acorn A5000
💡BBC Basic Interpreter
💡Graphical User Interface (GUI)
💡Sound Synthesis
💡Data Structure
💡Computer Programming
Highlights
The transcript describes a unique auditory and visual approach to demonstrating sorting algorithms, with sounds representing the elements being swapped.
Acorn's BBC Micro and its successor, the A5000, are discussed, highlighting the evolution of computing and programming interfaces.
BBC Basic interpreter is mentioned, illustrating the continuity of programming languages and their influence on modern systems.
The operating system's quick boot-up time due to being stored in ROM is noted, emphasizing the efficiency of older computing systems.
A GUI-based interface of the A5000 is contrasted with the BBC Micro, showcasing the shift to more user-friendly computing experiences.
Built-in applications and the concept of 'apps' in the 90s are explored, providing historical context to modern application ecosystems.
The use of libraries in programming is explained, emphasizing the reliance on community-contributed code for efficiency and reliability.
Acorn's BBC Basic is used to create a visual and auditory representation of sorting algorithms, demonstrating creative programming applications.
The transcript details the implementation of a program that visualizes sorting algorithms with sound, offering insight into multi-sensory programming.
Bubble Sort's process and its auditory representation are explained, providing a clear example of how the algorithm works.
The time complexity of Bubble Sort is discussed, with a practical demonstration of its performance on different element counts.
Quick Sort is introduced, with an explanation of its partitioning method and its superior performance over Bubble Sort.
Selection Sort is covered, comparing its time complexity to Bubble Sort and noting its fewer swaps but similar performance.
Heapsort is introduced, explaining its use of a heap data structure and its time complexity of n log n.
A comparison of sorting algorithms is presented, visually and audibly, to demonstrate their efficiency and differences.
The transcript concludes with a discussion on the practical applications of these sorting algorithms and their performance implications.
Transcripts
so each time it swaps a pair of elements
it plays the sound of both of them
you can hear this sort of fluctuating
pitches
each time it compares each pair of
elements it plays a noise and then
potentially swaps them
and what we thought we'd do is make them
all sort 100 elements and you'll see
them side by side
in the last couple of videos we've done
on sorting algorithms there's been quite
a few comments uh on the videos and
requests from people to do
some more on different sorting
algorithms so it's been a couple of
weeks since we did the videos and um
also there's been some more videos on
computer file in particular i saw the
one on the bbc micro so the bbc wanted
to develop a project to introduce people
to computers and programming they
commissioned a british company called
acorn
to make this computer and how easy it is
to use basic to draw things on the
screen and make noises
this is an a5000 which is a computer
made by acorn
which dates from about 1991 i think
so um
it's it's kind of
a descendant of the bbc micro it's it's
got an arm chip
which the bbc micro didn't have because
it's a an acorn it's got um
it's got bbc basic interpreter built
into it there is a bbc basic interpreter
for windows
it's a bit limited in terms of what you
can use for memory and i didn't want to
have to pay for it and i have this
sitting in a corner like the bbc micro
the operating system is in rom so you
turn it on and it's
it's pretty quick to boot up
so
we just wait
and
there we go it's booted up unlike the
bbc micro this boots up into a gui
you've got a mouse and some things to
click on this is called the icon bar at
the bottom here and this is a hard drive
icon so you click on that it opens it
comes with a hard drive in a window that
looks familiar to you probably if you
used any modern operating system this is
the floppy drive here
so you click on that it'll say drive
empty because it is and then we've got
apps which are some built-in
applications and networking and over
here we've got
graphics options and operating system
options so acorn we're talking about
apps back in the 90s well yeah it's just
short applications so if you click on it
you've got some built-in basic things so
you've got an alarm which tells you the
time if you click on configure it brings
up the configuration
so you can change things like sound
options so i can change the noise to be
various different things when i was
looking at sorting algorithms on youtube
i found
another video or another couple of
videos made by someone else who had
written a program in c plus but did
visualization of sorting algorithms
so it would show you an unsorted list
and it would sort it into order each
time it would swap a pair of elements or
do something it would play a certain
pitch depending on the value of that
element well that's quite interesting
but there are some sorting algorithms
that they haven't done that i'd like to
see so i thought i'd do it myself they
posted their source code and it was
using some c plus plus library that i
couldn't get an up-to-date version of on
my system
so a library is just a collection of of
code written by other people that does a
certain task for you so you can just use
that most people use libraries of code
because you can generally be guaranteed
that it does what it's supposed to do
correctly and i thought well having seen
that bbc basic video and the
the triangles program on screen i can
show you you know i did my own
implementation as i was playing the
triangle on screen i also decided to
make it make a noise
so i can show you the source code for
that this is it i'm going to put some
spaces in just make it a little bit
clearer mode 27 tells it what screen
resolution to use and what color is
available that sort of thing okay and
then we've got this repeat until false
block what it does it repeats all this
until false and now false never
evaluated to true so it just repeats it
forever this says set a variable called
color to a random numbers between zero
and seven
this then says set the graphics color to
that random number between zero and
seven
then we play a sound
related to that random number as well so
the numbers between zero and seven we
need to scale it to be in the range zero
to two five five so that's the pitch
value and it
zero is the lowest pitch it doesn't two
five five is the highest pitch it will
do if we left it zero to seven it would
just be very low and they'd all sound
quite similar this line that says plot
actually draws a triangle so that's what
you would have seen in the other video
now this line is here to slow it down
because it goes very fast on this so if
i comment this line out we use rem
which i think stands for reminder so if
i save that and then i run triangles
again
it goes so fast that you can't already
sound because as soon as it starts
playing one sound it's trying to stop
playing the next and you can't hear
anything another thing i used was a book
that
came into my possession i came to the
office called games for your bbc micro
this is just code listings of of certain
games the first one i did was quite
short it's called doctor audio it says
this game is a variation of dr watson in
which when you guess the computer's
number the feedback is given as a tone
the picture of this note varies
according to how far your guess is from
the correct number the sounds are
programmed in line 130. this is where
how i learned how to do sounds because
it said line 130 sound 1 -15 abs a minus
b 5. so it turns out that i had to look
this up because it wasn't in this book
sounds takes one two three four
different
parameters
so the first one is the channel you want
to play on i think channel zero does
percussion sounds or something strange
so anyway the first argument says play
on channel one the second one is the
volume and that has to be between i
think zero and -15 minus 15 is the
loudest zero is the quietest this says
abs a minus b so that subtracts one
number from the other and
um
gets you the absolute value of it
and then the last one is the duration of
the note it's in centi seconds so it's
500th of a second it plays it for here
goes the program they might have rude
words in it i can't remember
something
so i am thinking about between 100 what
is it let's go for
25.
okay it was changed a little bit from
what you said in the book
but ivy wrote it so the higher the pitch
is the closer it is 25 is wrong you
so what's my next guess i'm going
to say um 75.
so 75 sounds closer let's try 80.
no that's further away uh 60
yeah i'm gonna go for
70.
hooray where was the disc then with that
book
where's the disc the disc is
the data is stored on the pages
which means you've got to transfer it
via your hand and the keyboard
so show me what that meant okay so what
i have to do is um type everything in to
a nice text editor
this one's not particularly nice
this is the code that does that program
this is
about 30 lines probably now i kind of
was a little bit more familiar with bbc
basic and how to draw things in certain
colors and how to play sounds i decided
that i could probably implement those
visual sorting programs
so first of all we've got bubble sort i
think this sorts
30 elements
so with bubble sort we compare elements
and keep swapping elements if they're
bigger than the ones we're in front of
until they get to the end so
um
the green elements are ones that are in
the right place red elements are
unsorted and the blue ones are sort of
ones that are being the ones are active
at the moment
so for 30 elements that took
23.38 seconds 384 comparisons and 228
swaps so if we change it to 60 elements
open it in the editor and change maxwell
from 30 to
60.
so say five
okay so now we've got six elements
we've doubled the input size and because
it runs with the square of the input
size
two times two is four so it should take
four times as long with four times the
number of comparisons and four times the
number of swaps each time it does a
comparison and each time it does a swap
it it increments a counter and just
prints it out up here
so each time it swaps a pair of elements
it plays the sound of both of them
you can hear this sort of fluctuating
pitches
each time it compares each pair of
elements it plays a noise and then
potentially swaps them
it's getting
smaller now
we're only sorting say 20 maybe now
what this is showing uh us is each of
these columns which is the same width is
a different number and so that's a low
number and they said you've got a high
number so when we start out the list is
unsorted so you've got sort of also high
and low columns all next to each other
and when we have sorted the list in it
with low numbers like end and high
numbers at that end we also covered
quick sort in our previous videos so
we'll show you that so there's a
variable called number of elements
that's set to a thousand so i'm going to
reduce it to
say uh
400. okay and we've also got another
option here so we can set graphical to
true or false actually what you find is
if you really want to do proper speed
tests you need to turn the graphics off
because they slow it down a lot if you
wanted to prove a point and
do something like this by the way this
graph is linked to from the previous
sorting videos
so let's save that
and then run it so we've got
quick sort
so
here's our list of unsourced elements so
you can see there's also high low ones
hopefully you'll remember from the video
on quick sort the way this works it
partitions the list by picking an
element called pivot and putting all
elements less on it on one side and
greater than on the other side and then
it
it does that again on each sub on each
side so you can see it's kind of it's
done all the left hand side and now it
will start doing the right hand side so
there's the pivot it does all the
left-hand side
picks another pivot it keeps doing that
until it's sorted
[Music]
you can see with quick sort it is a lot
quicker than bubble sort another
algorithm that we didn't cover before if
it is still fairly simple is called
selection sort you go through your list
and you look for the lowest element
that's in the in the unsorted list you
take that and you put it in your sorted
list
you go through the unsorted list pick
the lowest element from there put that
in your sorted list here's 100 elements
being selection sorted
we've got to look through the whole list
find the smallest and then we put it at
the other end
so
is this a quick one this is not
particularly quick this also is n
squared because you've got to look at
you can look at these over and over
again
it's the same time complexity as bubble
sorts although i think it might perform
a little bit better because it does
slightly fewer comparisons
whereas it certainly does fewer swaps
it only needs to do at most
one swap per element in the list whereas
bubbles can go crazy the comparisons are
still quite high and that makes it a
little bit slow
and what we thought we'd do is make them
all sort a hundred elements and um you
can see them side by side and
hopefully uh sped up a bit because some
of them are quite slow
[Music]
[Music]
what we've seen is bubble salt and
cocktail salt and selection saw are
quite slow in comparison to quick sort
um quicksort runs in n log n
as we said in the quick sort video
uh another algorithm that people were
asking about in the comments is heapsort
that also runs an n log n you need quite
a lot of background knowledge to
understand how it works so heapsort uses
something called a heap
now a heap is a type of data structure
which is represented by a binary tree
whereby
every element in the tree
um
has children who are
smaller than it we haven't covered trees
to cover trees we need to probably cover
linked lists to cover
linked lists we need to do something
about data structures and we haven't got
there yet
however i will show you heapsort before
i started what it does it builds a heap
up the largest element is always at zero
and then it swaps that element to
the end and it restructures the heap so
that the largest elements are getting at
that end well let's let's go
so this is building up the heat
now it's built the heat it can keep
taking the largest element and
maintaining the heat structure
[Music]
i'm using a sorted list
[Music]
well that was quite quick that was 100
elements so it's the same as the other
ones we've just seen if you know what
heap is and not it's different from the
heap the heap is um an area of memory as
opposed to the stack
but the heap and a heap not the
and then we say which is lowest between
seven and eight it's seven uh which is
lowest between eight and nothing it's
eight and then similarly ten and nothing
it's ten is the idea that we've got it
in the case of ipv4
関連動画をさらに表示
3 Types of Algorithms Every Programmer Needs to Know
Projeto e Análise de Algoritmos - Aula 10 - Ordenação em tempo linear
Learn Merge Sort in 13 minutes 🔪
Sorting Secret - Computerphile
Sorting - Part 1 | Selection Sort, Bubble Sort, Insertion Sort | Strivers A2Z DSA Course
61. OCR GCSE (J277) 2.1 Insertion sort
5.0 / 5 (0 votes)