In the last issue we considered the bubble sort method (Forex Magazine 2004 number 5, Programming in MQL II: Sort method of the bubble).
Let us recall what the algorithm is: we are in the process of sorting "probegaem" on elements of the array, comparing the current element with the following. If the next element of the array is smaller than the current, then change their seats.
"Probegaem on the array of values even more - as many times as elements in the array, each serving, if necessary, described reshuffle.
Now remember, in the process of sorting varied array of data containing the numbers 35, 12, 38, 120, 34:
35, 12, 38, 120, 34 <- initial state
----------------------
12, 35, 38, 34, 120 <- 1 after the first passage
12, 35, 34, 38, 120 <- 2, after the first passage
12, 34, 35, 38, 120 <- after the 3rd passage
12, 34, 35, 38, 120 <- after the 4 th passage
12, 34, 35, 38, 120 <- after the 5 th passage
Well you can see that already in the 3 rd pass an array becomes otsortirovannym, it means that the rest of the work we could not perform. How is implementing an algorithm for MQL II, could have been avoided unnecessary work? If a little thought, would be obvious that everything that happens in the sort - it is a permutation of the array sites, and if we can tell, whether carried out at least a reversal, it may become for us a signal that the sorting is still not finished. In previous issues of the magazine (Forex Magazine 2004 number 1 and number 2, ObuchenieMQL II, Lesson number 1 and Lesson number 2) was considered the logical operators and variables are the logical type, and now we need the knowledge.
To add to our program a logical variable is_sorted. Each time, before once again look over and compare the elements of the array will assign the variable value of false. If we ever change the value of the array, then assign it to true. After the end of the over sized element, we check the value of the variable and, depending on its importance (t.e.v depending on whether any permutation sized items), we are completing or continuing sorting.
var: is_sorted (true);
for ix = 0 to 4
(
is_sorted = true;
for iy = 0 to 3
(
if (values [iy]> values [iy 1]) then
(
tmp = values [iy];
values [iy] = values [iy 1];
values [iy 1] = tmp;
is_sorted = false;
);
);
if (is_sorted)
(
break;
);
);
Remember that the instruction "break" requires that the program to stop the current cycle. Using it in combination with variable is_sorted, allows us to reduce the number of operations to sort the data.
Starting indicators that do not include such details at a very fast computer, most likely will not lead to any difficulties. But if your computer is not very fast, but still the same, you run a lot of these indicators, it may happen that the graphics will podtormazhivat and slow to respond to your actions. Most likely, it will happen because of the fact that too much time spent on compliance is not the work required. The above nehitrye changes in the program could lead to the unloading of computer resources.
Now would be implemented next iteration:
35, 12, 38, 120, 34 <- initial state
----------------------
12, 35, 38, 34, 120 <- 1 after the first passage
12, 35, 34, 38, 120 <- 2, after the first passage
12, 34, 35, 38, 120 <- after the 3rd passage
12, 34, 35, 38, 120 <- break
We see that at the 4 th pass from the fact that it was not made any changes, the program will understand that the array is already sorted, and will cease its work on the array.
But do not think that this sort would be equally quick to work on all types of arrays. If the modified program, we try to sort out an array of data, in which only two adjacent elements are not in place, the program will be completed only two passes of the array: the first - to swap two cells, the second - to ensure that the data are sorted:
12, 34, 38, 35, 120 <- initial state
----------------------
12, 34, 35, 38, 120 <- 1 after the first passage
12, 34, 35, 38, 120 <- break
If the same sized array initially will contain data in the reverse order, then he would run as if we did not make any changes to the implementation of sorting algorithm:
120, 38, 35, 34, 12 <- initial state
----------------------
38, 35, 34, 12, 120 <- 1 after the first passage
35, 34, 12, 38, 120 <- 2, after the first passage
34, 12, 35, 38, 120 <- after the 3rd passage
12, 34, 35, 38, 120 <- after the 4 th passage
12, 34, 35, 38, 120 <- break
Thus, it is important to understand that the algorithm itself unchanged, only changed its embodiment in the MQL II.
There are more sophisticated sorting algorithms that run faster, but the effort spent on their understanding and implementation, will be able to pay off only when a need to sort a very large amount of data.
While the focus on our laurels and look at a small problem for the expansion of horizons. We have already raised the challenge to reverse the values of two elements, and for this we used the additional temporary variable. Now let's suppose that our computer is so little memory that we can not afford to allocate more space for one variable, and have to be satisfied with only two variables available. It turns out that using two back operations, such as the plus iminus "or" multiply and divide, you can share data in two variables. Here's how:
A = A B
B = A - B
A = A - B
The reader is invited to self-reflect on this algorithm, but would like to note that this method has a limitation: the operation using the plus and minus "or" multiply and divide "it is impossible to reverse a very large number. The point is that under a variable in your computer has a certain amount of memory, and if the amount of memory is strictly regulated, it means that there is a maximum number that can be stored in a variable. What happens if we are to the maximum number of add a number, say the unit? Everything depends on the implementation of a programming language, one can say for sure - will not the number that is expected.
At present, all the next time we look at search algorithm specific element in the sorted array.
Alexander Ivanov
No comments:
Post a Comment