Sorting Secret - Computerphile

Summary

In this talk, two popular sorting algorithms, Selection Sort and Insertion Sort, are explained through a visual method that reveals their similarity. The presenter uses simple diagrams to show that while these algorithms are often thought of as distinct, they are actually the same when viewed from different perspectives. By breaking down sorting into easy-to-understand steps, the presenter demonstrates how numbers are ordered through basic comparisons, making the complexities of sorting algorithms more accessible. This discovery highlights the importance of viewing problems from new angles to uncover hidden connections.

Takeaways

• 🔄 The script discusses two fundamental sorting algorithms: Selection Sort and Insertion Sort, and reveals a surprising connection between them.
• 🎨 The presenter uses a visual approach to explain sorting, emphasizing that no coding or computer science knowledge is required to understand the concepts.
• 📊 The script introduces a 'sorting box' concept, a simple model for sorting two numbers at a time, which serves as a building block for the sorting algorithms.
• 🔲 The sorting process is visualized as a grid of sorting boxes, where numbers are sorted by passing them through the grid column by column for Selection Sort.
• 📏 The same grid can be viewed differently to represent Insertion Sort, where the sorting is done row by row, inserting each number into its correct position in a sorted sequence.
• 🤔 The script challenges the conventional wisdom that Selection Sort and Insertion Sort are distinct, suggesting they are essentially the same algorithm viewed from different perspectives.
• 👨‍🏫 The presenter, Graham, shares a personal anecdote about discovering this concept while teaching, highlighting the importance of different perspectives in understanding algorithms.
• 🤝 The script includes a dialogue between Graham and Sean, where they discuss the broader implications of this observation and its potential for teaching sorting algorithms.
• 🧠 The discussion touches on the idea of 'perspective' as a key to understanding complex computer science concepts, suggesting that simple visualizations can lead to profound insights.
• 📚 The script mentions an attempt to apply this visual approach to other sorting algorithms like Quicksort and Merge Sort, indicating that while the method is insightful, it may not apply universally.

Q & A

What is the main focus of the transcript?

The main focus of the transcript is to explain two well-known sorting methods, Selection Sort and Insertion Sort, and demonstrate how they are fundamentally the same when viewed from different perspectives.

How does the speaker describe the process of Selection Sort?

The speaker describes Selection Sort as a process where each column of a sorting grid selects the smallest number from the remaining numbers and pushes it to the bottom, eventually resulting in a sorted list.

How is Insertion Sort different from Selection Sort in terms of visualization?

While Selection Sort focuses on columns selecting the smallest number, Insertion Sort focuses on rows inserting numbers into the correct position in an already sorted sequence. Both processes result in the same sorted output but are viewed from different perspectives.

What example does the speaker use to explain the sorting process?

The speaker uses the numbers 5, 2, 3, 1, and 4 in random order to demonstrate how both Selection Sort and Insertion Sort can sort these numbers into ascending order.

What is the basic building block used in the explanation?

The basic building block is a simple sorting box that takes two numbers, outputs the smallest number at the bottom, and the largest number at the right-hand side, regardless of the input order.

Why does the speaker believe that Selection Sort and Insertion Sort are the same?

The speaker believes that Selection Sort and Insertion Sort are the same because, when visualized, the sorting steps are identical whether viewed by columns or rows, suggesting a hidden structural similarity between the two methods.

What is the significance of visualizing sorting algorithms according to the speaker?

According to the speaker, visualizing sorting algorithms helps to uncover hidden connections and structural similarities that are not immediately obvious when simply writing or coding the algorithms.

How does the speaker demonstrate the progression of sorting in Selection Sort?

The speaker demonstrates the progression of Selection Sort by showing how the smallest number in each column moves to the bottom, gradually leading to a fully sorted list after processing each column.

What does the speaker say about their discovery regarding these sorting methods?

The speaker shares that they discovered the similarity between Selection Sort and Insertion Sort while trying to teach sorting algorithms. This observation came from visualizing the sorting process rather than relying on coding or complex computer science concepts.

Why does the speaker believe that others might not have noticed this similarity before?

The speaker believes others might not have noticed this similarity because the structure of these algorithms is often hidden in the code. By focusing on simple visual representations instead of programming, this hidden duality between the methods becomes apparent.

Outlines

00:00

🔢 Understanding Sorting Algorithms: Selection Sort vs Insertion Sort

In this introduction, the speaker sets the stage for discussing two popular sorting algorithms: Selection Sort and Insertion Sort. People often see these as distinct, but the speaker reveals that they are, in fact, the same when visualized in a specific way. Using illustrations, the speaker will demonstrate that both sorting methods share an underlying structure. The aim is to convey this through simple visual representations without requiring any programming knowledge.

05:02

📦 Visualizing Sorting with a Simple Box

The speaker explains sorting by visualizing a process using a 'sorting box' for two numbers. This box compares two inputs and outputs the smaller one at the bottom and the larger one on the right, regardless of input order. By connecting several of these boxes into a triangle-shaped network, the speaker demonstrates how numbers can be sorted. A specific example using five random numbers (5, 2, 3, 1, and 4) is processed to illustrate how the smallest number is selected by the network and 'ripples' down to the bottom.

🔁 Visualizing Selection Sort: Column by Column

In this section, the speaker describes how the triangle of boxes visually represents Selection Sort. By treating the columns one at a time, each column selects the smallest number and moves it to the bottom. The remaining numbers are progressively sorted in the same manner, with the smallest numbers moving down each column. This visual approach highlights how the Selection Sort algorithm works by selecting and positioning the smallest numbers until the list is fully sorted.

🖼️ Reinterpreting the Same Diagram: Insertion Sort

Here, the speaker reinterprets the same diagram used for Selection Sort, this time focusing on rows instead of columns. In this new perspective, the diagram shows how Insertion Sort works. Each row inserts a number into its correct position in a partially sorted sequence. The process continues row by row until all numbers are in the correct order. This row-based visualization demonstrates that Insertion Sort and Selection Sort are identical when viewed from different perspectives.

🔄 Comparing Selection and Insertion Sort: Two Sides of the Same Coin

The speaker concludes by emphasizing the dual nature of these sorting algorithms. By viewing the process either through columns (Selection Sort) or rows (Insertion Sort), the same sorting behavior is observed. This revelation, based on perspective, showcases the deep connection between the two methods. The speaker reflects on the simplicity and elegance of this discovery, suggesting that certain complexities in computer science can be unraveled by shifting perspectives.

🔍 Exploring Further: Other Algorithms and Dualities

In a closing conversation, the speaker shares how this insight sparked curiosity about other algorithms like Quicksort and Merge Sort. Despite some exploration, the same duality found between Selection Sort and Insertion Sort did not emerge in those cases. The speaker reflects on this journey of discovery and encourages further thinking about visualizing algorithms in new and intuitive ways.

Keywords

💡Sorting

Sorting refers to the process of arranging items in a specific order, typically numerical or alphabetical. In the context of the video, sorting is the main theme, focusing on algorithms that organize numbers into ascending or descending order. The script discusses two sorting methods, Selection Sort and Insertion Sort, and reveals a surprising connection between them.

💡Selection Sort

Selection Sort is a simple comparison-based sorting algorithm. It works by repeatedly selecting the smallest (or largest, depending on the order desired) element from the unsorted portion of the list and moving it to the beginning of the sorted section. The video script uses a visual approach to demonstrate how Selection Sort operates, showing that each column in a sorting grid selects the smallest number from the remaining unsorted elements.

💡Insertion Sort

Insertion Sort is another simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. The video script reveals that Insertion Sort can be seen as the same process as Selection Sort, but viewed from a different perspective, focusing on rows instead of columns.

💡Perspective

Perspective in this context refers to the way one views or interprets something. The video script emphasizes that the difference between Selection Sort and Insertion Sort is merely a matter of perspective. By changing the way the sorting process is visualized, the same underlying mechanism can be seen as two different algorithms.

💡Algorithm

An algorithm is a set of rules or steps used to solve a problem or perform a computation. In the video, algorithms are the methods used to sort numbers. The script discusses how different algorithms can be visualized and compared, highlighting the simplicity and elegance of Selection Sort and Insertion Sort.

💡Ascending Order

Ascending order is a sequence where each element is greater than or equal to the one before it. The video script mentions ascending order as the desired outcome of the sorting process, where numbers are arranged from smallest to largest.

💡Descending Order

Descending order is the reverse of ascending order, where each element is less than or equal to the one before it. While the video script focuses on ascending order, the concept of descending order is implicitly understood as the opposite sorting arrangement.

💡Computer Science

Computer science is the study of computers and computing, including their theory, design, development, and application. The video script suggests that understanding sorting algorithms, like those discussed, does not require extensive knowledge of computer science, emphasizing the accessibility of these concepts.

💡Visualization

Visualization in the context of the video refers to the use of diagrams or drawings to represent abstract concepts or processes. The script uses visualization as a tool to demonstrate the equivalence between Selection Sort and Insertion Sort, making the sorting process more intuitive and easier to understand.

💡Duality

Duality in this context means the existence of two forms or aspects that are fundamentally the same but appear different. The video script explores the duality between Selection Sort and Insertion Sort, showing that they are essentially the same algorithm viewed from different angles.

💡Magic

In the video script, 'magic' is used metaphorically to describe the surprising and enlightening realization that two seemingly different sorting algorithms are actually the same when viewed from different perspectives. It conveys the sense of wonder and discovery in understanding the underlying simplicity of these algorithms.

Highlights

The lecture discusses the surprising equivalence between Selection Sort and Insertion Sort.

Sorting methods are often perceived as distinct, but the lecture reveals a hidden connection.

Visual illustrations, rather than coding, are used to demonstrate the sorting methods.

The concept of a 'sorting box' for two numbers is introduced as a basic building block.

Sorting is visualized as a network of these 'sorting boxes' arranged in a triangle.

The process of sorting is shown by pushing numbers through the network column by column.

Selection Sort is explained as a method where each column selects the smallest number.

The same sorting network is then viewed row by row to illustrate Insertion Sort.

Insertion Sort is described as inserting each number into the correct position in a sorted sequence.

The lecture emphasizes the importance of perspective in understanding sorting algorithms.

The speaker shares a personal anecdote about the 'Eureka' moment of discovering the connection.

The simplicity of the observation is highlighted, contrasting with complex computer science concepts.

The lecture concludes with a discussion on the potential for similar insights in other sorting algorithms.

The speaker's colleague from Oxford is mentioned as a collaborator in exploring this concept.

Attempts to apply this perspective to Quicksort and Merge Sort are mentioned, with mixed results.

The lecture concludes by emphasizing the value of simple observations in complex fields.

Transcripts

Today we're going to talk about sorting. And in particular, we're going to talk

about two very well-known sorting methods. One is called Selection Sort; the

other one is called Insertion Sort. And when people learn about sorting methods

they usually learn about these as being two completely different ideas. You have

selection sort on the one hand and insertion sort on the other hand. And what I'm going

to show you today is that these are actually the same; you can regard them as

being equal. The trick is that you just draw pictures of them. You don't need any

coding to see this; you don't need to know any fancy stuff. In fact, you don't

need to know anything about computer science at all. If you just draw a

picture of selection sort in the right way, and a picture of insertion sort in

the right way, you see that they're actually the same thing. And this is kind

of a secret about sorting methods that even people like me, who have been doing

computer science for many years - most people - or hardly anybody - actually

knows this little trick. We'll start off by kind of refreshing ourselves with

pictures about what sorting actually is. So, let me draw a box. What we're going to

do is put some numbers into this box. It doesn't matter how many numbers - everything

which I'm going to show you is completely general - but we'll do it with five.

So suppose we do a 5 and a 2 and a 3 and a 1 and a 4. These are the first five numbers, in

some kind of random order here. But the key thing is they're not sorted, they're not in

ascending order. What we'd like our sorting box to do is

give us the same numbers out, but in sorted order. So we'd like to have 1,

2, 3, 4 and 5 coming out. Let's start to think about how we might

construct a little program which implemented this kind of sorting

procedure here. The most basic building block which you can think of is just a

little box with four sides. What this box is going to do is on the left-hand side

and on the top side you're going to have two numbers come in. And then, at the

bottom, the smallest number is going to pop out. And on the right-hand side the

largest number is going to pop out. So you can think of this as being like

little sorting box for only two numbers. So, for example, if we put the number 1

in on the left-hand side and the number 2 in on the top, then what our little

sorting box would do is give us the smallest one out the bottom

and it will give us the biggest one out the right-hand side. So, this is a sorting

box for two numbers. And it doesn't matter the order in which the two numbers come in.

So if I swap this around and if I had the 2 coming in here and a 1 coming in

here, it doesn't make any difference. The

smallest one is going to pop out the bottom, and the biggest one is going to

pop out the right-hand side. So the game here is we've got this basic building block

and we want to kind of plug these together, just with pictures, and see

how you can build a little sorting program

The trick is that you just build a little triangle of these boxes. So let's

put a bunch of these things together. There's a little triangle of these boxes

and we're going to just wire them together in a very straightforward way

We'll just draw the obvious little links between them. And each of these boxes

just sorts two numbers, like we saw a few moments ago. So let's take our little

example and just push it through this little sorting network and actually

see what happens. So I think the numbers we had were 5, 2, 3, 1

and 4. So, out the bottom, we hope to get 12345. So let's see what happens.

So we're going to treat the first column first of all and we'll see what happens.

So it's really simple. So, you've got the 2 and the 5 coming into the first box.

So the smallest number pops out the bottom. So that's the 2, and the biggest

number comes out the right-hand side - so that's the 5. And then we do the same with

the second box in the column. So we've got 2 coming in, and a 3 coming in, so

the smallest number pops out the bottom. And the biggest number comes out

the right-hand side. And we just do the same again. Then we got a 1 and a 2 - so the 1

comes out the bottom, and the 2 comes out the right-hand side. And then we've got 4

and a 1 - the 1 pops out the bottom and the 4 comes out the right-hand side.

So what you see is that the smallest number, which in this case is 1, has

kind of rippled its way down to the bottom. So what's happened is this first

column has selected the smallest number. And it's quite easy to see that that's

the case, because the top box selects the smallest from the two numbers it's given,

and then the second box selects the smallest numbers from the two numbers

it's given, and so on and so on. So kind of - the smallest number is going to

ripple its way down to the bottom - so selecting the smallest one. Then we do

the same with the remaining columns, and

we won't be surprised with what happens. So we've got a 3 coming in and a 5

coming in. So the 3 will pop out and the 5 will pop out here. Then we got a 2

and the 3, so the 2 is smaller so it pops out. And the 3 comes out here. And then we got 2 and

a 4, and the 2 is the smallest. And then the 4 pops out the other side. You see

what's happened again: from the remaining numbers 5, 3, 2 and 4, the second column

has selected the smallest one. And then, if we just complete this, it's obvious what's

going to happen. We get a 3 here and a 5 here. 3,4,4,5. So what you see is that

our little sorting grid has taken five numbers, in a mixed-up order, and just by

pushing them through, one column at a time, we've ended up with the numbers in

the correct order. And this is known as Selection Sort, because each column just

selects the smallest number from what is left.

OK? So nice and easy. You don't need to know anything about computer science, anything

about algorithms, anyone can understand what's going on with selection sort here.

But, you can actually view this picture in another way. So let me re-draw the same

picture. So I just wire it up, in exactly the same way as before. And we'll push

exactly the same five numbers through. So we started off with a 5,2,3,1 and a 4.

So, what we did last time is we treated it in terms of the columns. But actually you

can do exactly the same thing in terms of the rows. So we'll do one row at a

time, and actually see what happens. So, if we consider the first row, it's the

same as before. We get the 2 and the 5 coming in. And the 2 pops out here,

and 5 pops out on the right-hand side, because the 2 is the smallest one.

So we'll do the second row. So what happens? So, we've got a 2 and a 3 coming in.

So the 2 is the smallest; it'll come out the bottom. And 3 is the biggest so it comes

out on the right-hand side. And then we go over to this box in the row. We've got

a 3 and a 5. So, the 3 comes out the bottom, and the 5 comes out the

right-hand side. So what's actually happened is the

second row has taken the 2 and the 5, which are already in the right

order, because the first box did that for us. And it's taken the 3 and it's

put 3 into the correct place. So maybe if I use a different colour here,

you can see this. So I've got a 2 and a 5 here. And then

I've got a 3 coming in on the left-hand side. And what the second row

does, is it puts the 3 into the right place. So, out the bottom, you get 2, 3 and 5.

So what the second row has done is inserted this number into the right

place. And let's see what happens with the next row. So then we've got a 1 and a 2

coming in. So the 1 comes out the bottom, because it's the smallest. And then the

2 comes out here. And we've got a 2 and a 3 Se we get the 2 and the 3. And then we've got

a 3 and a 5. And the 3 is the smallest, so it comes out here. What you see is exactly

the same thing has happened again. We had a 1 here and then we had 2, 3

and 5, which has already being sorted by the grid above us. And then this row

here is just going to put the 1 into the right place.

What's popped out the bottom of this grid is 1, 2, 3 and 5. So we just complete

the picture. We'll get the expected results. So we've got a 1 and a 4. So, the 1 is the

smallest so it pops out the bottom. And the 4 goes around here. And we've got a 2 and

a 4. So the 2 pops out and the 4. And the 3 and the 4. So the 3 is smallest and then

we get the 4 and the 5. This sorting method, when you think about the

rows rather than the columns, is called Insertion Sort. And it's called

insertion sort because each of these rows just inserts a number into the

correct position in a sorted sequence. So, for example, if we look at the bottom row

here, the input on the top is a sorted sequence - 1, 2, 3 and 5 -

those are in the right order. And all the bottom row is doing, is putting this 4

into the correct position so that we get 1, 2, 3, 4 and 5.

Previously, we had exactly the same picture, and we said that's selection sort,

if you view it in terms of the columns. And if you take the same picture now, and

view it in terms of the rows, this way around, then we get insertion sort. So, for

me this is a bit of magic. I've been in computer science for a long, long time.

I was thinking about how to teach sorting algorithms to my students a few years ago,

and came up with this pictorial idea, and I didn't realize until then that

insertion sort and selection sort are exactly the same thing. But you only see

this if you look at it in the right way using the pictures.

>> Sean: Basically it all comes down to perspective, right? >> Graham: Yes, exactly, it's ...

if you look at stuff in the right way then you can see things that you

couldn't see before. So, if you write programs to do

insertion sort or selection sort, the kind of structure here, which is the same,

is being kind of hidden from you. But if you just draw some simple

pictures and forget all your fancy computing, then you end up with an

observation which is quite interesting. >> Sean: Have you come across anything else that

that is kind of similar? Have you gone through other sort of algorithms and

thought about them this way? >> Graham: Yes a colleague of mine from Oxford a

few years ago, I was showing him this to him. And he said: "Oh! we can write a paper

about this!" So we tried to look at, like, Quicksort and Merge Sort, and see if they

had the same kind of duality. But it didn't quite work out at the time. And we

kind of gave up writing the paper about it. But, I think this is just a simple

observation in its own right here.