Well, good morning or good afternoon.
I am Esteve Codina
and I'm going to present this video,
which is 16P, where we develop
the bubble sort algorithm as an exercise of the previous video
16T, in block number six "Algorithms
and Graphs. Some elementary concepts".
We will follow the following order of contents.
We will go next to the the learning objectives.
So we'll see the introduction.
And next we will go into a new set of data structures,
the pointers
we will describe the elementary sorting algorithm, the bubble sort
we will see two 'pidgin' codes for the bubble sort
and we will see references for consulting
additional additional elements for the bubble
sorting algorithms,
and finally extensions.
Okay.
So the learning
objectives are to put in action concepts seen in the previous video.
16T by means of an exercise.
So we will set initially
the previous concept, which is the special data structure: the pointers
We use the pointers and next with the pointers tool we will go
into the description of bubble formation for which we will see two 'pidgin' codes
describing this algorithm.
Okay, so
well, we have already seen that there are problems in urban mobility
which require algorithms as a way of solving these problems,
and they need numeric data sets structured
in data structures in the computer.
for solving them,
right?
We have seen arrangements or arrays, one dimensional, two dimensional
in the previous video,
and we will see now the concept of pointers.
Okay, so what do we understand by pointers?
Pointers simply are variables whose contents,
or that contain, precisely addresses
or positions to another variable or arrangement.
For instance, imagine that we have an array called P, as we had
in the previous video of four positions containing 2000 10,000, 100 and 500.
And we want to refer to an arbitrary position of this arrangement P.
Then we can use an additional variable PI
which will contain this arbitrary position to the arrangement P,
right?
So if
these are, if the variable PI contains three,
then it means that we are pointing to the third position of arrangement P,
right?
Okay.
So in the 'pidgin' code, a P(PI) will contain 100 if PI is 3,
in summary.
Okay,
so let's go now into the description of what do we understand
by the bubble sort algorithm.
Imagine that we have an arrangement of four positions called H,
which is not ordered, right?.
So we want precisely to order them.
So that the first position is smaller or equal than the second position,
the second positions smaller or equal,
than the third, and the third is smaller or equal than the fourth.
Okay.
So, an intuitive way to proceed is the following one.
We can set a window on the left side of the arrangement
of two positions, of length 2.
And we make a comparison between these initial two positions: six
the first, and then the second, which contains zero.
If the first position is smaller than the second position, we will leave it as is.
On the contrary, we will interchange
the content of the first position with the second position.
Next we will move the window, one position
to the right, and we carry out the same operation.
We will compare the second position with the third position,
we need to change them
if the second position is larger than the third position
or we leave it as is, if otherwise, right?.
And finally we will move to the rightmost position,
this window of length two, and we'll carry out to the same operation.
So in the end we will make sure that the largest element of the arrangement
will be set in this final position: in position number four.
Okay.
So the procedure will have to be repeated again, starting from the beginning,
but we will not necessarily need to check it until the end, because in the end
we know for sure that the largest element will be stored into it.
Right?
So in the second pass of the algorithm, we again see the first position.
With the second position, we compared them and interchanged them if necessary.
And we will move this window of two
to position 2 and 3, and we will make the same comparison.
But we will not go further
because we know that in the final position we have the largest element.
So after the ending pass of this second iteration,
we see that the second largest element of the arrangement
is contained in position number 3.
So, finally we will go into the first and the second
and we'll compare them and we will leave finally the array sorted.
It will finally contain 0356, which is an array which is sorted,
Right?.
Okay.
So, this is a verbal description, using natural language, of the algorithm.
And we what we want to know is, using the 'pidgin' code and the structures
that we have seen in the previous video, a description of the algorithm.
Okay.
So we will make use of these data structures.
We will store our data into the array H.
We will use an index variable for
the numbers 1 to 4, and we will use two pointers.
The pointer 'ini' will go to an arbitrary
point of the window and 'bottomH'
will go to the ending searchable position of the arrangement H,
yeah?,
Okay.
So, the 'pidgin' code for
the bubble sort could be described as follows, right?
So initially we would set the pointer 'bottomH'
as the dimension of the array,
yeah?
So bottom eight, is set to 4,
pointing to the final position of the arrangement H,
and then what we have done is a series of iterations
which will start, sorry, that are carried out
while the ending position is larger or equal than two.
Yeah, so we start with 'bottomH' = 4, so we will make a pass
of this initial iterative step.
So, the first 'while'
contains as condition 'while bottomH is larger or equal than 2',
right?
So, when bottomH is smaller than 2,
this will mean that we have ended the algorithm. Yes.
So, no action will take place when 'bottomH' is smaller than 2.
The actions within this 'while' statement are: initially,
we will set the 'ini' pointer equal to 2
and then we will go from 'ini' to 'bottomH',
making the comparison with the window of two positions that we have seen.
Notice the structure of this 'pidgin' code description.
We have two 'while's. The first 'while' is the external 'while', right?.
So is the passage that we read from
from position number 2
to the largest searchable position and we inserted into it
another 'while'; a nested 'while',
right?. Okay.
So the nested while starts from position 'ini' to 'bottomH'.
And what we do is: if we find that within positions 'ini'
and 'ini' - 1, which marked the window,
we find them ordered, then
we simply do nothing, yeah?
Yeah!.
If H[ini] is smaller than H[ini-1],
then we interchange the contents.
Otherwise we do nothing and we increase the pointer 'ini'.
in 1 position,
right?.
So after that
we go to the last position 'bottomH' and decrease bottomH
by one position, right?.
So notice that we have inserted in, a natural language description,
which is 'interchange contents' over H[ini] and H[ini-1].
So the interchange contents
would be simply carried out by using an additional variable
and on capital H, which will store the position of H[ini-1],
and then we would put H[ini] into H[ini-1].
And then the content of the variable
non-capital h will be led into H[ini],
and in this way we would have interchanged H[ini] and H[ini-1].
Okay, so this is all for
the first description of the bubble sort algorithm.
An alternative description of the bubble sort algorithm
could be the following one.
We've just practically the same as the previous one.
We have also an initialization step
which consists of setting the bottomH to the largest position.
And now instead of using a 'while'
as a structure in the inner loop, we use a 'for' statement
because we know in advance that we have to go from 2 to 'bottomH'.
So we know in advance how many passes from
the window of length 2 we have to do in each internal iteration.
So now we have 'for' and 'for' uses
an implicit index, which is J. So the contents of J
starts from 2 and goes to 'bottomH'.
So, at each pass of the 'for' statement,
we do exactly the same interchange as we did in the previous slide.
Notice that
index j is not increasing the 'pidgin' code,
while in the previous code the 'ini' pointer was increased
each time in the description of the algorithm.
Okay.
Okay. So,
once we have made a description of the algorithm
through a 'pidgin' code,
and we are more or less sure that it will work, it's valuable
to trace the algorithm. Tracing the algorithm is: write out the values
of the pointers and the variables at each pass of the algorithm
so that they match what we think that they have to do, right?.
So check, please, that
the the final sequence of variables is obtained
after each pass of either of the two
previous 'pidgin' codes.
So the key learning
concepts that we have learned are the following:
we have revisited the concepts seen in the previous video.
We have seen again, the notion of a new data structure.
We have seen a more complex algorithm
than the calculation of Fibonacci numbers, the bubble sort algorithm.
We have seen how the 'pidgin' codes
describe algorithms working with data structures and we have seen
also more complex examples of 'for, 'while' and 'if' structures.
Okay.
As references,
you can see, for instance, they're also descriptions,
in these two web pages.
And as suggested exercise,
I suggest to you to calculate
the sequence of prime numbers smaller than a given number
using the sieve of Eratosthenes.
So go into this web page,
get a knowledge of what is the sieve
of Eratosthenes in this, and try to write a 'pidgin' code describing
the algorithm procedure that implements the calculation of prime numbers
using this very efficient procedure.
Okay.
Also in the proposed exercises, look at the binary search algorithm.
Yeah?.
So this very easy web page, the codewizards
algorithm for kids, contains the binary search,
for looking where to find positions, where to insert some
given value within a sorted arrangement.
In both cases, write out
a code for the algorithm, make a description of the necessary data structures.
And finally, after making sure that you
have a right 'pidgin' code
algorithm, trace your algorithm
writing out the variables and each loop of the corresponding algorithm.
So here you can see as block extensions.
Well, as I already said in the previous video,
it would be good that you have an introduction to Python programing
in these two references.
Thank you very much for your attention.