Структура данных и алгоритмы Вопрос 3.1. Как реализуется сортировка методом "пузырька" и какова временная сложность этого метода сортировки

Сортировка - процесс, позволяющий упорядочить множество однотипных данных в возрастающем или убывающем порядке.

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

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

Пусть задан массив array из n элементов. Сравниваются пары значений array[i] и array[i+1] в интервале от 1 до n-1: если array[i] > array[i+1], то значения меняются местами. Алгоритм останавливается, когда больше нечего переставлять; в этом случае массив отсортирован.

В общем случае пузырьковая сортировка - самый худший из всех когда-либо изобретенных методов упорядочивания массивов данных. Для алгоритма пузырьковой сортировки количество выполняемых сравнений всегда одинаково и равно , где n - количество сортируемых значений. В наилучшем случае (если список уже отсортирован) количество перестановок равно нулю. Количество перестановок в среднем и в худшем случаях равны соответственно:

В лучшем случае: 0, В среднем случае: , В худшем случае:

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

void bubble_sort(int *array, int n)

{

int i, changed, temp;

do {

changed = 0;

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

if (array[i] > array[i+1]) {

changed = 1;

temp = array[i];

array[i] = array[i+1];

array[i+1] = temp;

}

} while (changed);

}

Вопрос 10.1. Как реализуется сортировка вставками и какова временная сложность этого метода сортировки

Сортировка - процесс, позволяющий упорядочить множество однотипных данных в возрастающем или убывающем порядке.

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

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

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

В отличие от пузырьковой сортировки и сортировки методом отбора количество сравнений, имеющих место в процессе сортировки методом вставки, зависит от исходной упорядоченности списка. Если список не упорядочен, то количество сравнений равно . В наилучшем, среднем и наихудшем случаях количество сравнений будет равно:

В лучшем случае: 2(n-1), В среднем случае: , В худшем случае:

По этой причине в наихудших случаях алгоритм вставки так же плох, как и пузырьковый метод или метод выбора; в среднем случае он лишь немногим лучше этих методов. Однако, алгоритм сортировки методом вставки обладает двумя реальными преимуществами. Во-первых, его поведение естественно. Это означает, что если массив уже отсортирован в нужном порядке, алгоритм проводит наименьшее количество вычислений, а если массив отсортирован в порядке, обратном требуемому (наихудший случай), - его работа наиболее интенсивная. Благодаря этому алгоритм отлично работает с почти упорядоченными массивами. Другим преимуществом является то, что этот метод не изменяет порядка следования одинаковых ключей. Это означает, что если список уже отсортирован по двум ключам, то после сортировки методом вставки он останется отсортированным по обоим ключам.

void insert_sort(int *array, int n)

{

int i, j, temp;

for (i = 1; i < n; i++) {

temp = array[i];

for (j = i-1; j >= 0 && temp < array[j]; j--)

array[j+1] = array[j];

array[j+1] = temp;

}

}