wonder! The most beautiful sorting algorithm in the world!

58 Shen Jian 2021-10-14 04:57:54

Go straight to the theme , In the world “ Most beautiful ” Sort algorithm , Only 6 That's ok .

void stooge_sort(int arr[], int i, int j){

         if (arr[i]>arr[j]) swap(arr[i], arr[j]);

         if (i+1>=j) return;

         int k=(j-i+1)/3;

         stooge_sort(arr, i, j-k);

         stooge_sort(arr, i+k, j);

         stooge_sort(arr, i, j-k);

}

《 Introduction to algorithms 》 In exercises “ Perfect sequencing ”, from Howard、Fine Wait for several professors to put forward , It's called “ Perfect sequencing ”, Because of its Code implementation , grace 、 Neat 、 beautiful .

The code is not easy to understand , Explain your ideas step by step .

887e43c0169458961a65f3598e4a8690.png

First , The parameter passed in by sorting is the array to be sorted arr[i, j];

3a8d124b4642c2048aebd63a919832f3.png

First step : Compare i And j The element of location , Decide whether to replace according to the sorting rules .

Voice over : Chestnut , Suppose the collation is from small to large .

After the replacement , Determine whether the sorting is over , When i and j Adjacent time , End of sort .

b14a79c1a3277531780f5aadb86057e3.png

The second step : take arr[i, j] Three equal parts ;

Voice over : The total number of elements is j-i+1.

7f7360ec80b8f60b84148443fc7960df.png

The third step : recursive arr Before 2/3 Half area .

8c7ddaf2153ccf7e73e11b38390bf5fa.png

Step four : recursive arr After 2/3 Half area .

af12989c22b6c6521a4e394098fa0f03.png

Step five : recursive arr Before 2/3 Half area .

End of sort .

Magic is not magic !!!

Look again. , Impressive, No ?

void stooge_sort(int arr[], int i, int j){

         if (arr[i]>arr[j]) swap(arr[i], arr[j]); // Compare

         if (i+1>=j) return; // Is it over?

         int k=(j-i+1)/3; // Three equal parts

         stooge_sort(arr, i, j-k); // front 2/3 Half area

         stooge_sort(arr, i+k, j); // after 2/3 Half area

         stooge_sort(arr, i, j-k); // front 2/3 Half area

}

But it is of no damn use , Except for the code , Perfect sorting is useless , Because it's a very slow algorithm .

It's easy to see from the code :

(1) When only 1 Element time , The perfect sort of time is also 1;

(2) When there is n Element time , The perfect sort is calculated by a constant , Plus three recursions , The amount of data per recursion is (2/3)*n;

namely , Its time Complexity recursion by :

T(1) = 1;

T(n) = 3T(2/3n) + 1;

Through recursive calculation method , The resulting , Perfectly sorted The time complexity is O(n^2.7), Than O(n^2) The order of is slow .

Proof of perfect ordering , Don't expand in the article . From the code, you can feel , adopt swap And triple recursion , On trend , Small elements move forward , Large elements will move back , Until sorting is complete .

Voice over : The quick sort process is partition+ Two recursions , It's also a small element moving forward , Big elements go back , Until sorting is complete .

I hope this minute , You have something to gain .

Architect's way - Share technical articles that can be implemented

Only 6 Perfect sorting of rows , Have you learned ?

Voice over : In the future, handwritten sorting of interview is no longer a problem .

Please bring the original link to reprint ,thank
Similar articles

2021-10-14