На главную

 

 

Сайт основан 1 марта 2003 года

= Основы алгоритмизации и программирования =


Одномерные массивы.
Методы сортировки элементов массива


Существует большое разнообразие алгоритмов сортировки элементов массива.

Рассмотрим три наиболее простых способа сортировки, которые интересны тем, что практически все другие возможности упорядочивания являются производными этих трёх:

-          метод выбора;

-          метод вставок;

-          метод обмена – «всплывающие пузырьки».

Метод выбора:

Этот способ является естественным способом, о котором вспоминают в первую очередь, когда приходиться упорядочивать последовательности величин.

Идея его такая: найдём в массиве наименьший элемент и поменяем его местами с первым элементом. После этого, те же действия выполним с другими (без первого) элементами, начиная со второго, потом с третьего и т.д., пока не останется один элемент - последний. Он будет наибольшим.

Работу алгоритма можно изобразить так:

Первый проход

Второй проход

Третий проход
в начало текста

Метод вставок:

Пусть в заданном массиве первые i-1 элементов уже отсортированы по возрастанию. Найдём в этой части массива место для i-го элемента. Для этого будем сравнивать его по порядку со всеми элементами, которые стоят левее, начиная с соседнего, пока не окажется, что некоторый a[k]<=a[i]. После этого сдвинем часть массива a[k+1], a[k+2], …, a[i-1] на один элемент вправо и освободим таким образом место a[k+1] для элемента a[i], куда его и поставим. Потом перейдём к элементу a[i+1] и повторим для него тоже, что делали для a[i]. Потом перейдём к a[i+2] элементу и т.д., пока не дойдём до конца массива.

Первый проход

Второй проход

Третий проход

Четвёртый проход
в начало текста

Метод обмена:

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

Идея сортировки методом обмена заключается в многоразовых попарных сравнениях элементов, которые находятся рядом, и перестановки этих элементов в заданном порядке.

Сортировка начинается сравнением двух последних элементов массива: а[n] и a[n-1]. Тот, который имеет меньшее значение «всплывает». Потом сравнивается пара элементов а[n-1] и a[n-2], потом а[n-2] и a[n-3] и т.д. до первого элемента. За этот проход на первое место станет наименьший элемент массива.

Другой проход выполняется таким же образом, но уже без первого элемента, который уже нашёл своё место.

Третий проход выполняется без первых двух элементов и т.д. Последний проход выполняется для двух а[n] и a[n-1] элементов, и последнее место займёт наибольший элемент.

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

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

Первый проход

Второй проход

Третий проход
в начало текста

 


Наверх

На главную

 

Дизайн : WWS corporation & ROKI company.