Сортировка пузырьком

Расположим массив сверху вниз, от нулевого элемента - к последнему.

Идея метода: шаг сортировки состоит в проходе снизу вверх по массиву. По пути просматриваются пары соседних элементов. Если элементы некоторой пары находятся в неправильном порядке, то меняем их местами.

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

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

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

i-цикл от 0 до size с шагом 1

j-цикл от size-1 до i с шагом -1

если a[j-1] > a[j], то

x = a[j-1]

a[j-1] = a[j]

a[j] = x

все если

все j-цикл

все i-цикл

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

Сортировка выбором

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

Будем строить готовую последовательность, начиная с левого конца массива. Алгоритм состоит из n последовательных шагов, начиная от нулевого и заканчивая (n-1)-м.

На i-м шаге выбираем наименьший из элементов a[i]... a[n] и меняем его местами с a[i]. Последовательность шагов при n=5 изображена на рисунке ниже.

Вне зависимости от номера текущего шага i, последовательность a[0]...a[i] (выделена курсивом) является упорядоченной. Таким образом, на (n-1)-м шаге вся последовательность, кроме a[n] оказывается отсортированной, а a[n] стоит на последнем месте по праву: все меньшие элементы уже ушли влево. Алгоритм сортировки выбором представлен ниже:

i-цикл от 0 до size с шагом 1

k = i

x = a[i]

j-цикл от i + 1 до size с шагом 1

если a[j] < x, то

k = j

x = a[j]

все если

все j-цикл

a[k] = a[i]

a[i] = x

все i-цикл

Для нахождения наименьшего элемента из n+1 рассматриваемых алгоритм совершает n сравнений. С учетом того, что количество рассматриваемых на очередном шаге элементов уменьшается на единицу, общее количество операций:

n + (n-1) + (n-2) + (n-3) +... + 1 = 1/2 * (n²+n) = O(n²)

Таким образом, так как число обменов всегда будет меньше числа сравнений, время сортировки растет квадратично относительно количества элементов.

Алгоритм не использует дополнительной памяти: все операции происходят "на месте".

Не нашли, что искали? Воспользуйтесь поиском: