Hello, everyone!
This lesson, let's learn selection sort of Chapter 8 internal sort. It includes direct selection sort and heapsort
About direct selection sort, it will select the minimum record in the sequence which is waiting for sorting in turns.
heap sort is implemented by making use of maximum heap.
Let’s look at the demonstration of direct selection sort.
In the array waiting for sorting , we can see that 12 is the minimum number.
So we place it at the position for the minimum number
Then 29 is the minimum one. So we exchange it with 34 which take up the position for the minimum number.
We do this operation in turns until all the elements are handled. And then the sorting is finished.
The frame of redirect selection sort is this.
At first, we store the subscript of the element taking up the position for the minimum element in the variable smallest.
Which means I assume the element in this position have the minimum value.
After that, we look back, from this element to nth element , we observe elements one by one.
compare the elements behind to the element in the position of subcript which we stored in variable smallest previously.
Of course, if we find an element less than the element we store now, we can modify the subscript of the minimum element.
Once this loop is over, we already know at where the minimum element of the subsequence stay.
Then we can exchange this element with the element whose subscript is i.
In this loop, we operator n-1 times.
Which means we choose the first-small element, the second-small.. the (n-1)th-small in turn.
And the rest one, of course is the biggest one.
This algorithm is unstable.
mainly because when we choose the ith-smallest element,
we will choose the last element in the set of the elements having the smallest value in the subsequence.
And exchange this element with the element whose subscript is i.
The distance between them is very long. Which make it unstable.
It’s cost of memory is θ(1).
mainly because of the temporary variable we use in swap operation.
As for cost of time, most time is spent in compare.
In every loop, we need to look the element in the subsequence in turn.
So during the double circulation. we have compared n^2 times
As to the number of exchanges, we can say it is not big comparing to other sort algorithm.
In other word, we will only exchange when the element in position i is not the ith-smallest element.
Therefore, the number of exchange is n-1 in total.
The total cost of time is θ(n^2).
AS for heapsort, it make use of the maximum heap.
The maximum heap retains relative sizes of these elements.
Once we find the maximum element, we can find the second maximum one. Then find elements one by one.
Therefore, it is faster than the previous simple direct selection sort.
There are more selection sorts, we will introduce them in external sorting.
let’s look at the process of the sorting.
Firstly,we need to build a maximum heap.The process of building is linear, which means it can be finished in theta(n) time.
after that, we delete it from heap
AS for deletion,actually we just need to find the last element in the heap, then exchange it with the element in the heap top.
once the exchange is completed, the maximum element is out of heap.
Then the size of the heap is reduced by 1.
After that, we adjust the rest elements from the root,
adjust it to a new maximum heap which size is reduced by 1.
We can see that, in the process of the adjustment, we just find the position the it should stay at.
After that, we push the elements in the path from the root to this position to the root.
Let’s look at the process of heap sort, At first, we build the maximum heap.
then,we perform operations n-1 times.
For every operation, we delete the maximum elements in the current sequence.
After deleting the maximum element, it will stay at the appropriate position in the current case.
The maximum one will stay at the last of array.
The second-biggest one will stay at the penultimate position of array.
When operations are finished, the array is just ordered without other operation.
The cost of time spent on building heap is θ(n).
As for cost of a single delete operation, if there are n elements in the heap, it would be θ(log n).
If there are i elements, it would be θ(log i)
The process of the sort is consist of one building heap and n-1 delete operation
So the total cost of time is θ(n log n)
The memory is mainly consist of auxiliary space we need during swap operation and move.
And the cost of the auxiliary space is θ(1).
Finally, I left you with some questions to think about.
The first one is that, why is the direct selection sort unstable in consideration of that it is so simple.
And can we modify it to make it stable?
In addition, we can modify the heap sort algorithm.
When we find tow elements unordered, we swap them directly
rather than find the position it should stay at
and then push the elements on the path from the root to the position we find to the root.
Thank you.