Цитата мудреца

Голосование

Система Orphus. Если вы заметили ошибку на сайте, нажмите сюда.
Загружается, подождите...
Начало сайта Материалы сайта Программы Статьи для начинающих программистов
Версия для слабовидящих
Версия для печати

Сортировка массива

С января 2004 года журнал "Магия ПК" начал публиковать мои статьи для начинающих программистов. В них я рассказываю как прописные истины (применение различных операторов языка Паскаль), так и делюсь "секретами" (различными подходами к решению тех или иных задач).

Идея начать цикл статей посвящённых азам и секретам программирования родилась спонтанно. Один мой знакомый начал изучать программирование. Выучив несколько языков, которые требовали в институте, он так и не смог понять принцип, как же писать программы, как подойти к решению тех или иных задач. Именно для помощи в таких ситуациях, я и решил начать писать. Для этого пригодился и опыт преподавания языков программирования на компьютерных курсах (1990 г.).

Эти статьи предназначены для начинающих программистов, точнее для тех, кто решил попробовать себя в программировании. Самое первое препятствие на этом пути — страх перед трудностями, перед кажущейся сложностью процесса составления программ. Для того, чтобы помочь упростить сложные задачи — эти статьи.
  Нет сообщений • Страница 1 из 1

Сортировка массива

Зачем же использовать те языки, в которых не реализованы процедуры сортировки массивов, спросите вы. Да может быть и не стоит их использовать. Только не всегда предоставляется возможность выбрать язык, на котором будет писаться программа. Но нас не должна напугать необходимость написания такой процедуры вручную. Более того, мы должны быть уверены, что процедура, которую мы напишем, будет выполняться ни чуть не хуже стандартной встроенной, а может быть, в чём-то и лучше. Да, да. Она обязательно будет лучше хотя бы потому, что за любую универсальность надо чем-то платить: скорей всего это будут лишние операторы, подготавливающие данные, сравнивающие эти данные с допустимыми значениями. Мы же, подготавливая свою процедуру для конкретного случая, уж позаботимся о том, чтобы параметры, передаваемы ей, были корректными. Благо язык Паскаль уже на этапе компиляции позволяет исключить множество возможных ошибок тем, что проверяет типы и размеры переменных.


Изображение

Итак, начнём. Предположим, что у нас есть массив строковых переменных, который нам надо отсортировать.


На самом деле нет никакой разницы, что будет сортировать наша процедура. Просто сортировка строк — достаточно наглядна. В то же время, когда сравниваются два числовых значения, результат этого сравнения достаточно предсказуем. Со строками же намного сложнее. В Паскале, если сравнивать две строки, можно получить результат, что одна будет больше, а другая меньше. Это происходит следующим образом: сравниваются первые символы; та строка, чей код первого символа меньше, считается меньшей. Если же первые символы одинаковы, то сравниваются вторые, и так далее. Стоит заметить, что код заглавных букв меньше, чем код строчных букв. Поэтому при сортировке строк, начинающихся на заглавные и строчные буквы, первыми будут стоять заглавные. Есть возможность задать сравнение строк без учёта регистра, но это уже не входит в рамки данной статьи.


А теперь код процедуры:


Код: Выделить всё
const
  ElementCount = 10;

type
  TElement = string; 
  TSimpleArray = array [1..ElementCount] of TElement;

procedure ArrSort(var Source: TSimpleArray; Progress: boolean);
var
  i, j: integer;
  tmp: TElement;
begin
  for i:=2 to ElementCount do
    for j:=i downto 2 do
      if ((Source[j] < Source[j-1]) and Progress) or
         ((Source[j] > Source[j-1]) and not Progress)
        then
          begin
            tmp := Source[j-1];
            Source[j-1] := Source[j];
            Source[j] := tmp;
          end;
end;

Это стандартный и достаточно распространённый алгоритм сортировки. Но прежде чем его проанализировать, давайте посмотрим, что мы подготовили для него.


Константой ElementCount мы определяем количество элементов массива. Тип TSimpleArray определяет саму структуру массива. Тип TElement определяет тип элементов массива. Почему мы завели отдельный тип для элементов массива, а не указали его прямо в определении массива, мы разберём позже.


Сама же процедура сортировки имеет два входных параметра: Source — сам массив и Progress — логическая переменная, указывающая направление сортировки: если Истина, значит сортировка возрастающая. Заметьте, что первый параметр мы передаём в процедуру не по значению, а по ссылке (ключевое слово var). Это сделано по двум причинам: во-первых, результат сортировки окажется в том же массиве, который мы передали в качестве параметра. По правилам языка Паскаль, впрочем, как и во многих других языках, переменные, переданные в качестве параметров по значению, не могут быть изменены. Это значит, что в качестве параметра мы можем при написании кода программы просто вписать значение (строку или число). Соответственно, изменение этого значения бессмысленно. Если мы передаём параметр как ссылку на переменную, то мы не можем вместо него сразу вписать значение (это должна быть именно переменная). Зато внутри процедуры мы можем изменить содержимое этой переменной, что бывает очень полезно, как в данном случае. Вторая же причина, по которой стоит использовать передачу параметров по ссылке на переменную, это то, что передача таких параметров занимает меньше памяти. Все параметры, передаваемые процедуре, а также все внутренние переменные располагаются в стеке (специальной части памяти, выделенной для работы программы). Размер этого стека ограничен, и нерациональное его использование может существенно замедлить работу программы, т.к. операционной системе придётся заботиться о расширении стека во время работы программы. Передавая большие переменные по значению, программа полностью загружает их в стек, в то время как для переменных, переданных по ссылке, в стеке хранится только ссылка на область памяти, где эта переменная расположена.


Теперь поговорим о внутренних для процедуры переменных. Переменные i и j являются счётчиками в циклах. Здесь хочу отметить два момента: всегда переменные, используемые в качестве счётчика в цикле for, должны быть описаны как внутренние в процедуре (иначе компилятор возмутится). И ещё, существуют негласные правила: использовать в качестве переменных-счётчиков в циклах одиночные буквы, начиная с i (j, k, l, m…), точно так же, как координаты принято обозначать последними буквами алфавита (x, y, z). Первые же буквы алфавита (a, b, c, d…) принято использовать для временных переменных любого типа, но с условием, что их тип одинаков между собой. Остальные же переменные рекомендуется называть более-менее осмысленными именами.


Ещё одна переменная в локальном списке — tmp. Это переменная для временного хранения одного элемента из массива, который мы будем сортировать. Вот здесь нам и понадобился именованный тип этой переменной. Дело в том, что при любом программировании — будь то создание программ, написание сценариев и даже создание документов в MS Word — следует придерживаться такого правила: любой элемент, любое значение, если оно используется больше чем один раз, должно быть описано отдельно. Это нужно для того, чтобы, если придётся изменить значение этого элемента, нам не пришлось разыскивать его по всему тексту программы, а, изменив описание в одном месте, мы изменим все вхождения этого элемента в тексте. Именно для этого и используются типы (стили).


Теперь приступим к рассмотрению алгоритма работы процедуры.


Самый первый цикл проведёт нас от второго элемента массива к самому последнему. Почему от второго? Да потому что сортировка вообще имеет смысл, если элементов в массиве больше одного. И ещё потому, что мы изначально делаем предположение, что первый элемент уже стоит на своём месте, а все перемещения начинаем делать только со второго.


Что же мы будем делать с элементами массива, начиная со второго? Мы будем их сравнивать с предыдущим элементом. Если текущий больше предыдущего, то никаких действий производить не надо (мы разбираем вариант сортировки по возрастанию). Если же текущий элемент меньше предыдущего, то мы должны их поменять местами. Но этого мало. Мы должны снова проверить его в сравнении с предыдущим, и если он окажется снова меньше, то повторить перестановку. Именно для этого мы организовали второй цикл, который начинается с текущего элемента, определяемого первым циклом, и заканчивается вторым элементом, который, в самой последней итерации будет сравниваться со своим предыдущим, т.е. первым. Позже, на примере, мы рассмотрим, как это всё происходит.


Теперь разберём операцию проверки элементов. Согласитесь, что перемещать элемент вверх по массиву мы должны в двух случаях: 1) если у нас идёт сортировка по возрастанию и элемент меньше своего предшественника; 2) если мы сортируем по убыванию и элемент, который мы проверяем, больше предыдущего. Если вы посмотрите на выражение в условном операторе if, то увидите, что мы именно это и написали.


Как же мы меняем элементы местами? Для этого нам понадобится наша временная переменная tmp. Мы сохраняем в ней вышестоящий элемент. Затем записываем в эту ячейку текущий элемент, и в завершение возвращаем сохранённый элемент в текущую ячейку.


Изображение

А сейчас давайте рассмотрим работу этой процедуры на примере:


Рассмотрим ситуацию, когда элемент "в" уже занял свою позицию во главе списка, т.е. поменялся с элементом "однажды" местами. Следующий элемент "студёную" не двигался, т.к. он является больше своего вышестоящего собрата и должен оставаться на своём месте. Следующим шагом в цикле по переменной i мы должны заниматься элементом "зимнюю". Сравнивая его с элементом "студёную" мы видим, что их надо поменять местами, что мы и делаем. То же самое мы сделаем ещё раз (уже благодаря циклу по переменной j), когда будем сравнивать переставленный элемент "зимнюю" с элементом "однажды".


Но в этом алгоритме есть и излишества, которые при больших размерах массива могут приводить к существенному замедлению в работе процедуры. Обратите внимание, что проверка на необходимость переставлять элементы происходит внутри обоих циклов. Это означает, что независимо от начального положения элементов, все итерации пройдут от первой до последней.


Рассмотрим вариант, когда текущим становится элемент "пору". Его действительно необходимо переставить на одну позицию вверх. Но остальные действия с ним не нужны. Наша же процедура сначала сравнит его с элементом "однажды", поймёт, что ничего с этим делать не надо, но на этом не остановится. Поскольку перестановок не было, в следующей итерации цикла по переменной j будет сравниваться элемент "однажды" с элементом "зимнюю". Согласитесь, это бессмысленно. Ещё более глупо будут казаться эти действия после того, как мы поймём на следующем шаге, что элемент "я" вообще двигать не надо.


Поэтому, давайте попробуем оптимизировать эту процедуру, чтобы избежать лишних движений.


Код: Выделить всё
procedure ArrSortM(var Source: TSimpleArray; Progres: boolean);
var
  i, j: integer;
  tmp: string;
begin
  for i := 2 to MaxArrIndex do
    begin
      j := i;
      while (j > 1) and (((Source[j] < Source[j - 1]) and Progres) or
        ((Source[j] > Source[j - 1]) and not Progres)) do
        begin
          tmp := Source[j - 1];
          Source[j - 1] := Source[j];
          Source[j] := tmp;
          j := j - 1;
        end;
    end;
end;

Что изменилось в модернизированной процедуре? Обратите внимание на второй вложенный цикл. Теперь это не цикл, выполняющийся определённое число раз (for), а цикл по условию (while). Это значит, что мы сначала проверяем, нужно ли нам производить какие-либо действия с текущим элементом, или нет. И если действия с ним не нужны, то мы сразу переходим к следующему элементу. Но переменная j всё же присутствует. Она, как и прежде служит счётчиком-указателем на передвинутый нами вверх элемент. Только управляем мы ею вручную: сначала присваиваем ей значение переменной i, а потом уже, если перемещение было произведено, уменьшаем её на единицу.


Хочу обратить ваше внимание на то, что самым первым условием, проверяемым в цикле while, является проверка на то, чтобы переменная j оставалась больше единицы. Это важно, потому что, если это условие не проверить, то может возникнуть ошибка индекса массива на этапе проверки значений, когда мы попытаемся сравнить Source[j] с Source[j - 1]. В этом случае в последнем сравниваемом выражении будет обращение к индексу 0, чего не предусмотрено в нашей процедуре.


Порядок проверки условий в любом языке программирования всегда имеет смысл. Дело в том, что реализация логических выражений такова, что программа не заставляет компьютер совершать лишние действия. Представьте себе, что у нас есть два условия, соединённые между собой оператором "И" (and). Тогда, если первое условие дало результат Истина, то компьютер начинает проверять второе условие. Если же первое условие дало Ложь, то проверка остальных смысла не имеет, т.к. не зависимо от их результатов, общий будет Ложь. То же самое происходит и с оператором "ИЛИ" (or). Дальнейшие условия не проверяются, как только в одном из условий, соединённых этим оператором, встретилась Истина.


Таким образом, мы сначала проверяем допустимость индекса j, а потом уже условие перемещения элементов нашего массива.


Все эти оптимизации без сомнения облегчили работу компьютеру, а значит, увеличили скорость выполнения операции. Но вам может показаться, что у нас увеличился сам размер кода процедуры. Да, это так: было 6 операций, а стало 7. Но это только лишняя работа компилятора. Смею вас уверить, что для процессора работы не прибавилось, и оптимизированная процедура в откомпилированном виде будет занимать столько же байт, сколько и первая. А дело всё в том, что компилятор разворачивает оператор for на составные элементарные действия: 1) инициализация переменной-счётчика (присваивание ей начального значения); 2) проверка её на достижение предельного значения; 3) увеличение (уменьшение) её на единицу за каждый цикл. Мы избавились от оператора for и повторили те же самые действия вручную.


В заключение хочу добавить, что вы можете написать отдельную функцию для выяснения приоритетов между элементами массива и вставить вызов этой функции в проверку условия цикла. Это может понадобиться, когда нужный вам порядок расположения элементов будет не так однозначен, как простое сравнивание элементов.

Ответить

  Нет сообщений • Страница 1 из 1

Вернуться в Статьи для начинающих программистов



Кто сейчас на сайте

Зарегистрированные пользователи: Bing [Bot], Yandex [bot]