select sort
The basic idea of selection sorting is: each time select the smallest (or largest) element from the data elements to be sorted and store it at the beginning of the sequence until all the data elements to be sorted are exhausted.
We can define a begin position to place the minimum value found each time, and another end to place the maximum value found each time.
void SelectSort(int* a, int n) {
int begin = 0, end = n - 1;
while (begin < end) {
int mini = begin, maxi = begin;
for (int i = begin; i <= end; i ++ ) {
if (a[i] < a[mini]) {
mini = i;
}
if (a[i] > a[maxi]) {
maxi = i;
}
}
Swap( &a[begin], &a[mini]);
Swap( &a[end], &a[maxi]);
begin++;
end--;
}
}
But there are still some problems with the above algorithm. When we change the array to 26 2 5 3 9 4 8 5 1 7, there will be problems with the sorting results.
Let’s analyze why this happens now?
This is the process of the first run of the program. Even if the intervals of [0,begin] and [end,n-1] are arranged in order, this explains the strange positions of 7 and 1 in the result of the program. This is because begin and maxi are equal. When the position of begin and mini are exchanged, the largest value is replaced. We need to correct the position of maxi at this time.
void SelectSort(int* a, int n) {
int begin = 0, end = n - 1;
while (begin < end) {
int mini = begin, maxi = begin;
for (int i = begin; i <= end; i ++ ) {
if (a[i] < a[mini]) {
mini = i;
}
if (a[i] > a[maxi]) {
maxi = i;
}
}
Swap( &a[begin], &a[mini]);
//When begin==maxi, the maximum value is replaced, we need to correct the position of maxi
if (begin == maxi) {
maxi = mini;
}
Swap( &a[end], &a[maxi]);
begin++;
end--;
}
}
Now the program we ran out is normal. This is also a special case that our selection sort algorithm needs to be aware of.
Heap sort
Heapsort (Heapsort) refers to a sorting algorithm designed using a stacked tree (heap) data structure, which is a type of selection sort. It selects data through the heap.
Properties of the heap:
1. The value of a node in the heap is always not greater than or not less than the value of its parent node (that is, a large or small heap); 2. The heap is always a complete binary tree.
Upward adjustment algorithm
We must first understand the process of entering data from the end of the heap. When we build a small heap and need to enter data 1, we need to adjust the algorithm upwards so that the heap remains a small heap.
When the data is entered into the heap, we name the newly inserted node kid and its parent node parent. Kid is compared with parent. When a[parent]>a[kid], exchange the values of a[parent] and a[kid], and then move the position of kid to the position of parent. Repeat this process again. Specifically, there are diagrams below:
The algorithm for upward adjustment is as follows:
void AdjustUp(int* a, int kid) {
int parent = (kid - 1) / 2;//Calculate the position of the parent node from the position of the child node
while (kid) {
if (a[kid] < a[parent]) {
Swap( &a[parent], &a[kid]);
kid = parent;
parent = (kid - 1) / 2;
}
else {
break;
}
}
}
When we want to arrange an array into a small heap, we only need to use a loop to do it
for (int i = 1; i < n; i ++ ) {
AdjustUp(a, i);
}
Down adjustment algorithm
After understanding the upward adjustment, we need to understand the process of deleting the data on the top of the heap, which requires the use of the downward adjustment algorithm.
To delete the data at the top of the heap, first exchange the data at the top of the heap with the data at the end of the queue, then delete the data at the end of the queue, and use downward adjustment to make the heap still a small heap (we use both the data entered at the end of the queue and the data deleted at the top of the heap small pile).
We first complete the deletion of the data at the top of the heap, as shown in the following figure:
Secondly, the downward adjustment algorithm is used to make the heap of deleted data still a small heap. We first find the parent node and name it parent, find its corresponding left child and name it kid. The position of its right child is kid + 1. Select the smaller one of the left and right children and compare it with a[parent]. When a[parent] is larger, exchange the positions of a[parent] and a[kid], and move the position of parent to the position of kid. Repeat in turn.
Adjust downwards as follows:
void AdjustDown(int* arr, int size, int parent) {
assert(arr);
int kid = parent * 2 + 1;//find the child node
while (kid < size) {
// find the smaller child node
if (kid + 1 < size & amp; & amp; arr[kid + 1] < arr[kid]) {
kid ++ ;
}
if (arr[kid] < arr[parent]) {
Swap( &arr[kid], &arr[parent]);
parent = kid;
kid = parent * 2 + 1;
}
else
{
break;
}
}
}
When we want to arrange an array into a small heap, we only need to use a loop to do it
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
Heap sort implementation
Understanding heap sort is easier when we have the basics of scaling up and scaling down algorithms.
Before heap sorting, we need to arrange the array into heaps (large heaps or small heaps), here we can use the upward adjustment or downward adjustment algorithm. Secondly, suppose we want to sort in ascending order, at this time we need to build a large pile. Exchange the position of the elements at the top of the heap and the elements at the end of the team, and then adjust the n-i (i=0,1,2~n-1) elements in front of the heap downwards (some people may wonder why the downward adjustment algorithm is used here, Instead of the upward adjustment algorithm? We can pay attention to the upward adjustment algorithm function void AdjustUp(int* a, int kid) and the downward adjustment function void AdjustDown(int* arr, int size, int parent) The kid in the upward adjustment algorithm function is every Insert the element once, the position of the last element in the array. The size parameter in the downward adjustment algorithm function is the number of elements in the heap. Here, each exchange of positions between the top of the heap and the tail of the queue means that the sorting of a number has been completed. We think that there is one less data in the heap, and here only the downward adjustment algorithm can adapt to the change of conditions here.), so that it still becomes a large heap. Repeat in order to complete the ascending sort.
void HeapSort(int* a, int n) {
//build a heap, method 1
//for (int i = 1; i < n; i ++ ) {
// AdjustUp(a, i);//Upward adjustment algorithm
//}
//Build method 2
for (int i = (n - 1 - 1) / 2; i >= 0; i--) {
AdjustDown(a, n, i);//Down adjustment algorithm
}
//sort
for (int j = n - 1; j > 0; j--) {
Swap( &a[0], &a[j]);
AdjustDown(a, j, 0);
}
}
int main() {
int a[] = { 2,3,6,7,5,11,8,9,10,12,14 };
int sz = sizeof(a) / sizeof(a[0]);
HeapSort(a, sz);
for (int i = 0; i < sz; i ++ ) {
printf(" %d ", a[i]);
}
return 0;
}
When using heap sorting, if you want to sort in ascending order, you need to build a large heap. If you sort in descending order, you need to build a small heap.