Теоретические сведения. Задача сортировки является такой же базовой, как задача поиска

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

В общем случае сортировку следует понимать как процесс перегруппировки, заданного множества объектов в определенном порядке.

Сортировка применяется для облегчения поиска элементов в упорядоченном множестве. Задача сортировки одна из фундаментных в программировании.

Сортировка – это процесс перегруппировки заданного множества объектов в некотором установленном порядке.

Сортировки массивов подразделяются по быстродействию. Существуют простые методы сортировок, которые требуют n*n сравнений, где n – количество элементов массива и быстрые сортировки, которые требуют n*ln(n) сравнений. Простые методы удобны для объяснения принципов сортировок, т. к. имеют простые и короткие алгоритмы. Усложненные методы требуют меньшего числа операций, но сами операции более сложные, поэтому для небольших массивов простые методы более эффективны.

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

· сортировка методом «пузырька» (простого обмена);

· сортировка методом простого выбора (простой перебор);

· сортировка методом простого включения (сдвиг-вставка, вставками, вставка и сдвиг).

Сортировка методом «пузырька» (простого обмена)

Алгоритм попарного сравнения в литературе называют «методом пузырька», проводя аналогию с пузырьком, поднимающимся со дна бокала с газированной водой. По мере всплывания пузырек сталкивается с другими пузырьками и, сливаясь с ними, увеличивается в объеме. Чтобы аналогия стала очевидной, нужно считать, что элементы массива расположены вертикально друг над другом, и их нужно так упорядочить, чтобы увеличивались сверху вниз.

Алгоритм состоит в повторяющихся проходах по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает – массив отсортирован. При проходе алгоритма, элемент, стоящий не на своём месте, «всплывает» до нужной позиции.

/*Описание функции сортировки методом "пузырька" (простым обменом)*/

void BubbleSort (int k,int x[max]) {

int i,j,buf;

for (i=k-1;i>0;i--)

for (j=0;j<i;j++)

if (x[j]>x[j+1]) {

buf=x[j];

x[j]=x[j+1];

x[j+1]=buf;

}

}