Another algorithm, designed to organize arrays, algorithm is Sorting inserts (Insertion Sort). This algorithm(as other, viewed on our website) simple enough. It consists of two loops (one embedded in the other). The first loop produces a passage through the array, and second – the movement of the elements to. Let's just take a look, It might look like a sort code, and already below analyze, how it works.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | #include <iostream> using namespace std; int main() { const int N = 10; int a[N] = { 12, 5, 3, 2, 45, 96, 6, 8, 11, 24 }; int buff = 0; // для хранения перемещаемого значения int i, j; // для циклов /************* Начало сортировки *******************/ for (i = 1; i < N; i++) { buff = a[i]; // запомним обрабатываемый элемент // и начнем перемещение элементов слева от него // пока запомненный не окажется меньше чем перемещаемый for (j = i - 1; j >= 0 && a[j] > buff; j--) a[j + 1] = a[j]; a[j + 1] = buff; // и поставим запомненный на его новое место } /************* Конец сортировки *******************/ for (int i = 0; i < N; i++) // вывод отсортированного массива cout << a[i] << '\t'; cout << endl; } |
Algorithm Sorting inserts It can be described by the following positions:
- Remember in a temporary variable ( buff example) the value of the current array element;
- While elements of the left of the stored value is greater than the stored – We move them in the right position. It turns out, the previous item will take the stored cell. And the, that is before the previous – moves in turn the place of the previous. And so the items will move one after the other.
- The movement ends with elements, If the next element, want to move, It is meaningfully less, than that, remember that in a temporary variable at the beginning of the loop.
- Loop takes the next element, and again shifts all, which are located in front of him and big on value.
We will show visually the movement of values in an array of seven elements during operation sorting inserts:
On the first iteration in a variable buffer is written with an index value of the cell 1 and the loop will check this item. There we have the number 2. It is larger than the value, is recorded in the zero cell, so the movement is not. Further, the variable buffer is written the value of the index of the cell 2 again comparing the values go left, etc.. Only on the fourth iteration of the outer loop will overwrite values. Three first will be swapped with the five, and then with the four.
In this way, during sorting inserts recorded in element buff “sifted” to the beginning of array. In cases, when the element with a value less than would be foundbuff or the beginning of the sequence is reached – sieving stops.
A good visual illustration of the algorithm Sorting inserts is onwikipedia:
Time spent on the operation of this algorithm is entirely dependent on the initial data: the number of elements in the array and the original ordering. It's clear, that the larger the array – the longer the time necessary for its processing. Also, more time is required to sort the array in which the value is absolutely not ordered.
Algorithm Sorting inserts good for small arrays (up to several tens of elements). More efficient work, if the data of the array were previously partially sorted. If the array will be added new data (new items), algorithm can sort them as they are added (Unlike bubble sorting and sorting option). The effectiveness of the algorithm will increase significantly, if you add in the code algorithm binary search.
We also offer watch a short vidourok on computer with the analysis algorithm Sorting inserts:
Change sorting, They were taken to the amount of time, who performed the outer and inner loops.
What for? In this sort it is so easy to find – the total number of loops x 2 = N * (N-1) / 2 … and do not need anything to output.
But the computational complexity of sorting (any) measures the not some repetition loops, and evaluate the degree of growth the number of operations and comparisons of permutations of length N. And it is known in advance, what bad sorting (bubble, inserts … and almost all the other) have a degree of complexity O(N)N * = N (quadratic), and good (fast recursive) – O(N)=N*log(N).
There we have the number 2 21 There we have the number 2 // a[j + 1] = buff; // There we have the number 2[j] = buff;
In this case, it does not change them, and at the end it will output something like 12 12 12 12 12 24 45 45 96 96
You have an error in your code.
In string 21.
should not be
a[j + 1] = buff;
and
a[j] = buff;
All, understand, why does it work.
for (j = i – 1; j >= 0 && a[j] > buff; j–) a[j + 1] = a[j];
a[j + 1] = buff; // and deliver the stored at its new location
}
It's so clear, but it seems, what
for (j = i – 1; j >= 0 && a[j] > buff; j–)
{
a[j + 1] = a[j];
a[j + 1] = buff; // and deliver the stored at its new location
}