Data structure – sorting algorithm (merge && non-comparison)

Directory

1. Merge sort

1.1 Basic idea

1.2 Implementation of Merge Sort Recursive Mode

1.3 Implementation of non-recursive merge sort

1.4 Summary of features of merge sort

2. Counting and sorting

2.1 Basic idea of counting sort

2.2 Implementation of counting sort

2.3 Summary of the characteristics of counting sort:


1. Merge sort

1.1 Basic idea

Merge sort (MERGE-SORT) is an effective sorting algorithm based on the merge operation, which is a very typical application of divide and conquer (Divide and Conquer). Combine the ordered subsequences to obtain a completely ordered sequence; that is, first make each subsequence in order, and then make the segments of the subsequences in order. Merging two sorted lists into one sorted list is called a two-way merge. Merge sort core steps:

1.2 Implementation of Merge Sort Recursive Mode

Merge sort is equivalent to post-order traversal. At this time, the middle position can be found to control the merge interval

[begin, mid] [mid + 1, end], recurse until there is only one value, return the left and right intervals, merge the left and right intervals, return after completion, recurse the right interval, and return after the recursion, merge the left and right intervals .

void _MergeSort(int* a,int begin,int end,int* tmp) {
if (begin >= end) {
return;
}
int mid = (begin + end) / 2;
_MergeSort(a, begin, mid, tmp);
_MergeSort(a, mid + 1, end, tmp);
//merge
int begin1 = begin, end1 = mid;
int begin2 = mid + 1, end2 = end;
int tmpPos = begin1;
while (begin1 <= end1 & amp; & amp; begin2 <= end2) {
if (a[begin1] > a[begin2]) {
tmp[tmpPos++] = a[begin2++];
}
else {
tmp[tmpPos++] = a[begin1++];
}
}
while (begin1 <= end1) {
tmp[tmpPos++] = a[begin1++];
}
while (begin2 <= end2) {
tmp[tmpPos++] = a[begin2++];
}
memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
}
void MergeSort(int* a, int n) {
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL) {
printf("malloc fail\\
");
exit(-1);
}
_MergeSort(a, 0, n - 1, tmp);

free(tmp);
}

1.3 Implementation of non-recursive merge sort

problem analysis:

Quicksort is similar to pre-order traversal, and the keyi value is processed first. Therefore, the data structure stack and queue can be used to record the subsequent intervals for non-recursive implementation. Since the keyi value is processed first, it does not pay attention to whether the left and right starting positions are recorded. Perform data processing on the left and right positions, and finally obtain an ordered sequence.

But for merge sorting, after popping the stack to obtain the starting position of the left and right sides of the sequence, after processing the left subsequence and the right subsequence, the original sequence still needs to be merged again, and at this time the original sequence no longer exists in the stack, so It is difficult to implement non-recursion with the help of data structures.

Solution:

At this time, the cycle can be used to control the initial sequence mode for processing. At this time, it is necessary to control the two sets of data. If the first set reaches the boundary, the next set of data will cross the boundary, and an out-of-bounds access error will occur.

void MergeSortNonR(int* a, int n) {
assert(a);
int* tmp = (int*)malloc(sizeof(int) * n);
assert(tmp);
int gap = 1;
while (gap < n) {
for (int i = 0; i < n; i + = 2 * gap) {
int begin1 = i, end1 = i + gap - 1;
int begin2 = i + gap, end2 = i + 2 * gap - 1;
// fix border
if (end1 >= n) {
end1 = n - 1;
//begin2 and end2 are corrected to a non-existing space
begin2 = n;
end2 = n - 1;
}
else if (begin2 >= n) {
begin2 = n;
end2 = n - 1;
}
else if (end2 >= n) {
end2 = n - 1;
}
int tmpPos = begin1;
while (begin1 <= end1 & amp; & amp; begin2 <= end2) {
if (a[begin1] > a[begin2]) {
tmp[tmpPos++] = a[begin2++];
}
else {
tmp[tmpPos++] = a[begin1++];
}
}
while (begin1 <= end1) {
tmp[tmpPos++] = a[begin1++];
}
while (begin2 <= end2) {
tmp[tmpPos++] = a[begin2++];
}
}
memcpy_s(a, sizeof(int) * n, tmp, sizeof(int) * n);
gap *= 2;
}
free(tmp);
}

1.4 Summary of features of merge sort

  1. The disadvantage of merging is that it requires O(N) space complexity, and the thinking of merging and sorting is more to solve the problem of external sorting in the disk.
  2. Time complexity: O(N*logN)
  3. Space complexity: O(N)
  4. Stability: Stable

2. Counting sort

2.1 Basic idea of counting sort

Counting sorting, also known as the pigeonhole principle, is a modified application of the hash direct addressing method. Steps:

1. Count the number of occurrences of the same element

2. Recycle the sequence to the original sequence according to the statistical results

3. Limitations:
1) If it is a floating point number or a string, it cannot be sorted
2) If the data range is large and the space complexity is high, it is not suitable
3) If you use absolute mapping, it is easy to waste space, and negative numbers are not easy to handle

2.2 Implementation of counting sort

Optimization, statistical minimum, subtracting the minimum value from the counted mapping position, can relatively reduce space waste, and can sort negative numbers at the same time

void CountSort(int* a, int n) {
assert(a);
int min = a[0], max = a[0];
for (int i = 1; i < n; i ++ ) {
if (a[i] < min) {
min = a[i];
}
if (a[i] > max) {
max = a[i];
}
}
int range = max - min + 1;
int* count = (int*)malloc(sizeof(int) * range);
assert(count);
memset(count, 0, sizeof(int) * range);
//count
for (int i = 0; i < n; i ++ ) {
count[a[i] - min] + + ;
}
// write back sort
int j = 0;
for (int i = 0; i < range; i ++ ) {
while (count[i]--) {
a[j + + ] = i + min;
}
}
}

2.3 Summary of features of counting sort:

  • Counting sort is highly efficient when the data range is concentrated, but its scope of application and scenarios are limited.
  • Time complexity: O(MAX(N,range))
  • Space Complexity: O(range) bit job class
  • Stability: Stable

The knowledge points of the article match the official knowledge files, and you can further learn relevant knowledge algorithm skill treehome page overview 47268 people are learning systematically