“This is the third day of my participation in the Gwen Challenge in November. Check out the details: The last Gwen Challenge in 2021.”

Focus on the public account [High-performance architecture exploration], reply [PDF], free access to classic computer books

Hello, I’m Yule.

Very simple. <<Is this the simplest (and most surprising) sorting algorithm ever? >>, read the contents of the inside, quite interesting, so today with the help of this article, share to you.

algorithm

Below I look at the pseudo-code implementation, before proving the correctness of the sorting algorithm, we temporarily named it as ICan ‘tBelieveItCanSort😁.

I believeitcansort (A[1..n]) {for I = 1 to N do for J = 1 to N do if A[I] < A[J] then swap(A[I], A[j])}Copy the code

What’s your first reaction to seeing the code above? Do you think, like ME, that

❝

This is a wrong bubble sort algorithm, but the range of the second line is wrong, the third line swap conditions are reversed 😁.

❞

Here is the pseudocode for bubble sort:

BubbleSort(A[1..n]) {
  for i = 1 to n do
    for j = i + 1 to n do
      if (A[i] > A[j]) then
        swap(A[i], A[j]);
}
Copy the code

❝

For the convenience of subsequent description, I will collectively call this algorithm “new algorithm”.

❞

From the realization of the above two pseudo-codes, the differences between the new Algorithm ICan ‘tBelieveItCanSort and the traditional bubble sorting algorithm BubbleSort are as follows:

  • In the new algorithm, the inner loop is for j = 1 to n do

    In the traditional bubble algorithm, the inner loop is for j = I + 1 to n do

  • In the new algorithm, the exchange condition is if A[I] < A[j] then

    In the traditional bubble sorting algorithm, the exchange condition is if A[I] > A[j] then

Ok, let’s get back to the point and go back to the new algorithm. In order to make it easier for you to read, we will paste the pseudo-code of the new algorithm again:

I believeitcansort (A[1..n]) {for I = 1 to N do for J = 1 to N do if A[I] < A[J] then swap(A[I], A[j])}Copy the code

Regardless of whether the algorithm is correct or not, the code above gives us A first impression of being sorted in descending order because it does the switching when A[I] < A[j]. But in fact, when you look at the results of the code run, it does appear to be in ascending order.

The proof is given below.

prove

The correctness of this algorithm will be proved by mathematical induction.

Assuming Pᵢ is the array obtained after I loops (1 ≤ I ≤ n), then the former I term is already in ascending order, i.e. A[1] ≤ A[2] ≤.. ≤ A[I].

To prove that the algorithm is correct, it is only necessary to prove that P is true for any [I + 1..n].

According to mathematical induction, as long as we prove that P₁ holds, assuming that Pᵢ holds, then prove that Pi+1 also holds, the proposition can be proved.

P₁ is obviously correct, and this step is no different from the descending order of the normal bubble algorithm. After the first loop, A[1] is the largest element of the entire array.

And then we assume that Pᵢ is true, and then we prove that Pi+1 is true.

Now we begin to prove the correctness of the new algorithm 😁.

First suppose there is a subscript K:

❝

First, if A[k] (k between 1 and I) satisfies the smallest number A[k] > A[I +1], then A[k −1]≤A [I +1] (k≠1).

If A [I +1] is greater than or equal to A [I], then such A k does not exist, so let k= I +1.

❞

Now, consider the following scenarios:

  • 1 ≤ j ≤ k−1 At this time, since A[1.. I] is an increasing order and A[k] is the smallest number that A[k] > A[I +1], A[j] < A[I +1], no element exchange occurs.

  • K ≤ j ≤ I (obviously, this step is not entered when k = I +1)

    As A[J] > A[I +1], there will be element exchange after each comparison.

    We use A [] and A ‘[] to represent the exchange of before and after switching elements, so A [I + 1) = A [k], A’ [k] = A (I + 1).

    After A series of swaps, the largest element is finally placed in position A[I +1], the original A[I +1] becomes the largest element, and A[k] is inserted with an element whose size is between the original A[k] and A[k-1].

  • I plus 1 is less than j is less than n

    Since the largest element has been swapped into the previous I +1 element, there is no element swap.

After a series of conditions above, finally, P is the result after the execution of the ascending sorting algorithm.

❝

Since the inner and outer loops are exactly the same, this algorithm is arguably the simplest sorting algorithm.

❞

To optimize the

From the above proof process, we can find that, except for the cycle I =1, the part after j=i-1 in the rest of the cycle is completely invalid, so we can omit this part and get the simplified algorithm.

I believeitcansort (A[1..n]) {for I = 2 to N do for J = 1 to I-1 do if A[I] < A[J] then swap(A[I], A[j])}Copy the code

contrast

But from the point of view of the code, the new algorithm looks like a variation of the bubble algorithm, but from the above proof, the new algorithm is actually an insertion algorithm.

The following is a simulation diagram of the new algorithm:

The new algorithm

The following is a simulation diagram of the bubble algorithm:

Bubble sort

implementation

The code implementation is relatively simple, as follows:

#include <algorithm> #include <iostream> #include <vector> void SimplestSort(std::vector<int> &v) { for (int i = 0; i < v.size(); ++i) { for (int j = 0; j < v.size(); ++j) { if (v[i] < v[j]) { std::swap(v[i], v[j]); }}}} int main () {STD: : vector < int > v = {9, 8, 1, 3, 2, 5, 4, 7, 6}; SimplestSort(v); for (auto item : v) { std::cout << item << std::endl; } return 0; }Copy the code

Output result:

1, 2, 3, 4, 5, 6, 7, 8, 9Copy the code

A simpler algorithm?

After reading this paper, IT occurred to me that there was a simpler and easier algorithm to understand, which we will call the sleep algorithm.

Thought:

❝

Construct n threads that correspond to these n numbers. After initialization, the thread goes to sleep, waits for the corresponding number of time units to wake up, and then outputs its corresponding number. So that the smallest number corresponds to the first thread to wake up, this number is the first to be printed. When all threads wake up, the sorting is done.

❞

For example, for a set of numbers like [4,2,3,5,9], create five threads, each sleeping 4s, 2s, 3s, 5s, 9s. After these threads wake up, they can report their corresponding numbers. So when all the threads wake up, the sorting is done.

The idea is simple, but the problem is that the number of threads created depends on the number of elements in the array to be sorted, so this algorithm is just one idea for now.

conclusion

It’s not necessarily the simplest sorting algorithm ever, but it’s the most amazing sorting algorithm. The magic is that the greater-than and less-than signs are reversed to get the right answer.

In fact, there’s another simple way to think about this algorithm, which is to bubble twice, the first time to non-increasing sort, the second time to non-decreasing sort, so it’s a negative and a negative make a positive, so I get the right answer.

Due to the time complexity of the “simplest” algorithm is too high, it is only a realization of the idea, but also to open up the idea, the actual use, or recommended to use the ten classic sorting algorithm.

That’s it for today. See you next time.