Sorting Secret - Computerphile
Summary
TLDRIn 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
🔢 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.
📦 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.
Mindmap
Keywords
💡Sorting
💡Selection Sort
💡Insertion Sort
💡Perspective
💡Algorithm
💡Ascending Order
💡Descending Order
💡Computer Science
💡Visualization
💡Duality
💡Magic
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.
Weitere ähnliche Videos ansehen
Sorting - Part 1 | Selection Sort, Bubble Sort, Insertion Sort | Strivers A2Z DSA Course
Programming BASIC and Sorting - Computerphile
Algorithms Explained for Beginners - How I Wish I Was Taught
3 Types of Algorithms Every Programmer Needs to Know
61. OCR GCSE (J277) 2.1 Insertion sort
59. OCR GCSE (J277) 2.1 Bubble sort
5.0 / 5 (0 votes)