Методы сортировки. 
Методы сортировки

МЕТОДЫ СОРТИРОВКИ При разработке программного обеспечения очень распространенной операцией является сортировка значений, т. е. расположение списка элементов в некотором порядке (например, слова по алфавиту или числа в возрастающем или убывающем порядке).

Существует множество алгоритмов сортировки элементов. Наиболее простой из них — метод «пузырька». Алгоритм реализуется в виде двух вложенных циклов. Во внутреннем цикле просматриваются по порядку все элементы массива, попарно сравниваются рядом стоящие элементы, и если второй больше первого (при сортировке по убыванию) элементы меняются местами. Параметром внутреннего цикла является индекс (номер) элемента массива. Для полной сортировки такая перестановка должна быть выполнена n-1 раз, где n — количество элементов в массиве. Для этого организуется внешний цикл, параметром которого является шаг сортировки.

Пример. Отсортировать элементы одномерного массива целых чисел по возрастанию.

На рисунке 1 приведена последовательность перестановки элементов.

Рисунок 1. Сортировка методом «пузырька».

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

На рисунке 2 приведена блок-схема рассмотренного алгоритма.

Рисунок 2. Блок-схема алгоритма сортировки методом «пузырька».

Переменная m введена для возможности обмена значениями между двумя переменными, k отвечает за шаги сортировки.

Программа на языке С++ по данному алгоритму будет выглядеть следующим образом.

Рисунок 3. Программа сортировки элементов массива методом «пузырька».

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

Более эффективным является метод прямого выбора.

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

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

сортировка значение программный обеспечение.

Рисунок 4. Сортировка методом прямого выбора Фрагмент программы, с помощью которого реализуется сортировка методом прямого выбора, приведен ниже.

// сортируем элементы массива по возрастанию.

const int n=20;

int list [n];

int temp;//переменная для временного хранения при обмене значениями.

int i;//переменная управления циклом (номер элемента массива).

int k;//переменная управления циклом (номер шага сортировки).

int nmin;//номер минимального значения.

for (к=0; i < к 1; i++).

{.

nmin = к;

// ищем номер минимального элемента среди значений list [ i … n -1].

for (i = k+1; i< n; i++).

if (list[i] < list[ nmin ]) nmin = i;

//меняем местами list[ nmin ] и list[ k ].

temp = list[ nmin ];

list[ nmin ]= list[ k ];

list[ k ] = temp;

}.

}.

Следует отметить, что поиск минимального значения во внутреннем цикле происходит в оставшейся части списка.

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