Sort by direct inclusion, just like sort by method simple choice, usually used for arrays that do not contain duplicate elements.
Sorting by this method is performed sequentially step by step. On k-th step, it is considered that the part of the array containing the first k– 1 element, already ordered, i.e. .
Next, you need to take k-th element and choose a place for it in the sorted part of the array such that after its insertion the order is not violated, that is, you need to find such that . Then you need to insert an element a(k) to the location found.
With each step, the sorted part of the array increases. To perform a complete sort, you need to run n– 1 step.
It remains to answer the question of how to search for a suitable place for the element X. Let's do the following: we will look at the elements located to the left X(that is, those that are already ordered), moving towards the beginning of the array. Items need to be viewed a(j), j changes from k– l to 1. Such browsing will end when one of the following conditions is met:
Found element that indicates the need for insertion X between and a(j).
The left end of the ordered portion of the array has been reached, so insert X in first place.
Until one of these conditions is met, we will shift the viewed elements by 1 position to the right, as a result of which space will be freed up in the sorted part under X.
The sorting technique is illustrated in Table 2:
Table 2 - Example of sorting using direct inclusion
The initially ordered sequence consists of the 1st element 9. The element A( 2) =5 is the first of the unordered sequence and 5< 9, поэтому ставится на его место, а 9 сдвигается вправо. Теперь упорядоченная последовательность состоит из двух элементов 5, 9. Элемент A( 3) =15 of the unordered sequence is greater than all elements of the ordered sequence, so it remains in its place and at the next step the ordered sequence consists of 5, 9, 15, and the element under consideration is 6. The process continues until the sequence becomes ordered.
shaker sort
The bubble method allows for three simple improvements. First, if no exchange has been made at some step, then the algorithm can be terminated. Secondly, you can remember the smallest value of the array index, for which permutations were performed at the current step. Obviously, the upper part of the array up to the element with this index has already been sorted, and at the next step, you can stop comparing the values of neighboring elements when such an index value is reached. Thirdly, the bubble method works unequally for "light" and "heavy" values. A light value gets to the right place in one step, and a heavy one goes down towards the right place by one position at each step.
The ShakerSort method is based on these observations. When it is applied, the direction of sequential browsing changes at each next step. As a result, at one step the next lightest element "floats up", and at the next step the next heaviest element "sinks". An example of a shaker sort is shown in Table 3.
Table 3 - An example of a shaker sort
Sorting an Array Using Inclusions with Decreasing Distances (Shell's Method)
D. Shell proposed an improvement in sorting using direct inclusion.
The idea of the method: all elements of the array are divided into groups in such a way that each group includes elements spaced from each other by a certain number of positions L. The elements of each group are sorted. After that, all the elements are again combined and sorted into groups, while the distance between the elements decreases. The process ends after the ordering of elements with a distance between them equal to 1 is carried out.
An example of sorting by the Shell method is shown in Table 4.
Table 4 - Example of sorting by the Shell method
First, consider the option when the initial value L is equal to half the number of elements in the array, and each subsequent value is half the previous one. Note that elements that are separated by a step size are exchanged. If no exchange occurs when comparing 2 elements, then the places of the compared elements are shifted to the right by one position. If the exchange has taken place, then the corresponding compared elements are shifted by L.
Split Sort (Quick Sort)
The partition sort method was proposed by Charles Hoare. This method is a development of the simple exchange method and is so effective that it has become known as the quicksort method - "Quicksort".
The main idea of the algorithm is that randomly some element of the array is selected x, after which the array is scanned from the left until an element is encountered a(i) such that a(i) > x and then the array is searched from the right until an element is encountered a(i) such that a(i)< x. These two elements are swapped, and the process of viewing, comparing, and exchanging continues until we reach the element x. As a result, the array will be split into two parts - the left one, in which the key values will be less than x, and the right one with key values greater than x. The process then continues recursively for the left and right parts of the array until each part contains exactly one element. Recursion can be replaced by iterations if you remember the corresponding array indexes.
The process of sorting an array by the fast method is presented in Table 5.
Table 5 - Example of quick sort
Sorting is the arrangement of data in memory in a regular manner according to the selected parameter. Regularity is considered as an increase (decrease) in the parameter value from the beginning to the end of the data array.
When processing data, it is important to know the information field of the data and its placement in the machine.
Distinguish between internal and external sorting:
Internal sort - sort in random access memory;
External sorting - sorting in external memory.
If the records to be sorted take up a large amount of memory, moving them is expensive. In order to reduce them, sorting is done in key address table, that is, they do a permutation of pointers, and the array itself does not move. This - address table sorting method.
When sorting, the same keys may occur. In this case, it is desirable after sorting to arrange the same keys in the same order as in source file. This - stable sort.
We will consider only sorts that do not use additional RAM. Such sorts are called "at the same place".
Sorting efficiency can be considered according to several criteria:
Time spent on sorting;
The amount of RAM required for sorting;
The time spent by the programmer writing the program.
We single out the first criterion. The equivalent of the time spent on sorting can be considered number of comparisons And number of movements when sorting.
The order of the number of comparisons and moves during sorting lies within
From O (n log n) to O (n 2);
O(n) is an ideal and unattainable case.
There are the following sorting methods:
Strict (direct) methods;
Improved methods.
Strict methods:
Direct connection method;
Direct selection method;
direct exchange method.
The efficiency of strict methods is about the same.
Direct Inclusion Sort
Elements are mentally divided into ready-made sequence a 1 ,...,a i-1 and the original sequence.
At each step, starting from i = 2 and increasing i each time by one, from the original sequence is extracted i-th element and shifted to the finished sequence, while it is inserted in the right place.
The essence of the algorithm is as follows:
for i = 2 to n
X = a(i)
We find a place among a (1) ... a (i) to include x
next i
There are two direct inclusion sorting algorithms. First - no barrier
Barrier-Free Direct Inclusion Sorting Algorithm
for i = 2 to n
X = a(i)
For j = i - 1 downto 1
If x< a(j)
Then a(j + 1) = a(j)
Else go to L
endif
Next j
L: a(j + 1) = x
next i
return
The disadvantage of the above algorithm is a violation of the structured programming technology, in which it is undesirable to use unconditional jumps. If the inner loop is organized as while loop, then it is necessary to set up a “barrier”, without which, with negative values of the keys, a loss of significance and a “freeze” of the computer occur.
Barrier Direct Inclusion Sorting Algorithm
for i = 2 to n
X = a(i)
A(0) = x (a(0) - barrier)
J = i - 1
While x< a(j) do
A(j+1) = a(j)
J = j - 1
Endwhile
A(j+1) = x
next i
return
Efficiency of the Direct Inclusion Algorithm
The number of key comparisons Ci at the i-th screening is at most i-1, at least - 1; if we assume that all permutations of N keys are equally likely, then the average number of comparisons = i/2. The number of transfers is Mi=Ci+3 (including the barrier). The minimum estimates occur in the case of an already ordered initial sequence of elements, while the worst estimates occur when they are initially arranged in reverse order. In a sense, sorting by inclusion exhibits truly natural behavior. It is clear that the above algorithm describes the stable sorting process: the order of elements with equal keys remains unchanged.
The number of comparisons in the worst case, when the array is sorted in the opposite way, C max = n (n - 1) / 2, i.e. - O (n 2). The number of permutations M max = C max + 3(n-1), i.e. - O (n 2). If the array is already sorted, then the number of comparisons and permutations is minimal: C min = n-1; Mmin = =3(n-1).
Sort by direct exchange (bubble sort)
This section describes a method where the exchange of two elements is the most characteristic feature of the process. The direct exchange algorithm outlined below is based on comparing and changing places for a pair of adjacent elements and continuing this process until all elements are ordered.
We iterate through the array, each time shifting the smallest element of the remaining sequence to the left end of the array. If we consider arrays as vertical rather than horizontal constructions, then the elements can be interpreted as bubbles in a vat of water, with the weight of each corresponding to its key. In this case, with each pass, one bubble rises, as it were, to a level corresponding to its weight (see illustration in the figure below).
C min = n - 1, order O(n),
and no movement at all.
Comparative analysis of direct sorting methods shows that the exchange "sorting" in its classical form is a cross between sortings using inclusions and using selections. If the above improvements are made to it, then for sufficiently ordered arrays, bubble sort even has an advantage.
This method is commonly known as "bubble sort".
Direct Exchange Method Algorithm
for j = n to i step -1
if a(j)< a(j - 1) then
In our case, we got one pass “idle”. In order not to view the elements once again, and therefore to make comparisons, spending time on this, you can enter the checkbox fl, which remains in the value false, if during the next pass no exchange will be made. In the algorithm below, additions are marked in bold.
fl = true
if fl = false then return
fl=false
for j = n to i step -1
if a(j)< a(j - 1) then
fl = true
An improvement to the bubble sort is the shaker sort, where after each pass the direction is reversed in an inner loop.
Efficiency of the Direct Exchange Sort Algorithm
Number of comparisons C max = n(n-1)/2 , order O(n 2).
The number of movements M max \u003d 3C max \u003d 3n (n-1) / 2, the order of O (n 2).
If the array is already sorted and the flag algorithm is applied, then only one pass is enough, and then we get the minimum number of comparisons
Necessary definitions and classification of sorts.
Sorting. Necessary definitions and classification of sorts. Direct inclusion and selection sorts. Their effectiveness
Sorting is the arrangement of data in memory in a regular form by their keys. So when processing data, it is important to know the information field of the data and their placement in the machine. Therefore, they distinguish internal(sorting in RAM) and external sorting(sorting in external memory). Regularity the arrangement of elements is the increase (decrease) of the key value from the beginning to the end in the array.
If the records to be sorted take up a large amount of memory, moving them is expensive. To reduce them, use address table sort method. This method is used in key address table. Permutation of pointers is performed, i.e. The array itself is not moved. When sorting, the same keys may also occur. In this case, it is desirable to arrange the same keys after sorting in the same order as in the source file. This principle is used for sustainable sorting.
Sorting efficiency can be considered from several criteria:
1) time spent on sorting;
2) the amount of RAM required for sorting;
3) the time spent by the programmer writing the program.
The time spent sorting is proportional to the number of comparisons in the sort and the number of element moves.
It is believed that the order of the comparison number during sorting can be in the range from o(nlogn) before o(n 2), Where o(n)- an ideal and unattainable case.
Sorting methods can be classified something like this:
1) strict (direct) methods(their efficiency is about the same):
· direct connection;
· direct choice;
· direct exchange;
2) improved methods.
In life, the principle of this sorting is present when playing solitaire games, cleaning an apartment, when it is necessary to arrange a bunch of mixed things in the proper order, etc. A very natural way of sorting has been applied to data ordering as well.
Elements are mentally divided into a ready-made sequence a 1 ,...,a i-1 and original sequence. In the finished sequence, the elements are arranged in a given order (in descending or ascending order). And in the initial sequence there are elements that need to be sorted. At each step, the elements of the original sequence are reduced by one, and the finished sequence is increased by one. This is due to the fact that from the original sequence is extracted i- th element and is transferred to the finished sequence, while it is inserted in the right place among the elements of the finished sequence.
Consider an example of direct inclusion sorting on the sequence of elements: 10, 3, 11, 8, 2, 15, 44, 9 (Table 11.1). It needs to be sorted in ascending order.
First, the finished sequence has no elements. In the first step, the first element of the original sequence, 10, becomes the first element of the finished sequence. Then the second step: element 3 from the original sequence is placed in the finished one. It happens like this. If the element is greater than 10, then it remains in its place, and if it is less, then 10 is shifted by one to the right and an element is put in its place. Since 3<10, то готовая последовательность теперь будет иметь вид: 3, 10, а исходная – 11, 8, 2, 15, 44, 9. Далее на третьем шаге из исходной последовательности выбирается 11 и помещается в готовую последовательность. Сначала 11 сравнивается с 10, и так как 11>10, then 11 remains in place. The original sequence is now: 8, 2, 15, 44, 9. The next steps are done in the same way.
Table 11.1
How direct sorting works
The number of steps in this sort (Table 11.1) is equal to the number of elements in the sorted sequence, i.e. 8 steps = 8 elements.
There are two ways to implement this method- this is without a barrier (Fig. 11.1) and with a barrier (Fig. 11.2).
The direct inclusion method can be improved by finding a place for the inserted record in an ordered subtable using the method binary (dichotomous, binary, logarithmic) search. This modification of the insertion method is called insert with binary inclusion.
Consider j‑th sorting step ( j=2, 3, ..., n). If K[ j]>= K[ j-1] , then the order is not violated and we should go to R[ j+1]– oh records. If K[ j]< K[ j-1] , That R[ j] stored in work variable (Rab= R[ j]) and for it a place is sought in the ordered part of the table - in the subtable. Let us denote the lower bound of the index of this subtable as ng, top - through vg (originally ng=1. vg=j-1).
According to binary search the key K[ j] the record in question R[ j] must first compare with the key K[ i] records R[ i] , located in the middle of the ordered subtable (i=(ng+vg) div 2). If K[ j]> K[ i], then discarded (that is, no longer considered) the left side of the sub-table - records with smaller keys (ng= i+1) . If K[ j]< K[ i] , then the right side of the subtable is discarded - records with large keys (vg= i-1). The search continues in the rest of the subtable. The process of dividing parts of a subtable in half continues until one of the following situations occurs:
1) K[ j]= K[ i] , hence, (i+1) The -th position is the location for the entry in question. Let's move the records R[ i+1], R[ i+2], …, R[ j-1] one position to the right and thus free up space for insertion (R[ i+1]= Rab).
2) K[ j]<> K[ i] And ng> vg – the keys did not match, and the length of the last subtable is 1. In this case, the insertion point is the position ng, so records R[ ng], R[ ng+1], … , R[ j-1] should be shifted one position to the right (R[ ng]= Rab) .
The binary search algorithm is described in detail in the "Dichotomous Coincidence Search" section.
Let's look at an example j-th step of sorting (the place of the record with the key equal to 9 is determined; j=7, K[ j]=9 ):
The average number of comparisons for this method is nlog 2 (n).
Double path insertion method
Double path insertion method is a modification of the direct insertion method; it improves sorting performance.
To implement this method, an additional amount of memory is required, equal to the amount occupied by the table to be sorted (let's call it the output zone T). At the first sorting step in the middle of the output area (position m=(ndiv 2)+1) the first record of the table is placed R. Other positions T while empty. At subsequent sorting steps, the key of the next record R[ j] (j=2, 3, …, n) is compared with the record key T[ m] and, depending on the results of the comparison, a place for R[ j] found in T left or right of T[ m] insert method. In this case, the numbers of the leftmost ( l) and the rightmost ( r) of the elements brought into the output zone. End values l And r equal 1 And n respectively.
The following situations should also be taken into account in the algorithm:
record key R[j] less than the write key T[m], But l=1;
record key R[j] more write key T[m], But r=n.
In these cases, to insert a record R[ j] it is necessary to shift the records of the subtable along with the record T[ m] right or left (using direct insertion method).
Let's look at an example of sorting using this method.
Let the initial sequence of table keys look like:
24, 1, 28, 7, 25, 3, 6, 18, 8 (n=9, m=(n div 2)+ 1=5)
|
Step number |
Output zone |
|||||||||
Loading...