Introduction to Parallel Sorting
What is a sorting algorithm
Sorting algorithms are the cornerstone of algorithms, and many algorithms are based on sorting algorithms, such as dichotomous search, discretization, and so on. This article is going to introduce one of the sorting algorithms, the subsumption sort, in detail.
Performance of Subsumption Sorting
The time complexity of the subsumption sort is stabilized at\(\mathcal{O}(n \log(n))\), is a sorting method with stability (i.e., the relative positions of the same elements remain unchanged). Therefore, in general, subsumption sorting is better than quick sorting. Subsumption is based on an idea called "divide and conquer", i.e. divide and conquer.
principle of merging and sorting (math.)
Below we use the1 9 2 7 6 5 8 4These 8 numbers are used to demonstrate subsumption sorting.
The subsumption sort is divided into two main parts, one for division and one for combination.
Step 1: Breakdown
For each sequence, takemid=(l+r)/2(rounding down), and then separately for the left ([l~mid]) right ([mid+1~r]) The two paragraphs are sorted.
And so on! If\(l = r\)That means there's only one number left, so there's no need for this paragraph, just go ahead.return。
Step 2: Consolidation
For this step, we need to merge two subsequences. Note that the two subsequences being merged must be ordered. This allows for a linear merge.
We define two "arrows"icap (a poem)jpoint to the beginning of each of the two sub-sequences, and define an array of "storage rooms".t, which is used to store lined up numbers, like this:
Then we compare the numbers pointed to by the two arrows, see which one is smaller, let it go into the "storage room", and move that arrow forward.
For example, in the picture above.\(1 < 4\)So it came to this:
Next.\(2 < 4\), so let the number pointed to by i enter the storage room and move forward.
Go on next, pay attention!\(7 > 4\), so to get 4 into the storage room, advancing then thej。
By analogy, please manually simulate the latter part, if not wrong, it should look like this after simulation:
How's it going? Did you simulate it correctly? Note that if one arrow goes to the end, the other arrow has to continue to the end! If you still do not understand can look at the code
code implementation
// a is the original sequence and t is the storage room.
int a[100],t[100].
void mergesort(int l,int r){
if (l == r) return; // if there is only one number there is no need to arrange it
int mid = (l + r) / 2; // take the middle point
mergesort(l,mid); // sort the left half of the number
mergesort(mid + 1,r); // sort right half
int tot = 0,i = l,j = mid + 1; // start merging, tot is the last occupied position in the cubicle
while (i <= mid && j <= r){
if (a[i] <= a[j]) t[++tot] = a[i++]; // if the number pointed to by i is small, then put it in the storage room
else t[++tot] = a[j++]; // otherwise let the number pointed to by j go into the storage room
}
while (i <= mid) t[++tot] = a[i++]; // put the rest into the storage room
while (j <= r) t[++tot] = a[j++]; // same as above
for (int k = 1;k <= tot;++k) a[l + k - 1] = t[k]; // put the storage back into the original sequence
}
Extended application: finding the number of inverse pairs
principle
Reverse order pairs, two numbers in an exponential column\(a_i > a_j\)besides\(i < j\). Using the subsumption sort we can start with\(\mathcal{O}(n \log(n))\)The time complexity of finding the number of inverse pairs in a sequence.
In the merging process, the subsumption sortiAlways less thanjAt this point, if the\(a_i > a_j\), indicating that a set of reverse-ordered pairs emerges, and because the two sequences being merged are ordered, the\(a_i\)The number that follows must also be greater than\(a_j\)Thereforeans += mid - i + 1The specific code is as follows:
code implementation
// a is the original sequence and t is the storage room.
int a[100],t[100],ans = 0;
void mergesort(int l,int r){
if (l == r) return; // if there's only one number there's no need to rank it
int mid = (l + r) / 2; // take the middle point
mergesort(l,mid); // sort the left half of the number
mergesort(mid + 1,r); // sort right half
int tot = 0,i = l,j = mid + 1; // start merging, tot is the last occupied position in the cubicle
while (i <= mid && j <= r){
if (a[i] <= a[j]) t[++tot] = a[i++];
else t[++tot] = a[j++],ans += mid - i + 1; // if a[j] is smaller, then a reverse-order pair was found
}
while (i <= mid) t[++tot] = a[i++]; // put the rest into storage
while (j <= r) t[++tot] = a[j++]; // same as above
for (int k = 1;k <= tot;++k) a[l + k - 1] = t[k]; // put the storage back into the original sequence
}