1.Алгоритмы сортировки
В данной главе будут описаны все алгоритмы сортировки, которые были использованы в программе – пузырьком, выбором (локальным минимумом), вставками и быстрой.
1.1.Сортировка методом пузырька
Метод сортировки пузырьком на практике используется редко, в силу его слабой эффективности.
Суть метода заключается в переборе всех элементов массива и, если на текущей итерации некоторая пара соседних элементов массива расположены в неправильном порядке, то они меняются местами. После этого, перебор всех элементов начинается до отсортированного элемента на предыдущем проходе, и так далее до прохождения всех проходов (n). Таким образом, после каждого прохода самый «легкий» элемент окажется на самом верху перед более «легкими» элементами. Если образно представить массив вертикально от 0-го элемента сверху и n-1 элемента снизу (где n – кол-во элементов массива), то при каждом проходе по одному «легкому» элементу массива будут подниматься наверх, как пузырьки, отсюда и название метода.
Переведем эту задачу в алгоритм для написания в дальнейшем его кода:
Так, как нужно повторить «всплытие» для каждого элемента массива, нужно создать цикл, с кол-вом итераций, равным кол-ву элементов массива. Каждое «всплытие» элемента будет устанавливаться в начало массива до более «легкого» элемента, т.к. на каждом следующем проходе будут «всплывать» все более «тяжелые» элементы, поэтому ориентируем цикл от минимального к максимальному индексам:
for (i=0; i<size; i++)
Для «всплытия» более «легкого» элемента наверх, перебираем массив от нижнего элемента до элемента, который уже «всплыл» на предыдущих проходах. Для этого создаем внутренний цикл с счетчиком-переменной, меняющейся от нижнего индекса массива до уже упорядоченного элемента i:
for (j=size-1; j>i; j--)
Для «всплытия» более «легкого» элемента наверх, поменяем местами соседнюю пару элементов, если они находятся в неправильном порядке. Для замены местами, используем вспомогательную переменную:
if (array[j-1]>array[j]) {
x=array[j-1];
array[j-1]=array[j];
array[j]=x;
}
Таким образом, блок-схема и весь алгоритм выглядит так:
Рис. 1.1. Блок-схема сортировки Пузырьком
long i,j,x;
for (i=0; i<size; i++){
for (j=size-1; j>i; j--){
if (array[j-1]>array[j]) {
x=array[j-1];
array[j-1]=array[j];
array[j]=x;
}
}
}
Среднее число сравнений и обменов имеют квадратичный порядок роста: Theta(n2), отсюда можно заключить, что алгоритм пузырька очень медленен и малоэффективен. Поскольку одинаковые элементы не меняются местами, можно сделать вывод, что алгоритм устойчивый. Поведение алгоритма неестественное, т.к. по уже отсортированным до алгоритма элементам, также делаются проходы и сравнения.
1.2.Сортировка методом Выбора (метод локального минимума)
Суть метода заключается в определении минимального элемента в неотсортированной части массива и замена его местами с начальным элементом неотсортированной части. При следующем проходе неотсортированная часть уменьшается на 1. По сравнению с методом Пузырька, кол-во присваиваний значительно уменьшается.
Переведем эту задачу в алгоритм для написания в дальнейшем его кода:
Для нашей задачи, нужно перебрать все элементы массива, а на каждом шаге i, последовательность array[0]…array[i] будет отсортирована. Для этого создаем цикл с кол-вом итераций, равным кол-ву элементов массива:
for (i=0; i<size; i++)
На каждом шаге i, ищем минимальный элемент в неотсортированной части (array[i+1]…array[n-1]). Для этого создаем внутренний цикл с счетчиком-переменной j, меняющейся от начала неотсортированной части [i+1] до конца массива и проверяем в условии является ли меньше первого элемента неотсортированной части или нет и запоминаем наименьший элемент и его индекс в вспомогательных переменных:
for (j=i+1; j<size; j++)
if (array[j] < x) {
k=j;
x=array[j];
}
После того, как наименьший элемент будет найден, поменяем местами первый элемент неотсортированной части с наименьшим:
array[k]=array[i];
array[i]=x;
В случае, если наименьший элемент не будет найдет, в п.2 вставятся не то, что нужно, т.к. условие не выполнится и вспомогательным переменным ничего не присвоится. Чтобы этого избежать, перед внутренним циклом в п.2 присвоим вспомогательным переменным последний элемент отсортированной части:
k=i;
x=a[i];
Таким образом, блок-схема и весь алгоритм выглядит так:
Рис. 1.2. Блок-схема сортировки Выбором
long i,j,k,x;
for (i=0; i<size; i++){
k=i;
x=a[i];
for (j=i+1; j<size; j++)
if (array[j] < x) {
k=j;
x=array[j];
}
array[k]=array[i];
array[i]=x;
}
Для нахождения наименьшего элемента из n+1 рассматримаемых алгоритм совершает n сравнений. С учетом того, что количество рассматриваемых на очередном шаге элементов уменьшается на единицу, общее количество операций:
n + (n-1) + (n-2) + (n-3) + ... + 1 = 1/2 * ( n2+n ) = Theta(n2).
Таким образом, так как число обменов всегда будет меньше числа сравнений, время сортировки растет квадратично относительно количества элементов.
Алгоритм не использует дополнительной памяти: все операции происходят "на месте".
Поскольку равные элементы не меняются местами, алгоритм устойчивый.