The possibilities of improving sorting time parameters through preprocessing by stochastic sorting were investigated. The hypothesis that preprocessing by stochastic sorting can significantly improve the time efficiency experimentally confirmed. Sorting with different computational complexity is accepted as classical sorting algorithms: shaker sorting with computational complexity O(n2), insertions O(n2), Shell O(n·(log n)2) ... O(n3/2), fast with optimization of ending sequences O(n·log n). The greatest effect is obtained when performing comparisons using stochastic sorting in the amount of 160 percent of the array's size. Indicators of the exchange efficiency of two elements and a series of comparisons with exchanges are proposed, which made it possible to establish the greatest efficiency of data preprocessing by stochastic sorting when one element for comparison is selected from the first part of the array, and the other from the second. For algorithms with a computational complexity of O(n2) the improvement in time efficiency reached 70-80 percent. However, for Shell sort and quick sort, the stochastic presort has no positive effect, but instead increases the total sorting time, which is apparently due to the initial high efficiency of these sorting methods. The hypothesis about increasing the time efficiency of quick sorting combined with sorting by insertions on the final sections due to the use of preliminary stochastic processing of such sections has not been confirmed. However, according to the experiment, the recommended size of the array was established, at which it is necessary to switch to insert sorting in the modified quick sort. The optimal length of the ending sequences is between 60 and 80 elements. Given that algorithm time efficiency is affected by computer architecture, operating system, software development and execution environment, data types, data sizes, and their values, time efficiency indicators should be specified in each specific case. Sorting, stochastic sorting, algorithm, time efficiency, experiment
sorting was investigated.
The possibility of improving the time parameters of sorting by preprocessing with stochastic
Stochastic algorithms are very useful in solving complex optimization tasks, for example, in
finding the roots of complex equations [
Stochastic sorting consists in a cyclic comparison of randomly selected two elements of the array and, if necessary, their permutation. The stochastic sorting method, like any method, is capable for
2022 Copyright for this paper by its authors. modifications related to the selection of elements for comparison, the distribution law of random numbers, etc.
Combination or hybridization of sorting algorithms is a well-known approach [
In most cases, sorting algorithms are used with some regularity in relatively stable conditions: software and hardware, array size and filling, etc. So there is an opportunity to select the most effective algorithms or their combinations.
Of course, stochastic sorting cannot be applied independently, due to the lack of a termination condition and theoretical looping. However, a hypothesis was put forward about its effectiveness as a preliminary preparation of the array for further sorting by one of the classic methods. Experiments were carried out in order to confirm or refute the proposed hypothesis.
Sorts of different computational complexity [
For a long time [
Since the time characteristics of algorithms are largely affected by the hardware and software environment for their implementation and execution (multitasking, command execution pipeline, prepipeline optimization of command execution, branch prediction in the pipeline, caching of commands and data, and a number of others), the time of commands depends significantly non-linearly on specified environments. Comparative studies of sorting efficiency in various software and hardware environments are not the goal of this work. We have performed an experimental study on a laptop in the Windows 10 operating system using the Delphi development environment.
Sorting algorithms are quite universal, but they have their own effective application sphere. In this
regard, the search for new sorting algorithms and improvements to existing ones continues. The
"2 mm" algorithm [
Separately, we note algorithm hybridization in order to improve time efficiency. An experiment
was carried out in [
As is known, “efficient implementations generally use a hybrid algorithm, combining an
asymptotically efficient algorithm for the overall sort with insertion sort for small lists at the bottom
of a recursion” [
There is also ongoing research into the effectiveness of sorting algorithms. Additional quality
indicators are offered. Thus, in [
Work is being done to automate the development of sorting algorithms, such as those based on
logic and combinatorics [
Software. The experiments were carried out on the Windows 10 operating system. In the Delphi 10.3 environment, a 32-bit window program was created that implements sorting algorithms with various variants of random permutations.
The following measures were used to stabilize the results and significantly reduce the random factors that affect the execution time of the algorithms: • a separate thread was used to run a series of experiments; • the program was compiled in code optimization (release) mode; • the program was executed outside of the development environment; • no other windowed programs running; • during the experiments, the network was turned off; • the cache was cleared prior to the time measurements.
Hardware. The experiments were performed on a laptop with the technical characteristics listed in the Table 1 and Table 2.
Data structures. Sorting was accomplished by preparing arrays of 4 byte integers. The sizes of the
arrays were depending on the sorting method – smaller for less efficient sortings. Memory for arrays
was allocated directly by the Windows operating system using VirtualAlloc [
The experiment's organization. The execution time of sorting the same array will be random with some variance due to the volatility of Windows operating system threads and hardware state.
The sorting time was calculated by averaging the mean and median time spent sorting the same data array M times. The address of the array in memory did not change, the data was copied from the original unsorted array before each measurement.
The CPU cache was cleared before performing a separate sorting (parallel measurement). The following techniques were used to accomplish this: • at least ten passes of sequential access to cells in a previously allocated memory area; •
sleep function call for 500 ms delay.
To estimate the required number of parallel measurements (previously denoted as M) that would give a stable mean and median sorting time, a preliminary experiment was performed. In order to do this, quicksort was used on the same dataset 500 times.
This experiment results (Figure 1 and Figure 2) demonstrated that approximately 100 parallel measurements for the same data set are adequate for estimating the mean and median sorting time. At the same time, the sorting time will be overestimated rather than underestimated, with a maximum deviation of 0.5% from the value for 500 parallel measurements. All of the data presented in this paper were obtained for 100 parallel measurements (for each type of sorting, amount of data, etc.).
Before carrying out the main part of the experiments, effectiveness of the swapping of elements was investigated for improve of the array ordering. The time indicators of the series of exchanges were not determined at this stage.
Two methods of selecting random elements for comparison (with possible subsequent exchange) were investigated.
In first method selected two evenly distributed numbers ranging from 0 to N −1. A pair of elements to be compared may be located anywhere in the array.
In the second, the first element of the pair is chosen using the uniform distribution law from 0 to N / 2 −1 and the second from N / 2 to N −1. As a result, a pair of elements in the array's different halves is formed.
For the experiment, an array of randomly mixed 105 integers ranging from 0 to 99999 was prepared. Elements for comparison were chosen by series of 1000 pairs in one test and 200 such tests were performed sequentially. Totally 2 105 or 2N comparisons. The following indicators were recorded for each series of comparisons: • the number of exchanges in the series; • the average efficiency of exchanges in the series; • the disorder of the array after the series of comparisons ended.
The number of permutations for the first and second methods is shown in Figure 3. The trend line (based on the exponential law) is also depicted.
In a series of 1000 comparison attempts, the initial number of exchanges is around 500 (Figure 3), after which it begins to decrease. Over a range of 200,000 comparisons, the first method reduces the number of exchanges to 280 and the second to 100. The number of exchanges performed decreases in both methods of element selection according to laws that are close to linear. With a large enough number of attempts, the number of completed exchanges tends to zero. In practice, this means determining not only the most efficient way to select elements for comparison, but also a reasonable number of comparisons with at least 100 exchanges for every 1000 attempts.
Note that in the first method, the exchange of elements is more often performed. However, in this case, an additional comparison is required to determine the order of the selected indices i and j ( i j , i j or i = j ). For the second method of index selection, it is guaranteed that i j .
The relative change in the position of the elements before and after the permutation to their final position (in the sorted array) is defined as the efficiency of the permutation of a pair of elements: e(i, j, N ) = | xi − i | − | xi − j | max(xi , N − xi ) where i, j – index of elements in array x ; N – number of elements in array. We take into account that the array element's value is also its index in the ordered array (due to the method of forming an unordered array proposed above).
The indicator e(i, j, N ) determines how close the element at index i will become to its final position in the ordered array x after it is moved to the position at index j .
It should be noted that this function gives the same range of values regardless of the number of elements N in the array x . The worst possible value is e(0,0, N ) = −1 at xi = 0 , and the best possible value is e(0, N, N ) = 1 at xi = N .
Exchange efficiency indicator E(i, j, N ) is averages values e(i, j, N ) and e( j,i, N ) for a pair of swapped elements:
E(i, j, N ) = e(i, j, N ) + e( j,i, N ) 2 100%.
The exchange efficiency for each element of the pair can be both positive and negative. The worstcase scenario is that both elements' positions worsened as a result of the exchange; the best-case scenario is that both elements' positions improved.
Figure 4 depicts the average exchange efficiency for the first and second methods of selecting elements for comparison. The trend line (according to the exponential law) is also shown. The average disorder of array elements for both methods is shown in Figure 5.
The second method is better on exchange efficiency if the number of previous comparisons exceeds 160% of the total number of array elements.
The results of experiments using the second method of exchange, in which the index values are chosen from the first and second halves of the sorted array, are shown below. This method is the most useful in practice because, even with a large number of comparisons ( 2N 3N ), it has lower overhead due to a smaller number of conditional transition operators.
A series of experiments were carried out to test the hypothesis regarding the efficacy of stochastic sorting as array preprocessing prior to the application of the classic sorting algorithm. First, sorting with computational complexity O(n2 ) was considered: insertion sort and shaker sort.
The size of sorted array was of 103 , 104 , and 105 elements alternately. The sorting time was averaged by 100 parallel measurements were taken. In stochastic sorting, the number of comparisons varied from 0,5N to 5N with a step of 0,5N .
The results of the experiments are shown in Figure 6 and Figure 7. Efficiency was calculated as Ef = tклас tстох + tклас2
−1 100%.
where tклас is the time of classical sorting without preprocessing; tстох – stochastic sorting time; tклас2 is the same classic sorting, but after stochastic.
If the volume of the array is greater than 104 elements, the number of pairs for stochastic ordering should be in the range 3N 4N . The time spent sorting can be reduced by 70-80% using the methods considered.
The maximum efficiency for small size arrays (less than 104 element) is approximately 25-40% and is achieved after stochastic ordering of approximately 2N 2,5N pair. The efficiency then reaches a plateau (shaker sorting) or starts to decline (insert sorting).
A similar series of experiments was conducted for Shell sorting with a computational complexity of O(n (log n)2 ) ... O(n3/2 ) and quick sorting – O(n log n) . However, for these sortings the preordering of randomly selected pairs of elements no longer have a positive efficiency. On the contrary increases the total sorting time, which is obviously explained by the initial high efficiency of these sorting methods.
In subsequent experiments, the quicksort implementation assumes that end sections of a certain
length will be sorted by insertion sort. This type of sorting outperforms fast sorting with small
amounts of data [
The efficiency of applying preprocessing by stochastic sorting of the final parts of the array before using insertion sorting is of interest.
A series of experiments were carried out to determine the optimal value at which the transition from recursive calls to insertion sorting should occur. Quicksort was used to sort an array of 2 106 elements without end-section optimization and an array of 16 to 160 elements with a step of two. In each case, 100 parallel measurements were taken, and the results were averaged. The average time on sorting was compared. Without optimization, the quicksort time was 212.3 ms. Figure 8 depicts the time on sorting with optimization at various sizes of the final section. The optimal length of the final section is between 60 and 80 elements. This quicksort parameter was assumed to be 70 in subsequent experiments. Quicksorting with two components and inserts reduces quicksort time by about 20%.
In subsequent experiments, an attempt was made to improve the efficiency of quick sort by performing stochastic sorting before insertion sorting at the end sections. An assessment of the distribution of the lengths of the final sections was previously performed in order to accomplish this; 70 elements were chosen as the maximum length of the final section. Figure 9 depicts distribution of the arrays size sorted at the final sections. Approximately 80% are arrays with 2 to 30 elements, and the remaining 20% are arrays with 31 to 70 elements.
Experiments have shown that using random permutations to sort the final sections has no positive effect. The very short lengths of the end sections (2…30 elements in 80% of cases) explain this. As previously demonstrated, the effectiveness of stochastic sorting is most significant on large arrays with 104 elements or more.
The experiments confirmed the hypothesis that there is a significant improvement in the time efficiency of classical sorting with time efficiency O(n2 ) using stochastic preprocessing compared to the same classic without preprocessing.
The hypothesis about the possibility of increasing the time efficiency of quicksort by preprocessing small final parts of the array with stochastic sorting before switch to insert sort was not confirmed.
However, during the experiment, the recommended of the subarray size was determined, at which the two-component quick and insertion sort must be switched to the second component - insertion sort.
Any sorting algorithm has advantages and disadvantages, and the programmer must choose based on the task requirements. In some cases, using class O(n log n) sorts is less efficient than using class O(n2 ) . This could be due to hardware limitations, array filling specifics, the law of the array's value distribution, data types, and their representation in the RAM. Pre-processing with a stochastic algorithm in these cases may improve their time efficiency.
Because algorithm time efficiency is affected by computer architecture, operating system, software development and execution environment, data types, data volumes, and their values, time efficiency indicators should be determine on a case-by-case basis.