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

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

Обычно сортировку подразделяют на два класса: внутреннюю и внешнюю. При внутренней сортировке все элементы хранятся в оперативной памяти, таким образом, как правило, это сортировка массивов. При внешней сортировке — элементы хранятся на внешнем запоминающем устройстве, это сортировка содержимого файлов.

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

Сортировать массив можно:

1) по возрастанию – каждый следующий элемент больше предыдущего: a [1]< a [2]< …< a [ n ];

2) по неубыванию – каждый следующий элемент не меньше предыдущего: a [1]£ a [2] £ …£ a [ n ];

3) по убыванию - каждый следующий элемент меньше предыдущего: a [1]> a [2]> …> a [ n];

4) по невозрастанию – каждый следующий элемент не больше предыдущего: a [1]≥ a [2] ≥ …≥ a [ n ].

Рассмотрим некоторые методы внутренней сортировки.

2. Метод «пузырька» – метод простого обмена

Производится последовательное упорядочение смежных пар элементов массива: x [1] и x [2], x [2] и x [3], … x [ N -1] и x [ N ]. Если в паре первый элемент больше второго, то элементы меняются местами. Далее, таким же образом, обрабатываем следующую пару. В итоге, после N –1 сравнения максимальное значение переместится на место элемента X [ N ], т.е. " вверху" окажется самый " легкий" элемент – отсюда аналогия с пузырьком. Следующий проход делается аналогичным образом до второго сверху элемента (X [ N –1]), в результате второй по величине элемент поднимется на правильную позицию и т.д. Для сортировки всего массива нужно выполнить N –1 проход по массиву. При первом прохождении нужно сравнить N –1 пар элементов, при втором – N –2 пары, при k -м прохождении – N ‑ k пар.

Например, дан массив из 5 элементов: 5 8 1 6 7. Упорядочить его по возрастанию элементов.

1 прохождение: 5–1=4 сравнения (см. Таблица 1. Трассировка методом пузырька. Первый проход по массиву.

Таблица 1. Трассировка методом пузырька. Первый проход по массиву.

	Попарное сравнение элементов массива	Действие
1.		Нет обмена
2.		1«8
3.		6«8
4.		7«8

2 прохождение: 5–2=3 сравнения

5 1 6 7 8

3 прохождение: 5–3=2 сравнения

1 5 6 7 8

4 прохождение: 5–4=1 сравнение

1 5 6 7 8

Программа сортировки методом «пузырька»:

include < iostream>

#include < locale.h>

using namespace std;

void input(int *m, int & n) // Имя массива является адресом его начала.

{ // Или void input(int m[], int & n)

cout< < " Введите количество элементов массива ";

cin> > n;

for (int i=0; i< n; i++)

{

cout< < " a[" < < i< < " ]=";

cin> > m[i]; // Конструкция a[i] эквивалентна *(a + i)

}

}

void print (int *m, int n)

{

for (int i=0; i< n; i++)

cout< < m[i]< < " ";

cout< < " \n";

}

void sort_bubble (int *m, int n) // Сортировка пузырьком

{

int i, j, t;

for (i=0; i< n-1; i++)

for(j=0; j< n-i-1; j++)

if (m[j]> m[j+1])

{

t=m[j];

m[j]=m[j+1];

m[j+1]=t;

}

}

void main()

{

setlocale(LC_ALL, " rus"); // Меняем кодировку для консольного приложения

const int nmax=20;

int n, a[nmax];

input(a, n);

cout< < " Исходный массив: \n";

print(a, n);

sort_bubble(a, n);

cout< < " Отсортированный массив: \n";

print(a, n);

}

Среднее число сравнений и обменов имеют квадратичный порядок роста: О (n ²), отсюда можно заключить, что алгоритм пузырька очень медленен и малоэффективен.

3. Модифицированный «пузырек»

Пример. Упорядочить массив из 6 элементов: 12, 3, 5, 7, 9, 10 по неубыванию методом «пузырька».

При сортировке методом простого обмена («пузырька») возможна ситуация, когда на каком-либо из проходов не произошло ни одного обмена. Это значит, что все пары расположены в правильном порядке, так что массив уже отсортирован. И продолжать процесс не имеет смысла (особенно, если массив был отсортирован с самого начала).

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

Поэтому лучше использовать «модифицированный пузырек», который отсортирует за один просмотр.

Программа:

void modif_bubble(int *m, int n) // Модифицированный пузырек

{

int i=n, t; // Длина неотсортированной части массива

int f;

do {

f=0; //Предположим, что массив является отсортированным

for (int k=0; k< i-1; k++)

if (m[k]> m[k+1])

{

t=m[k]; m[k]=m[k+1]; m[k+1]=t; // Обмен

f=1; // Массив был неотсортированным

}

i--;

} while (f & & i> 1);

}