Hello, everyone. Data structure and algorithm. This lesson, let’s learn exchange sort including bubble sort and quick sort, of Chapter 8 internal sort.
Bubble sort and quick sort are both based on swap. Which means the sort is completed by swapping the elements unordered.
Let’s look at the concept of bubble sort.
Bubble sort, in every round, it compares all neighbor elements in reverse order. And exchange the neighboring elements once we find they are unordered.
In this process, it can find current minimum element every round.
In the next round, downsizing, and being continue to do this until the sort is over. Then the array is ordered.
There is an interesting dance, bubble sort dance.
From the dance, we can see that interaction of the actors represent different numbers, swap the elements when we find themare unordered
and then continue this process. During each round, we can select the minimum element.
Let’s look the demonstration of bubble sort.
We start from the last, if we find inversion element.If not, continue to move forward.
After the end of this round, we can definitely select the minimum one. In the next round, we can select the second-biggest one similarly.
The process of bubble sort looks like the process of direct selection sort.
In direct selection sort, in the process of selection the minimum element,there is not so many swaps.
And we just swap it and the element taking up the position for the minimum element.
There is only a big swap rather than many small swaps in every place.
Therefore, in the the sense we consider average cost, it is more efficient than bubble sort.
Let’s look the frame of bubble sort.
In the outer loop, we logically start from the position 0 of the array to the position n-1,work n-1 times. Because in the last round, there is only one element, nothing we need to do.
At the beginning of each round, we make a mark, which means there is no swap in this round.
If we actually swap, we should modify the mark.
In the inner loop, we start from the last of the array, and move forward step by step.
Every time, we compare the element on current place to the element exactly before it, and check whether they are reversion element.
It they are, we swap them and we modify the mark. make the mark false, which means we swap this round.
After finish the inner loop,
if the mark is true, which means the elements in last round is ordered.
there is nothing to do, we can directly stop and exit.
If not, which means we swap last round, we have to enter the next round of outer loop and continue to work, until the sort is over.
Bubble sort is stable.
Because in the process of sort,once we find reversion element, we exchanges them.
So there is no big jump.
As for the neighbor having the same key, we can do nothing and retain the relative order of them.
Not like direct selection sort.It find the minimum one, then definitely exchange it for the element taking up the position for the minimum element.
The swap is big, and cross very big space. Hence, direct selection sort is unstable.
In the other hand, the cost of it is only θ(1).
Because we only need a temporary variable to store data when we swap.
As for cost of time, we divide it into number of compare and swap.
In the best case for compare, which means the original array is ordered。
we would find this in the first round.
So, the minimum number of compare is θ(n)
In the worst case, which means the array is in reserve order.
Then we have to handle the whole subsequence every round.
Therefore,the maximum number of compare is θ(n^2).
那交换次数呢，也跟刚才的比较，它是相关的。aAs for number of swap, is related to compare.
In the best case, which means the sequence is already ordered,
There is no swap, so the minimum time is 0.
In the worst case, which means the sequence is in reverse order,
we have to swap every neighbor in the whole process, the cost would be θ(n^2)
The average of number of swap is θ(n^2).
The total cost of time in view of discuss of compare and swap previously,in the worst case, is θ(n^2)
the best case corresponds to ordered sequence,the cost of time is θ(n).
Ok, let’s look at quick sort,which is another sort based on swap.
the concept of quick sort is to find threshold value. This threshold value, may not be the value of certain element of sequence,
we only need it to divide the sequence waiting for sort.
Then we divide the sequence waiting for sort into two subsequences by the threshold value, to make the each record of left subsequence is smaller than or equals to the threshold value.
And the records in the right are all bigger than the threshold value.
For this two subsequences, we continue to handle them in the same way. It’s obviously an idea of divide and conquer.
The quick sort is a very important algorithm.
The time it is presented, is exact time of rapid development of application of computer.
And sort, like operator system, etc, be widely applied to many software.
And quick sort is very efficient indeed.
Quick sort, it is a very classic concept base on idea of divide and conquer. Within the sort algorithms, merge sort is also kind of sort based on divide and conquer.
Let’s look at the strategy of divide and conquer.
It mainly is these.divide, in other words, divide big problems into small problems.
conquer, in other words, the process of solving every small problem.
On, these small problems cannot overlap.
Only in this way, we can divide and conquer and don’t care about other conditions.
The last is merging.We may need to collet and organize the results of previous divide and conquer.
The different way of divide and conquer,may perform differently in the concrete process.
Concrete analysis of concrete problems in needed.
In the algorithm we have contact, like binary search tree,and binary searching, are both based on the idea of divide and conquer.
Let’s look at the concrete idea of quick sort.
Firstly, we find a threshold value.Then we divide it into two subsequences。 This threshold value just stay at the someplace of array waiting for sorting.
and handle the subsequence in the same way.
At the time of division, some sequence may be empty, then the another subsequence contains all rest elements.
We can see the conquest is also completed in the process of division.
So division and conquest is processed simultaneously.
The process of merging is not obvious.
Because our every threshold value is just stay at the final position when the sequences is divided and conquered.
We work recursively until the subsequence only contains one or zero element.Then it is handled.
If we look the elements in the array sequentially, it would be ordered.
When we study quick sort, the most important thing is to consider the selection of threshold value.
Because it determine whether the sequences is divided evenly.
These are all problems we should consider in the divide-and-conquer method.In other words, we should divide the big problem evenly.
And there are many chooses of threshold value. You may select the right-most element or left-most element.
But in this case, the algorithm would perform poorly for the sequence ordered or in reverse order.
It is of course good if we select randomly which means sequence is certainly divided evenly.
Actually, there is kind of study of quick sort called RQS, which means Randomness Quick Sort, also is randomly selection.
In addition, we may select the average of the elements of array.
We scan the array, sum the values of elements up, then divide sum by number of elements, then we get the average value.
Ah,of course it is a little troublesome and is unnecessary.
Actually we just need to avoid the selecting right-most or left-most,which cause unevenly partition in extreme situation.
Next, let’s look an example of partition.
Firstly, we choose 32 as threshold value,then put the right-most element on there,, so the right-most position is empty.
We observe elements form left.compare the left element to the threshold value, check whether they are inversion element.
If they are, which means the it should’t stay at left, so we move it to the place which is empty in the right.
So there is an empty place in the left, so we can find an unordered element in the right and put it on here.
If we do it continually, the last position we find should be the position for threshold value.
Simultaneously, the partition is completed.
We can see that elements in the left is smaller than threshold value and element in the right is bigger than threshold value. The position threshold value stay at is the final position for it, and it will not moved in the latter process.
Let’s look the frame of quick sort.
At first, we need to choose the threshold value.
After that, we swap the right-most element and the element having threshold value. In the other words, we empty the right-most position.
The algorithm here we use to choose the threshold value is very simple. the middle subscript is the subscript of threshold value, and pass it into function.
After that, we perform the partition.
The result of the partition is the threshold value pivot. This value is the subscript of the threshold value after partition.
And the whole sequence is already divided into two subsequences.
The elements of left subsequences are smaller than the threshold value. The elements of right subsequence are bigger than the threshold value.
The we recursively handle two subsequences respectively.
We observe the process of division.
We move the threshold value to the right-most position at beginning. Next, we store the threshold value into a temporary variable.
Then the left and right subscript moves from both ends to middle。
Because of empty position in the right,we find reversion element mainly in the left.
Which means the element we find should be bigger than the threshold value.
If we find such element, we put it on the empty position in the right.
Then the right point move forwards.
if not, we just move the left point to right until relative order of left point and right point is reversed.
This is an completely symmetric process,just like we say before.
Finally, when left and right subscript meet,this this left subscript actually is right subscript as well. the position they are at is exact the position for threshold value.
And the subscript of it will be passed to last class as the subscript of the threshold value.
The cost of quick sort for a sequence contains n elements
we assume is as Tn.It can be regarded as constant in special case.
The time of division is spent on scanning the array, so it is cn.
After division, the elements are divided into two parts except threshold value.
Then the sum of size of two parts is n-1.
Then let’s solve this recursion equation.
In the worst case, which means one is an empty sequence,the another one is a sequence which size if reduce by 1.
The result of this recursion equation is θ(n^2).
In the best case, which means the sequence are divided equally every time.
The result is θ(n log n). In the average case, in the other words, uniform probability.
We think the probabilities of the array is divided into 0 and n-1, 1 and n-2, … are equal, are 1/n.
We calculate the average of T(i) and T(n-1-i)
they both are the a nth of sum of T(k)
We replace them with this expression in the previous equation.
Then we get that the cost of time is nlogn as well in the average case.
In the worst case, the cost of time of quick sort is θ(n^2), which means the partition is extremely uneven.
The cost of memory is θ(n).Which mainly because of recursion.
when we walk down class by class, the space of stack is needed.
In the best or average case, the cost of time is n log n,and cost of memory is logn
But we should notice the cost of memory,it is a cost in theory。 But for some special input data, the space requirement may reach θ(n).
In order to handle this extreme situation, we need to θ(n) auxiliary space to support its performance.
Finally, I leave you some questions.
At first, compare bubble sort and direct selection sort, which one is better? why?
Quick sort is unstable, why?
Can we do further optimizing for quick sort?
For example, how can we select the threshold as randomly as possible.
In addition, for some small subsequence, we don’t handle it recursively.
In fact,there are some simple sort algorithm we can use here. Especially the sort algorithm which would perform well for basically ordered sequence or small sequence
We often use inserting sort here.
Another problem is that. how can we eliminate the recursion in the quick sort.
We have learned stack can be used to replace recursion, obviously it works here too.
In quick sort, can wee use queue to eliminate recursion?
For example, to consider such a decomposition tree of quick sort,how do we store the unhandled data
to support the performance of the whole sort.
Thank you.