Hello, everyone. In this lesson, we will start learning Chapter 8 of Data Structures and Algorithms —- Internal Sorting.
Firstly, Let’s take a look at the basic concept of sorting.
Sorting is an operation of records of sequence.
And a sequence is a linear list which have been introduced previously.
The elements of linear lists, which we call is records here, is the basic unit of sorting.
In the sorting problems, the sorting is based on the record’s key which can identify itself in many cases.
But in the other cases, it may be necessary to use a number of fields of record ,or even some repeated fields.
For instance, if we sort people according to their names, it’s possible that there are some people having the same name.
The sorting problem is to sort the sequence according to sort key of the record, and finally make the original sequence become a non-reduced or non-increase sequence.
We can say that the entire process is completed in memory
when the scale of the sorting problems is small.
And we can regard a sequence as an array since the sequence is the linear list.
Especially when we get input data form an array and also put output data on an array.
Let's formalize the sorting problems.
There is a sequence from r 1 to r n, the corresponding sort key is k1..kn respectively
The purpose of our sorting is to get a order sequence form r1’ to rn’, and the corresponding sort key is k1’..kn’ respectively.
And the sequence of sort key have a property that
k1’ is less than or equal to k2’, less than or equal to, till less than or equal to kn’.
We call this kind of sequence an non-reduce sequence.
If there is no equal sort key, we can call it ascending sequence.
Similarly, we can define non-increase and descending sequence.
The positive sequence and the inverted sequence are also important concept of sorting problem.
This so-called positive sequence is an ordered sequence according to your requirement.
And the inverted sequence is an completely reverse positive sequence.
The another property is stability.
if the relative ordering of records which have the same sort key don’t change after the sorting.
For example, 34, 34’ have same sort key in the original sequence, and after sorting, 34 is sting before 34’.
Actually we should present a strict formal proof if we want to say an algorithm is stable.
Similarly, there is a kind of algorithm called unstable algorithm.
Which means invariances of relative ordering of records that have the same sort key can’t be guaranteed.For example, like this.
As for unstable algorithm, we can show counter examples to prove it’s property.
The most important thing of evaluating sorting algorithm is code of time, especially number of compare of records and and number of moves.
The another import thing is cost of memory, which mainly means the necessary auxiliary space we need to complete the sorting algorithm.
For instance, if we sort an array consist of n elements.
If we need auxiliary space to store another n elements. The cost of the memory is O(n).
If i only need a variable to record one element of the array temporarily. The cost of memory is O(1)
Sorting algorithm is a basic algorithm which would be used repeatedly.
So whether the algorithm is easy to write, is easy to read, is easy to maintain should be considered.
Finally, I will left you with two problems.
The first is the meaning of stability of sorting algorithm?
The second is why we should consider the positive sequence and the inverted sequence. Thank you.