Solomon's Sort
Have a nice New Year!
In the treasury of exotic sorting methods I will propose another one, a bit peculiar, but promising decent speed with good random data.
Let there be a set N of n positive integers from 1 to n .
It is self-evident that it is necessary to have n cells to store n numbers. Regardless of the order in which the numbers will be written.
')
Source array
It is easy to imagine that it is enough to simply replace an unordered set of N by an ordered (ascending, or descending), writing the ordered set to the place of an unordered.
Ordered array
In the same way, it is possible to “sort” sets of numbers (we restrict ourselves to positive integers) satisfying the condition n max -n min = n .
Consider a more difficult case.
Let the set N (again, positive integers) be such that n max -n min > n , and all the numbers n (i) in the set are different.
To sort this set, you need:
1) find n max , n min
2) calculate the delta d = (n max -n min ) / n
3) for each n (i) (we will call the following procedure conditionally “stone scattering”):
3a) calculate the index indx = (n (i) -n min ) / d + 1 (since the calculations are also assumed in integers, one is added to compensate for rounding and exclude the zero index)
The numbers n (i) and indx indices aka the places where these numbers should stand.
3b) in the array Indxs “indexes” prepared in advance, filled with zeros, we increment the cell with the index obtained in the previous step
3c) read the resulting value
3d) multiply it by n and add it to the index, write the number n (i) at this address in the array N new
If identical indices are encountered, we write n (i) to the array N new , not side by side, but at the bottom.
4) then proceed to the "collection of stones"
Put i = 1 and successively read the array of indxs indices while i ≤ n
4a) if Indxs (i) = 0, go to the next i
4b) if Indxs (i) = 1, read the number from the array N new , output it to the sorted array, go to the next i
4c) if Indxs (i) = 2, read the numbers from N new written “vertically”, compare them and print first the smaller, then the larger, go to the next i
4d) if Indxs (i) = 3, read 3 numbers, find the minimum among them, display it and exclude it from the list, then compare the two remaining ones and output them already.
4e) for Indxs (i) = 4, all the same, first we find the minimum of four, delete it, then do the same for index 3.
4e) if Indxs (i) is greater than 4, call the algorithm recursively.
Sorted array
Let's try to estimate the number of operations.
The search for the minimum and maximum need one pass - n operations.
There are also n operations for “throwing stones”.
"Collecting stones" at a cost depends on the input data. In this case, you need n copies and 3 operations to compare a pair of numbers.
When testing on sets with n = 10,000, obtained from random.org (the resource does not give more than 10,000 numbers in one set), the algorithm shows the following statistics:
When n max = 10000. All indices = 1, sorting is done in 3 passes through the array.
When n max = 11000. Zeroes are almost half: 4547, units 906, twos: 4547, triples or more: 0 The same three passes, plus almost half of the n comparisons of 2 numbers.
With n max = 21000 Zeroes: 3967 Ones: 2845 Twos: 2409 Threes: 779 Fours: 0
With n max = 31000 Zeroes: 3881 Ones: 3134 Twos: 2197 Threes: 680 Fours: 108 More_than_four: 0
With n max = 101000 max in index: 6 Zeroes: 3729 Ones: 3541 Twos: 1923 Threes: 643 Fours: 139 More_than_four: 25
only 25 calls of the second iteration.
Intuitively, in the worst case, n / 5 iterations will be performed.
On average, offhand, the number of operations is about 4n
This sorting method belongs to the sorting group without comparisons and is an intermediate version between pocket and sorting with counting.
The main problem of sorting by counting is that the need to additionally sort values ​​that fall into one cell has significance when the number of numbers in a cell is more than 4.
But, first, we have a good handicap at the expense of units and pairs of numbers.
Secondly, the number of bursts is usually relatively small, less than one percent.
Thirdly, already at the second iteration, bursts are very well practiced. In addition, the restriction on the absence of repetitions in the input data is automatically lifted. If we encounter a burst of the same values, then for it a delta d = (n max -n min ) / n = 0 and we can safely copy the entire burst to the output.
The problem of the applicability of this sorting method not only for positive integers is also completely solvable.
Of course, this method requires more running and identifying pitfalls.
Benefits:
Speed, ease of understanding and programming.
Disadvantages:
Quite a lot of memory requirements, depending on the input data. What can you try to compensate for the more rational organization of the array N new . In any case, the memory needs at least 3n.
UPD:
Test Fort code on GitHub
In the treasury of exotic sorting methods I will propose another one, a bit peculiar, but promising decent speed with good random data.
Let there be a set N of n positive integers from 1 to n .
It is self-evident that it is necessary to have n cells to store n numbers. Regardless of the order in which the numbers will be written.
')
Source array
| 3 | five | 2 | one | eight | four | 7 | 6 | 9 | ten |
It is easy to imagine that it is enough to simply replace an unordered set of N by an ordered (ascending, or descending), writing the ordered set to the place of an unordered.
Ordered array
| one | 2 | 3 | four | five | 6 | 7 | eight | 9 | ten |
In the same way, it is possible to “sort” sets of numbers (we restrict ourselves to positive integers) satisfying the condition n max -n min = n .
Consider a more difficult case.
Let the set N (again, positive integers) be such that n max -n min > n , and all the numbers n (i) in the set are different.
| thirty | 55 | 21 | 17 | 82 | 46 | 79 | 63 | 94 | 108 |
To sort this set, you need:
1) find n max , n min
2) calculate the delta d = (n max -n min ) / n
3) for each n (i) (we will call the following procedure conditionally “stone scattering”):
3a) calculate the index indx = (n (i) -n min ) / d + 1 (since the calculations are also assumed in integers, one is added to compensate for rounding and exclude the zero index)
The numbers n (i) and indx indices aka the places where these numbers should stand.
| thirty | 55 | 21 | 17 | 82 | 46 | 79 | 63 | 94 | 108 |
| 2 | five | one | one | 7 | four | 7 | five | 9 | ten |
3b) in the array Indxs “indexes” prepared in advance, filled with zeros, we increment the cell with the index obtained in the previous step
| 2 | one | 0 | one | 2 | 0 | 2 | 0 | one | one |
3c) read the resulting value
3d) multiply it by n and add it to the index, write the number n (i) at this address in the array N new
If identical indices are encountered, we write n (i) to the array N new , not side by side, but at the bottom.
| 21 | thirty | 46 | 55 | 82 | 94 | 108 | |||
| 17 | 63 | 79 |
4) then proceed to the "collection of stones"
Put i = 1 and successively read the array of indxs indices while i ≤ n
4a) if Indxs (i) = 0, go to the next i
4b) if Indxs (i) = 1, read the number from the array N new , output it to the sorted array, go to the next i
4c) if Indxs (i) = 2, read the numbers from N new written “vertically”, compare them and print first the smaller, then the larger, go to the next i
4d) if Indxs (i) = 3, read 3 numbers, find the minimum among them, display it and exclude it from the list, then compare the two remaining ones and output them already.
4e) for Indxs (i) = 4, all the same, first we find the minimum of four, delete it, then do the same for index 3.
4e) if Indxs (i) is greater than 4, call the algorithm recursively.
Sorted array
| 17 | 21 | thirty | 46 | 55 | 63 | 79 | 82 | 94 | 108 |
Let's try to estimate the number of operations.
The search for the minimum and maximum need one pass - n operations.
There are also n operations for “throwing stones”.
"Collecting stones" at a cost depends on the input data. In this case, you need n copies and 3 operations to compare a pair of numbers.
When testing on sets with n = 10,000, obtained from random.org (the resource does not give more than 10,000 numbers in one set), the algorithm shows the following statistics:
When n max = 10000. All indices = 1, sorting is done in 3 passes through the array.
When n max = 11000. Zeroes are almost half: 4547, units 906, twos: 4547, triples or more: 0 The same three passes, plus almost half of the n comparisons of 2 numbers.
With n max = 21000 Zeroes: 3967 Ones: 2845 Twos: 2409 Threes: 779 Fours: 0
With n max = 31000 Zeroes: 3881 Ones: 3134 Twos: 2197 Threes: 680 Fours: 108 More_than_four: 0
With n max = 101000 max in index: 6 Zeroes: 3729 Ones: 3541 Twos: 1923 Threes: 643 Fours: 139 More_than_four: 25
only 25 calls of the second iteration.
Intuitively, in the worst case, n / 5 iterations will be performed.
On average, offhand, the number of operations is about 4n
This sorting method belongs to the sorting group without comparisons and is an intermediate version between pocket and sorting with counting.
The main problem of sorting by counting is that the need to additionally sort values ​​that fall into one cell has significance when the number of numbers in a cell is more than 4.
But, first, we have a good handicap at the expense of units and pairs of numbers.
Secondly, the number of bursts is usually relatively small, less than one percent.
Thirdly, already at the second iteration, bursts are very well practiced. In addition, the restriction on the absence of repetitions in the input data is automatically lifted. If we encounter a burst of the same values, then for it a delta d = (n max -n min ) / n = 0 and we can safely copy the entire burst to the output.
The problem of the applicability of this sorting method not only for positive integers is also completely solvable.
Of course, this method requires more running and identifying pitfalls.
Benefits:
Speed, ease of understanding and programming.
Disadvantages:
Quite a lot of memory requirements, depending on the input data. What can you try to compensate for the more rational organization of the array N new . In any case, the memory needs at least 3n.
UPD:
Test Fort code on GitHub
Source: https://habr.com/ru/post/208088/
All Articles