Programming BASIC and Sorting - Computerphile

Summary

This 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

00:00

🔍 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.

05:02

🎮 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.

10:02

📉 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.

Keywords

💡Sorting Algorithm

A sorting algorithm is a method for arranging elements in a specific order, typically numerical or alphabetical. In the video, various sorting algorithms are discussed and demonstrated, such as Bubble Sort, Quick Sort, and Heap Sort. These algorithms are essential for organizing data efficiently, and the video provides a visual and auditory representation of how each algorithm processes a list of elements.

💡Bubble Sort

Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted. In the video, Bubble Sort is shown with a visual representation where each swap is accompanied by a sound, illustrating the algorithm's process.

💡Quick Sort

Quick Sort is an efficient sorting algorithm that works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively. The video demonstrates Quick Sort and compares its efficiency to other algorithms, showing how it can quickly organize a large set of elements.

💡Heap Sort

Heap Sort is a comparison-based sorting technique based on a binary heap data structure. It's similar to selection sort where we first find the maximum element and place it at the end. We follow this process for the remaining elements. The video explains Heap Sort and shows how it builds a heap and then repeatedly extracts the maximum element to sort the list, demonstrating its efficiency.

💡BBC Micro

The BBC Micro is a series of microcomputers and associated peripherals designed and sold by the Acorn Computer company in the 1980s, as featured in the video. It was designed for the British Broadcasting Corporation's Computer Literacy Project, aiming to promote computer and programming education. The video discusses the BBC Micro and its descendant, the Acorn A5000, which are used to demonstrate programming concepts.

💡Acorn A5000

The Acorn A5000 is a personal computer that was released in 1991 by Acorn Computers. It is a successor to the BBC Micro and is featured in the video as an example of an older computer system. The A5000 is shown booting up and running BBC Basic, which is used to demonstrate various programming tasks, including the implementation of sorting algorithms.

💡BBC Basic Interpreter

The BBC Basic Interpreter is a programming language interpreter for the BBC Micro and compatible computers, including the Acorn A5000. It allows users to write and execute programs in the BBC Basic language. The video shows how the interpreter is used to implement and visualize sorting algorithms, providing an interactive way to understand their operation.

💡Graphical User Interface (GUI)

A Graphical User Interface (GUI) is a type of user interface that allows users to interact with electronic devices through graphical icons and visual indicators. The video mentions that the Acorn A5000 boots up into a GUI, which is a departure from the text-based interfaces of earlier systems. This GUI includes features like an icon bar and mouse support, making it more user-friendly.

💡Sound Synthesis

Sound synthesis refers to the artificial generation of sound. In the context of the video, sound synthesis is used to create auditory feedback during the sorting process. Each time elements are compared or swapped, a sound is played, with the pitch of the sound corresponding to the value of the elements. This adds an additional layer of interactivity and understanding to the sorting visualization.

💡Data Structure

A data structure is a way of organizing and storing data in a computer so that it can be used efficiently. The video touches on data structures like heaps, which are used in Heap Sort. A heap is a specialized tree-based data structure that satisfies the heap property, where each parent node is either greater than or equal to (in a max heap) or less than or equal to (in a min heap) its children. The video explains how heaps are used in sorting algorithms to improve efficiency.

💡Computer Programming

Computer programming is the process of designing and building an executable computer program to perform a specific task. The video script discusses various aspects of programming, such as implementing sorting algorithms and using the BBC Basic Interpreter. It also touches on the historical context of programming education with the BBC Micro and the Acorn A5000, showcasing the evolution of programming tools and techniques.

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