Структура данных и алгоритмы

Вопрос 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);

}