Сортировка массива методом прямого выбора в Delphi

Сортировка массива методом прямого выбора

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

a[l] & а[2] < . . .& a[SIZE]

где SIZE — верхняя граница индекса массива.

Примечание:

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

Существует много методов (алгоритмов) сортировки массивов.

Рассмотрим два из них:

метод прямого выбора;
метод прямого обмена.

Сортировка методом прямого выбора

Алгоритм сортировки массива по возрастанию методом прямого выбора может быть представлен так:

Просматривая массив от первого элемента, найти минимальный элемент и поместить его на место первого элемента, а первый — на место минимального.
Просматривая массив от второго элемента, найти минимальный элемент и поместить его на место второго элемента, а второй — на место минимального.
И так далее до предпоследнего элемента.

Ниже представлена программа сортировки массива целых чисел по возрас

танию, диалоговое окно которой изображено на рис. 5.15.

Процедура сортировки, текст которой приведен в листинге 5.9, запускается нажатием кнопки Сортировка (Buttoni). Значения элементов массива вводятся из ячеек компонента stringGridj. После выполнения очередного цикла поиска минимального элемента в части массива процедура выводит массив в поле метки (Label2).

Листинг 5.9. Сортировка массива простым выбором

Показать / Скрыть текст

На рис. 5.16 приведено диалоговое окно профаммы после завершения процесса сортировки.

Сортировка методом обмена

В основе алгоритма лежит обмен соседних элементов массива. Каждый эле

мент массива, начиная с первого, сравнивается со следующим, и если он

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

менты с меньшим значением продвигаются к началу массива (всплывают),

а элементы с большим значением — к концу массива (тонут). Поэтому данный

метод сортировки обменом иногда называют методом "пузырька". Этот процесс

повторяется столько раз, сколько элементов в массиве, минус единица.

На рис. 5.17 цифрой 1 обозначено исходное состояние массива и переста

новки на первом проходе, цифрой 2 — состояние после перестановок на

первом проходе и перестановки на втором проходе, и т. д.

Сортировка массива методом обмена

В основе алгоритма лежит обмен соседних элементов массива. Каждый элемент массива, начиная с первого, сравнивается со следующим, и если он больше следующего, то элементы меняются местами. Таким образом, элементы с меньшим значением продвигаются к началу массива (всплывают),а элементы с большим значением — к концу массива (тонут). Поэтому данный метод сортировки обменом иногда называют методом "пузырька". Этот процессповторяется столько раз, сколько элементов в массиве, минус единица. На рис. 5.17 цифрой 1 обозначено исходное состояние массива и перестановки на первом проходе, цифрой 2 — состояние после перестановок напервом проходе и перестановки на втором проходе, и т. д.

На рис. 5.18 приведено диалоговое окно программы сортировки массива методом обмена.

Процедура сортировки, текст которой приведен в листинге 5.10, запускается нажатием кнопки Сортировка (Buttonl). Значения элементов массива вводятся из ячеек компонента stringGridi. Во время сортировки, после выполнения очередного цикла обменов элементов массива, программа выводит массив в поле метки LabeL2.

Листинг 5.10. Сортировка массива методом обмена

Показать / Скрыть текст

Следует отметить, что максимальное необходимое количество циклов проверки соседних элементов массива равно количеству элементов массива минус один. Вместе с тем возможно, что массив реально будет упорядочен за меньшее число циклов. Например, последовательность чисел 5 1 2 3 4 , если ее рассматривать как представление массива, будет упорядочена за один цикл, и выполнение оставшихся трех циклов не будет иметь смысла.

Поэтому в программу введена логическая переменная changed, которой перед выполнением очередного цикла присваивается значение FALSE. Процесс сортировки (цикл repeat) завершается, если после выполнения очередного цикла проверки соседних элементов массива (цикл for) ни один элемент массива не был обменен с соседним, и, следовательно, массив уже упорядочен.

На рис. 5.19 приведено диачоговое окно программы сортировки массива методом обмена после завершения процесса сортировки.

Об остальных алгоритмах сортировки Вы можете узнать на сайте: алгоритмы сортировки.

DelphiComponent.ru - бесплатно видеоуроки по Delphi, статьи, исходники