Главная » 2009 » Декабрь » 27 » Программирование на MQL II. Сортировка методом пузырька, продолжение
Программирование на MQL II. Сортировка методом пузырька, продолжение
19:58
Программирование на MQL II. Сортировка методом пузырька, продолжение
В прошлом номере мы рассмотрели сортировку методом пузырька (Forex Magazine 2004 №5, Программирование на MQL II: Сортировка методом пузырька).
Давайте вспомним, в чём заключается алгоритм: в процессе сортировки мы "пробегаем" по элементам массива, сравнивая текущий элемент со следующим. Если следующий элемент массива меньше, чем текущий, то меняем их местами.
"Пробегаем" по массиву значений ещё и ещё - столько раз, сколько элементов в массиве, каждый раз выполняя, если необходимо, описанные перестановки.
А теперь вспомним, как в процессе сортировки менялся массив данных содержащий числа 35, 12, 38, 120, 34:
35, 12, 38, 120, 34 <- начальное состояние
----------------------
12, 35, 38, 34, 120 <- после 1-го прохода
12, 35, 34, 38, 120 <- после 2-го прохода
12, 34, 35, 38, 120 <- после 3-го прохода
12, 34, 35, 38, 120 <- после 4-го прохода
12, 34, 35, 38, 120 <- после 5-го прохода
Прекрасно видно, что уже на 3-ем проходе массив становится отсортированным, это означает, что остальную работу мы могли бы и не выполнять. Каким образом, реализуя алгоритм на MQL II, можно было бы избежать лишней работы? Ели немного поразмыслить, станет видно, что всё, что происходит во время сортировки - это перестановка элементов массива местами, и если мы сможем сказать, была ли выполнена хоть одна перестановка, то это может стать для нас сигналом к тому, что сортировка всё ещё не закончена. В предыдущих номерах журнала (Forex Magazine 2004 №1 и №2, ОбучениеMQL II, Урок №1 и Урок №2) были рассмотрены логические операторы и переменные логического типа, и сейчас нам понадобятся эти знания.
Добавим в нашу программу логическую переменную is_sorted. Каждый раз, перед тем как в очередной раз перебирать и сравнивать элементы массива будем присваивать этой переменной значение false. Если мы поменяем хоть раз значения элементов массива, то присвоим ей true. После завершения очередного перебора сортируемых элементов, мы проверим значение переменной и, в зависимости от её значения (т.е.в зависимости от того произведена ли какая-нибудь перестановка сортируемых элементов), мы завершаем или продолжаем сортировку.
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;
};
};
Напоминаем , что инструкция "break" предписывает программе прекратить текущий цикл. Использование её в паре с переменной is_sorted, позволяет нам сократить количество операций для сортировки данных.
Запуск индикаторов, которые не учитывают таких тонкостей, на очень быстром компьютере, скорее всего не приведёт к каким-либо трудностям. Но если ваш компьютер не очень быстр, да ещё к тому же вы запустили много таких индикаторов, то может случиться, что графики будут подтормаживать и замедленно реагировать на ваши действия. Скорее всего, это случится из-за того, что слишком много времени уходит на выполнение не требующейся работы. Вышеописанные нехитрые изменения в программе могут привести к разгрузке ресурсов компьютера.
Теперь будут выполнены следующие итерации:
35, 12, 38, 120, 34 <- начальное состояние
----------------------
12, 35, 38, 34, 120 <- после 1-го прохода
12, 35, 34, 38, 120 <- после 2-го прохода
12, 34, 35, 38, 120 <- после 3-го прохода
12, 34, 35, 38, 120 <- break
Видим, что уже на 4-м проходе из-за того, что не было сделано ни одной перестановки, программа поймёт, что массив уже отсортирован, и прекратит свою работу над массивом.
Однако не стоит думать, что такая сортировка будет одинаково быстро работать на всех типах массивов. Если изменённой программой мы попробуем отсортировать массив данных, в котором всего два соседних элемента находятся не на своих местах, то программой будут выполнены всего два прохода по массиву:первый - чтобы поменять местами две ячейки, второй - для того, чтобы убедиться в том, что данные отсортированы:
12, 34, 38, 35, 120 <- начальное состояние
----------------------
12, 34, 35, 38, 120 <- после 1-го прохода
12, 34, 35, 38, 120 <- break
Если же сортируемый массив изначально будет содержать данные, расположенные в обратном порядке, то выполняться он будет так, как будто мы не вносили никаких изменений в реализацию алгоритма сортировки:
120, 38, 35, 34, 12 <- начальное состояние
----------------------
38, 35, 34, 12, 120 <- после 1-го прохода
35, 34, 12, 38, 120 <- после 2-го прохода
34, 12, 35, 38, 120 <- после 3-го прохода
12, 34, 35, 38, 120 <- после 4-го прохода
12, 34, 35, 38, 120 <- break
Таким образом, важно понять, что алгоритм как таковой неизменился, изменилось только его воплощение на MQL II.
Есть более сложные алгоритмы сортировки, которые выполняются ещё быстрее, но усилия, затраченные на их понимание и реализацию, смогут окупиться только тогда, когд а потребуется сортировать очень большое количество данных.
Пока остановимся на достигнутом и рассмотрим маленькую задачку для расширения кругозора. Перед нами уже вставала задача поменять местами значения двух элементов, и для этого мы использовали дополнительную временную переменную. Теперь давайте предположим, что у нашего компьютера настолько мало памяти, что мы не можем себе позволить выделить место ещё под одну переменную, и вынуждены довольствоваться только имеющимися двумя переменными. Оказывается, используя две обратные операции, такие как "плюс иминус" или "умножить и разделить", можно осуществить обмен данными двух переменных. Вот, как это делается:
A = A + B
B = A - B
A = A - B
Читателю предлагается самостоятельно подумать над этим алгоритмом, однако хотелось бы заметить, что этот способ имеет ограничение: используя операции "плюс и минус" или "умножить и разделить" невозможно поменять местами очень большие числа. Дело в том, что под переменную в компьютере отводится определённое количество памяти, и если размер этой памяти строго регламентирован, значит, есть некоторое максимальное число, которое можно хранить в такой переменной. Что же произойдёт, если мы к этому максимальному числу прибавим ещё одно число, допустим единицу? Всё зависит от реализации языка программирования, одно можно сказать точно - получится совсем не то число, которое ожидалось.
На сегодня всё, в следующий раз мы рассмотрим алгоритм поиска конкретного элемента в отсортированном массиве.
