Толкование алгоритмов.
Массивы.
Сортировка массивов.
Пузырьковый метод.
Начало цикла толкования алгоритмов на тему массивы раздел сортировки массивов. На этом этапе мы будем разбирать пузырьковый метод сортировки массивов. К сожалению, на уроках зачастую мы не разбираем тонкости различных алгоритмов, теряя смысл, логику предоставленного нам алгоритма. Собственными усилиями я принял решение создать трактат, в котором попробую максимально возможно объяснить суть не самых простых вещей. Говоря про вещи, я прежде всего подразумеваю АЛГОРИТМ, составление алгоритма, его понимание исконно является сложной деятельностью, требующей огромного опыта с подобным. К каждому трактату будет приложена соответствующая блок-схема с данным алгоритмом, а также запись алгоритма на неформальном языке, в нашем случае DELPHI. Начнем.
Сперва определимся с понятием возрастающая и убывающая последовательность.
Предположим нам дана какая-то последовательность целых чисел, записанных в квадратных ячейках:
-3 | -5 |
Расположим элементы этих ячеек в порядке возрастания:
-5 | -3 |
И убывания:
-3 | -5 |
Таким образом мы упорядочили нашу последовательность в порядке возрастания или убывания.
Именно эту функцию должны выполнять сортировщики. В настоящий момент существует около 16 методов сортировки массивов. Все они разнообразны, некоторые являются модификацией других методов, но все они преследуют единственную цель: упорядочить элементы массива. Разница лишь в том, насколько быстро они будут это делать.
Итак, перейдем непосредственно к рассмотрению сортировки массива пузырьковым методом.
Название таит в себе вполне не завуалированный смысл, который заключается в сравнении всплывающего пузырька в воде с элементом массива, который преодолевает водный барьер и выходит в конце концов на свое место, как бы «всплывая» из неотсортированных элементов.
В принципе этот способ очень похож на метод сортировки прямого обмена.
Пусть дан произвольный массив M с суммарным количеством элементов n. Базой массива будет 0, то есть отсчет начинается с нуля, поэтому последний элемент массива будет иметь индекс n – 1, так как всего n элементов, а отсчет ведется с нуля. Например:
-3 | -5 |
|
В данном случае n = 7. Элементы начинаются с нуля, и поэтому, чтобы получить доступ к последнему элементу нужно из n (количество элементов в массиве всего) вычесть единицу: n -1 = 7 – 1 = 6.
Шестой элемент массива равен -5.
Рассмотрим два случая: в первом мы будем подходить к упорядочению элементов с начала (перемещать элементы в начало), а во втором с конца (перемещать элементы в конец). Давайте рассмотрим первый случай на примере нашего массива M.
Главный цикл (первый) будет перебирать все элементы, начиная от нуля до n – 2 (n – 1 – последний элемент, да и ещё минус один, так как в конце нам не потребуется проверять последний элемент, он из следствия второго цикла будет находиться на правильном месте, в чем мы убедимся позже) ПОСЛЕДОВАТЕЛЬНО, т.е двигаясь от предыдущего к следующему 0 -> 1 -> 2 … -> n -2. Действия этого цикла показано ниже, голубым цветом выделены те ячейки, которые охватит этот цикл:
-3 | -5 |
Как можно увидеть, последний элемент этого массива этим циклом не будет захвачен, поскольку n – 2. Почему именно так мы узнаем позже.
В данном цикле будет находиться ещё один цикл: вложенный цикл. Его задачей будет являться сортировка неотсортированных элементов. Все дело в том, что в процессе работы первого цикла постепенно будут появляться отсортированные элементы, именно эти элементы не будут входить во второй цикл, поэтому он сортирует лишь неотсортированные элементы следующим образом: поскольку мы рассматриваем первый случай, когда сортированные элементы будут уходить в самое начало, то наш цикл будет начинаться с последнего элемента массива n - 1. Двигаться цикл будет против направления нашего первого цикла. То есть с последнего к первому. В самом втором цикле будет лишь одна проверка, которая зависит от упорядочения (убывание или возрастание). Например для убывающей последовательности нам требуется найти самый большой элемент и перенести его в самое начало, именно это действие будет находиться во втором цикле. Итак, покажем на примере нашего массива действие второго цикла. В качестве сортировки возьмем возрастающую последовательность, то есть сортировка по возрастанию:
-3 | -5 |
|
-3 | -5 |
|
-3 | -5 |
|
-3 | -5 |
|
-3 | -5 |
|
-3 | -5 |
|
Итог первого прохода (итерации) первого главного цикла:
-5 | -3 |
Красным отмечен элемент, который в дальнейшем сравниваться не будет. Он зафиксирован как правильно-упорядоченный элемент.
Как можно заметить, наш второй цикл будет перемещать самый маленький элемент до самого начала. Затем, первый цикл сдвигается на один шаг, и второй цикл продолжает делать тоже самое, но уже минуя первый (нулевой) элемент массива, который после итерации (прохода) первого цикла стал минимальным, и нет смысла его вновь рассматривать. С увеличением количества проходов первого цикла будет уменьшаться количество рассматриваемых элементов во втором цикле, так как с каждым проходом главного цикла мы будем получать один упорядоченный элемент. Для наглядности продемонстрируем работу алгоритма на втором шаге первого цикла:
-5 | -3 |
|
-5 | -3 |
|
-5 | -3 |
|
-5 | -3 |
|
-5 | -3 |
|
В итоге получаем второй упорядоченный элемент, который в дальнейшем проверяться вторым циклом не будет:
-5 | -3 |
Это действие повторяется, пока первый главный цикл не дойдет до предпоследнего элемента массива – 5 (n – 2), ну, во-первых, почему n – 1 мы уже разбирали, а вот почему же мы вычеркиваем последний шестой индекс массива? Все дело в том, что переменная в первом цикле служит показателем для второго цикла, а именно она служит в качестве значения, до которого наш второй цикл спускается с последнего элемента n – 1. Мы ограничиваем этот спуск потому, что как мы убедились выше, нам вовсе не требуется сравнивать упорядоченные элементы. Второй цикл начинает с конца и в зависимости от стадии первого цикла он спускается до определенного неотсортированного элемента. В конце у нас должно быть лишь два сравнения. В данном конкретном случае с массивом M, это сравнение 6 элемента массива с 5. Предположим, что мы убрали ограничение на проверку последнего элемента, т.е вместо n – 2 цикл будет доходить до n – 1 (до последнего элемента массива). Войдем в ситуацию, когда цикл начнет проверять последний элемент т.е n – 1:
Второй вложенный цикл спускается до i + 1, то есть он ограничивает движение для отсортированных элементов, но если же наш первый цикл дойдет до последнего элемент, т.е i = 6, то 6 + 1 = 7, и тогда второй цикл будет пытаться проверить 7 элемент массива, которого у нас НЕТ с шестым, что противоречит логике метода. Именно поэтому мы убираем предпоследний элемент с первого главного цикла.
-5 | -3 |
|
Теперь продемонстрируем код на языке Delphi:
for i:= 0 to n – 2 do
begin
for j:= n – 1 down to i + 1 do
begin
if(M[ j – 1 ] > M[ j ])
swap(M[ j – 1 ], M[ j ]);
end;
end;
Для убывающей последовательности достаточно изменить знак в условии на противоположный. Соответствующая блок схема составлена в отдельном файле sortP_1.vsd (2007 год).
Второй случай. Сортируемые элементы отправляются с начала в конец.
В принципе этот способ ничем не отличается от вышеизложенного с небольшим лишь отличием: если в первом случае сортировка второго цикла велась с конца в начало, то в этом случае сортировка будет вестись с начала в конец. То есть:
-3 | -5 |
|
-3 | -5 |
|
-3 | -5 |
|
-3 | -5 |
|
-3 | -5 |
|
-3 | -5 |
|
-3 | -5 |
|
Итог первого прохода главного цикла. В данном случае мы просто сортируем начиная с конца, с самого большого значения, перенося его в конец, нежели в первом случае, в котором сортировка происходила от последнего элемента.
-3 | -5 |
Соответствующий Delphi код:
for i:= 0 to n – 2 do
begin
for j:= 0 to ((n – 2) – i) do
begin
if(M[ j ] > M[ j + 1 ])
swap(M[ j + 1 ], M[ j ]);
end;
end;
Во-первых, в первом главном цикле мы исключаем последний элемент по той же причине, что и в первом случае. Во-вторых, во втором вложенном цикле мы тоже исключаем последний элемент (n – 2), потому что мы идем от начала в конец, один из массивов имеет j + 1, это значит, что j сдвигается на единицу, если j будет доходить до n – 1, т.е в нашем случае до 6, M[ 6 + 1 ] = M[ 7 ], а это выход за пределы нашего массива, поэтому мы исключаем из списка номер этого элемента таким вот образом. Если в первом способе мы сужали начало, то в этом мы сужаем конец путем вычитанием из n – 2 переменную i, которая будет увеличиваться раз за разом.
Соответствующая блок схема предоставлена в файле sortP_2.vsd (2007 год).
Дата добавления: 2015-10-21; просмотров: 20 | Нарушение авторских прав
| <== предыдущая лекция | | | следующая лекция ==> |
| Эксплуатация гражданами автомобилей, мотоциклов или других механических ТС, у которых содержание загрязняющих веществ в выбросах либо уровень шума, производимого ими при работе, превышает | | | Общие сведения о красках Tamiya |