Algorithms and data structures. Direct Sort Direct Sort c

In our case, we got one pass "idle". To once again do not view the elements, which means making comparisons, spending time on this, you can enter the checkbox fl which remains in the meaning false if no exchange is made during the next pass. 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

Efficiency of the Direct Exchange Sorting Algorithm

The number of comparisons is C max = n (n-1) / 2, order O (n 2).

The number of displacements M max = 3C max = 3n (n-1) / 2, order O (n 2).

If the array has already been sorted and the algorithm with a flag is applied, then just one pass is enough, and then we get the minimum number of comparisons

Inclusion sort, like simple selection sort, is usually used for arrays that do not contain duplicate elements.

Sorting by this method is performed step by step sequentially. On k-Th step is considered that the part of the array containing the first k– 1 item is already ordered, that is.

Next, you need to take k–Th element and choose a place for it in the sorted part of the array so that after its insertion the ordering is not broken, that is, you need to find such that. Then you need to insert the element a (k) to the found place.

With each step, the sorted part of the array grows. To perform a full sort, you need to do n– Step 1.

It remains to answer the question of how to find a suitable place for an element NS... We will proceed as follows: we will view the elements located to the left of NS(that is, those that are already ordered), moving to the beginning of the array. You need to view the items a (j), j varies from k– l to 1. This scan will end if one of the following conditions is met:

An element was found that indicates a need to insert NS between and a (j).

The left end of the ordered part of the array has been reached, therefore, you need to insert NS to the 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 NS.

The sorting technique is illustrated in Table 2:

Table 2 - Example of sorting using direct inclusion

The originally ordered sequence consists of 1st element 9. 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 the elements of the ordered sequence, so the ordered sequence 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 sorting

There are three simple improvements to the bubble method. First, if at some step no exchange was performed, then the execution of the algorithm can be terminated. Secondly, you can remember the smallest value of the array index for which the permutations were performed at the current step. Obviously, the top of the array up to the element with this index is already sorted, and at the next step, you can stop comparing the values ​​of neighboring elements when this index value is reached. Third, the bubble method works unequally for "light" and "heavy" values. The light value gets to the right place in one step, and the heavy value drops one position towards the right place at each step.

The ShakerSort method is based on these observations. When it is applied, the direction of the sequential viewing changes at each next step. As a result, at one step, the next lightest element "pops up", and at the other, the next heaviest element "sinks". An example of a shaker sort is shown in Table 3.

Table 3 - Example of a shaker sort

Sorting an array using inclusions with decreasing distances (Shell method)

D. Schell 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 re-combined and sorted into groups, while the distance between the elements decreases. The process ends after the ordering of the elements is carried out with the distance between them equal to 1.

An example of Shell sorting is shown in Table 4.

Table 4 - Example of Shell sorting

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 are exchanged that are spaced apart. If, when comparing 2 elements, the exchange did not occur, 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 split sorting method was proposed by Charles Hoare. This method is a development of the simple exchange method and is so effective that it became known as the "Quicksort" method.

The main idea of ​​the algorithm is that some element of the array is randomly 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 scanned from the right until 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 get to 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 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 with iterations if you remember the corresponding array indices.

The process of sorting an array by the quick method is shown in Table 5.

Table 5 - Example of quick sort

Inclusion sort works on a list of unordered positive integers (commonly called keys), sorting them in ascending order. This is done in much the same way that most players arrange the cards dealt to them, picking up one card each time. Let's show how the general procedure works by the example of the following unsorted list of eight integers:

27 412 71 81 59 14 273 87.

The sorted list is recreated; at first it is empty. At each iteration, the first number of the unsorted list is removed from it and placed in the corresponding position in the sorted list. To do this, the sorted list is scanned, starting with the smallest number, until an appropriate place is found for the new number, i.e. until all sorted numbers with lower values ​​are in front of it, and all numbers with large values ​​are after it. The following sequence of lists shows how this is done:

Iteration 0

Sorted 27

Iteration 1 Unsorted 412 71 81 59 14 273 87

Assorted 27,412

Iteration 2 Unsorted 71 81 59 14 273 87

Assorted 27 71 412

Iteration 3 Unsorted 81 59 14 273 87

Assorted 27 71 81 412

Iteration 4 Unsorted 59 14 273 87

Assorted 27 59 71 81 412

Iteration 5 Unsorted 14 273 87

Sorted 14 27 59 71 81 412

Iteration 6 Unsorted 273 87

Sorted 14 27 59 71 81 273 412

Iteration 7 Unsorted 87

Sorted 14 27 59 71 81 87 273 412

In the following algorithm, only one list is started, and the numbers are rearranged in the old list.

Algorithm SIS(Sort by Direct inclusion). Sort the sequence of integers I (1), I (2), in the old place. ... ... , I (N) in ascending order.

Step 1.[Main iteration]

For J ← 2 to N do through step 4 od ;and STOP.

Step 2.[Select next integer] Set K ← I (J); and L ← J − 1.

Step 3.[Comparison with sorted integers] While K

AND L≥1 do set I (L + 1) ← I (L); and L ← L − 1 od.

Step 4.[ Turning on ] Set I (L + 1) ← K.

QUICKSORT:Sorting algorithm with average running time O (N ln N)

The main reason for the slow operation of the SIS algorithm is that, all comparisons and exchanges between keys in sequence a 1, a 2,. ... ... and N occur for pairs of adjacent elements. This method requires a relatively large

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Lines 38 08 16 06 79 76 57 24 56 02 58 48 04 70 45 47 Action

1 38 47 decrease in j

5 04 38 exchange

6 08 38 increase i

10 38 79 exchange

14 02 38 exchange

15 76 38 increase i,>

16 38 76 exchange

17 38 56 decrease j

19 24 38 exchange

20 57 38 increase i,>

21 38 57 exchange, decrease

22 04 08 16 06 02 24 38 57 56 76 58 48 79 70 45 47

(1 2 3 4 5 6) 7 (8 9 10 11 12 13 14 15 16)

time to put a key out of place at desired position in the order to be sorted. It is natural to try to speed up this process by comparing pairs of elements that are far apart in sequence.

K. Hoore invented and very effectively applied this idea (the QUICKSORT algorithm), reducing the average running time of the SIS algorithm from the order of O (N 2) to the order of O (N ln N). Let us explain this algorithm with the following example.

Suppose we want to sort a sequence of numbers from the first row in Figure 1. 15. Let's start with the assumption that first the key in this sequence (38) serves as a good approximation of the key that will eventually appear in the middle of the sorted sequence. We use this value as a pivot, relative to which the keys can be swapped, and proceed as follows. We set two pointers I and J, of which I starts from the left (I = 1), and J - from the left in the sequence (J = N). Comparing a I and a J... If a I ≤a J, set J ← J − 1 and make the following comparison. We continue reduce J until we reach a I> a J. Then let's swap a I ↔a J(Fig. 15, line 5, exchange of keys 38 and 04), set I ← I + 1 and continue increase I until we get a I> a J. After the next exchange (line 10, 79↔38), we again decrease J. Alternating between decreasing J and increasing I, we continue this process from both ends of the sequence to the “middle” until we get I = J.

Now there are two facts. First, the key (38), which was initially in the first position, is by this time in its proper place in the sorted sequence. First, all keys to the left of this element will be smaller, and all keys to the right will be large.

The same procedure can be applied to the left and right subsequences for the final sorting of the entire sequence. The last line (numbered 22) in Fig. 15 shows that when I = J is obtained, then I = 7. After that, the procedure is applied again to subsequences (1,6) and (8,16).

The recursive nature of the algorithm suggests that the values ​​of the indices of the outermost elements of the larger of the two unsorted subsequences (8,16) should be pushed onto the stack and then proceeded to sort the smaller subsequence (1,6).

In line 4 in Fig. 15, the number 04 has moved to position 2 and subsequences (1,1) and (3,6) are to be sorted. Since (1,1) is already sorted (number 02), we sort (3,6), which in turn leads to line 6, in which (3,4) and (6,6) are to be sorted. On line 7, subsequence (1,6) is sorted. Now we pop (8,16) off the stack and start sorting this subsequence. Line 13 contains subsequences (8,11) and (13,16) that need to be sorted. We put (13,16) on the stack, sort (8,11), etc. On line 20, the entire sequence is sorted.

Before describing the QUICKSORT algorithm formally, you need to show exactly how it works. We use the stack [LEFT (K), RIGHT (K)] to store the indices of the leftmost and rightmost elements of unsorted subsequences. Since short subsequences are sorted faster using the normal algorithm, the QUICKSORT algorithm has an input parameter M that determines how short the subsequence must be in order to sort it in the usual way. For this purpose, we use Simple Inclusion Sort (SIS).

Search

Now let's turn to the study of some of the main problems related to information retrieval on data structures. As in the previous section on sorting, we will assume that all information is stored in records that can be identified by key values, i.e. the record R i corresponds to the key value denoted by K i.

Suppose that the file contains N records in a random way in the form of a linear array. The obvious method for finding a given entry would be to iterate through the keys. If the required key is found, the search ends successfully; otherwise, all the keys will be scanned, and the search will be unsuccessful. If all possible orderings of the keys are equally probable, then such an algorithm requires O (N) basic operations in both worst and average cases. The search time can be noticeably reduced by pre-ordering the file by keys. This preliminary work makes sense if the file is large enough and accessed frequently.

Suppose that we went to the middle of the file and found the key K i there. Let us compare K and K i. If K = K i, then desired entry found. If K<К i ,то ключ К должен находиться в части файла, предшествующей К i (если запись с ключом К вообще существует) . Аналогично, если К i <К, то дальнейший поиск следует вести в части файла, следующей за К i . Если повторять эту процедуру проверки ключа К i из середины непросмотренной части файла, тогда каждое безуспешное сравнение К с К i будет исключать из рассмотрения приблизительно половину непросмотренной части.

A flowchart of this procedure, known as binary search, shown in Fig. 16

Algorithm BSEARCH (Binary search) search for a record with the key K in a file with N≥2 records, the keys of which are ordered in ascending order K 1<К 2 …<К N .

Step 0.[Initialization] Set FIRST ← 1; LAST ← N. (FIRST and LAST are pointers to the first and last keys in the not yet viewed part of the file.)

Step 1.[Main loop] While LAST≥FIRST do through step 4 od.

Step 2.[Obtaining a central key] Set I ← | _ (FIRST + LAST) / 2_ | . (K i is a key located in the middle or to the left of the middle of the part of the file that has not yet been viewed.)

Step 3.[Check for successful completion] If K = K I then PRINT "Successful completion, the key is K I"; and STOP fi.

Step 4.[Comparison] If K < K I then set LAST ← I-1 else set FIRST ← I + 1 fi.

Step 5.[Search unsuccessful] PRINT "unsuccessful"; and STOP.

The BSEARCH algorithm is used to find K = 42 in Figure 17.

Binary search can also be used to represent an ordered file as a binary tree. The key value found in the first execution of step 2 (K (8) = 53) is the root of the tree. Key intervals to the left (1,7) and to the right (9,16) of this value are pushed onto the stack. The top bin is popped off the stack and step 2 finds the middle element (or the element to the left of the middle). This key (K (4) = 33) becomes the next element after the root to the left if its value is less than the value of the root, and the next to the right otherwise. Subintervals of this interval to the right and left of the newly added key [(1,3), (5,7)] are now pushed onto the stack. This procedure is repeated until the stack is empty. Figure 18 shows a binary tree that would be built for the 16 ordered keys in Figure 17.

Binary search can now be interpreted as traversing this tree from the root to the desired record. If the final vertex is reached, and the specified key is not found, the required entry is missing in this file. Note that the number of vertices on a single path from the root to a given key K is equal to the number of comparisons performed by the BSEARCH algorithm when trying to find K.

Necessary definitions and classification of sortings.

Sorting. Necessary definitions and classification of sortings. Direct inclusion and selection sorts. Their effectiveness

Sorting Is the arrangement of data in memory in a regular form according to their keys. So, when processing data, it is important to know the information field of the data and its placement in the machine. Therefore, 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, then moving them is expensive. In order to reduce them, use sorting method of address table... This method is used in key address table... The pointers are rearranged, i.e. The array itself does not move. When sorting, the same keys may also be encountered. In this case, it is desirable to arrange identical keys after sorting in the same order as in the source file. This principle is used to sustainable sorting.

Sorting efficiency can be viewed from several criteria:

1) time spent on sorting;

2) the amount of RAM required for sorting;

3) time spent by the programmer to write the program.

The time it takes to sort is proportional to the number of comparisons in the sort and the number of item movements.

It is considered that the order of comparison number when 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 effectiveness is about the same):

· direct inclusion;

· direct selection;

· 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 sorting method has been applied to data ordering as well.

Elements are mentally divided into a ready-made sequence a 1, ..., a i-1 and the original sequence. In the finished sequence, the elements are arranged in a given order (descending or ascending). And the original sequence contains the elements that need to be sorted. At each step, the elements of the original sequence are reduced by one, and the finished one is increased by one. This is due to the fact that from the original sequence is extracted i- th element and transferred to the ready-made sequence, while it is inserted in the right place among the elements of the ready-made sequence.

Consider an example of sorting by the direct inclusion method on the sequence of elements: 10, 3, 11, 8, 2, 15, 44, 9 (Table 11.1). It is necessary to sort it in ascending order.

At first, the finished sequence has no elements. In the first step, the first element of the original sequence, which is 10, becomes the first element of the finished sequence. Then the second step: element 3 from the original sequence is placed into the finished one. It goes 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 the 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. Subsequent steps are performed in the same way.

Table 11.1

How Direct Sorting Works

The number of steps in this sorting (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 - it is without a barrier (Figure 11.1) and with a barrier (Figure 11.2).

General information

Control task

Job options