Программирование на MQL II. Сортировка методом пузырька

   При написании программ часто возникают однотипные задачи. Они хорошо известны опытным программистам и, более того, в развитых языках программирования эти задачи уже, как правило, реализованы в виде стандартных подпрограмм. Одной из таких типичных задач, рано или поздно встающих перед программистом, является сортировка данных.
   Настоящая реализация языка MQL не содержит встроенных подпрограмм для сортировки данных, но это не так плохо, как может показаться, так как с одной стороны MQL II имеет всё необходимое для самостоятельной реализации алгоритмов сортировки, а с другой стороны - подобные задачи являются прекрасным материалом для обучения программированию.
   В предыдущих выпусках журнала были рассмотрены основные конструкции языка MQL II, и читателю должны быть уже знакомы такие понятия как переменная, её тип, массивы, условные операторы "if-then" и циклы "for-to".
   Для определённости, сортировкой будем называть процесс расположения элементов массива в порядке возрастания их значений. Т.е., предположим, что имеется массив из пяти элементов со значениями 35, 12, 38, 120, 34.
   После выполнения сортировки этого массива, мы должны получить массив из пяти элементов со значениями 12, 34, 35,38, 120.
   В этой статье рассматривается простой способ сортировки данных, который называется "методом пузырька". Назван он так в связи с тем, что в процессе его выполнения меньшие значения (более лёгкие), как бы уподобляясь пузырьку воздуха в воде, всплывают на поверхность (перемещаются на левый край массива), а большие значения (более тяжёлые) - тонут (перемещаются на правый край массива).
   Собственно сам алгоритм заключается в следующем: в процессе сортировки мы "пробегаем" по элементам массива, сравнивая текущий элемент со следующим. Если следующий элемент массива меньше чем текущий, то меняем их местами.
   "Пробегаем" по массиву значений ещё и ещё - столько раз, сколько элементов в массиве, каждый раз выполняя, если необходимо, описанные перестановки.

   Для наглядности ниже приводиться состояния массива на каждом из проходов:

   35, 12, 38, 120, 34
   -------------------
   12, 35, 38, 34, 120
   12, 35, 34, 38, 120
   12, 34, 35, 38, 120
   12, 34, 35, 38, 120
   12, 34, 35, 38, 120

   Для того чтобы сделать это автоматически, составим следующую программу:
   var: ix(0);
   var: iy(0);
   var: tmp(0);
   array: values[5](0);

   values[0] = 35;
   values[1] = 12;
   values[2] = 38;
   values[3] = 120;
   values[4] = 34;

   for ix = 0 to 4 {
   for iy = 0 to 3 {
   if(values[iy] > values[iy+1]) then {
   tmp = values[iy];
   values[iy] = values[iy+1];values[iy+1] = tmp;
   };
   };
   };

   В данном примере мы воспользовались двумя циклами, один из которых вложен в другой. Что это означает? Это означает то, что на каждое изменение счётчика внешнего цикла "ix", четыре раза выполняется цикл по счётчику внутреннего цикла "iy".
   Опишем словами то, что происходит, когда мы выполняем внутренний цикл:

   for iy = 0 to 3 {
   if(values[iy] > values[iy+1]) then {
   tmp = values[iy];
   values[iy] = values[iy+1];
   values[iy+1] = tmp;
   };
   };

   Вспоминая описание цикла "for-to" (Forex Magazine 2004 №4, Обучение MQL II, Урок №4), мы видим, что команда "for iy = 0 to 3" предписывает компьютеру четырежды выполнить то, что заключено в скобки. Причём на первом повторе переменная "iy" принимает значение 0, затем, на втором повторе, её значение уже на единицу больше, т.е.1, затем 2, и на последнем повторе её значение равняется 3.
   Т.е. в этом цикле мы перебираем все значения массива,кроме последнего, сравнивая текущий элемент со следующим. Если следующий элемент массива меньше, чем текущий, то меняем местами их значения.
   Внимание, мы столкнулись с ещё одной типичной задачей, встающей перед программистами! Для того, чтобы поменять местами значения двух переменных, нам не достаточно выполнить два присваивания values[iy] = values[iy+1] и values[iy+1] = values[iy], т.к. после первого присваивания теряется начальное значение.
   Например, если values[iy+1] имеет значение 12, а values[iy] имеет значение 35, то при выполнении values[iy]= values[iy+1] обе переменных будут иметь значения 12. Вторая директива values[iy+1] = values[iy] не сделает ничего полезного, т.к. к моменту её выполнения обе переменных имеют одинаковые значения, а первоначальное значение переменной values[iy] для нас исчезло навсегда!
   Как поступать в таком случае? Есть несколько выходов из этой ситуации: самый простой для понимания - завести дополнительную переменную под временное хранение значения values[iy]. В данном случае мы используем переменную "tmp". Теперь, запомнив значение values[iy] во временной переменной, мы сможем его восстановить после операции values[iy] = values[iy+1]. И уже в values[iy+1] мы будем записывать значение, сохранённое в переменной "tmp".

   Вот как это выглядит:

   tmp = values[iy];
   values[iy] = values[iy+1];
   values[iy+1] = tmp;

   Давайте обобщим то, что у нас получилось:
   Если записать оба цикла, но, вместо внутреннего цикла, использовать его словесное описание, то получится следующее:

   for ix = 0 to 4 {
   // "пробегаем" по всем элементам массива, кроме последнего.
   // если текущее значение больше, чем следующее за ним, то
   // меняем местами значения текущего и следующего элементов.
   };

   Ещё раз, вспоминая описание цикла "for-to", видим, что команда "for ix = 0 to 4" будет выполнять блок, заключённый в фигурные скобки пять раз, то есть столько раз, сколько элементов в сортируемом массиве.
   Обобщая ещё раз всё вышесказанное, видим, что словесное описание алгоритма, записанного нами на MQL II, звучит так:
   Столько раз, сколько элементов в сортируемом массиве, повторять следующую процедуру: перебирая все элементы массива, кроме последнего, сравнивать их со следующим в массиве, если текущее значение больше, чем следующее за ним, то поменять местами значения текущего и следующего элементов.
   В следующей статье мы порассуждаем над тем, как можно ускорить выполнение алгоритма сортировки "методом пузырька", и рассмотрим метод быстрого поиска нужного элемента в отсортированном массиве. Так же, для расширения программистского кругозора, мы ознакомимся ещё с одним способом обмена двух переменных значениями.

Александр Иванов (AKA HORN)

Материал предоставлен : http://www.forextimes.ru/magazine