Модернизация сортировки методом пузырька

Приведем пару соображений по оптимизации написанного кода. Представим себе, что у нас есть массив на два миллиона чисел, и мы уже сделали миллион проходов. Это значит, что как минимум миллион чисел в массиве уже стоят на своих законных местах в конце массива. Следовательно, нет никакого смысла проходить правую половину массива, потому что там никаких изменений точно уже не будет. Итак, если на первом проходе мы делаем N−1 сравнение, то на втором достаточно N−2, на третьем достаточно N−3 и так далее по мере увеличения количества чисел, которые стоят на своих местах. Таким образом кусочек программы, отвечающий за сортировку можно переписать так:

PYTHON:

def BubbleSort(A):
for j in range(len(A)-1):
for i in range(len(A)-1):
if A[i] > A[i + 1]:
A[i], A[i + 1] = A[i + 1], A[i]

 

PASCAL:

procedure bubbleSort(var a: massiv);

var

i, j: longint;

begin

for j:= 1 to n - 1 do

for i:= 1 to n - j do

if a[i] > a[i + 1] then

swap(a[i], a[i + 1]);

end;

 

Количество операций (а вместе с ним и время работы) нам удалось сократить вдвое. Хотя, следует признать, что оценка времени работы алгоритма все еще составляет O(N2).

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

Например, в массиве 8, 1, 2, 3, 4, 5, 6 будет вообще достаточно одного прохода, чтобы вытолкнуть восьмерку на последнее место.

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

PYTHON:

def BubbleSort(A):
j = len(A) - 1
IsNotOrdered = True
while IsNotOrdered:
IsNotOrdered = False
for i in range(0, j):
if A[i] > A[i + 1]:
A[i], A[i + 1] = A[i + 1], A[i]
IsNotOrdered = True
j -= 1

 

PASCAL:

procedure bubbleSort(var a: massiv);

var

i, j: longint;

isNotOrdered: boolean;

begin

isNotOrdered:= true;

j:= n - 1;

while isNotOrdered do

begin

isNotOrdered:= false;

for i:= 1 to j do

if a[i] > a[i + 1] then begin

swap(a[i], a[i + 1]);

isNotOrdered:= true;

end;

dec(j);

end;

end;

 

Стоит заметить, что в худшем случае (а именно, если на входе дан массив, упорядоченный в другую сторону) время работы все равно будет составлять O(N2) и по количеству операций сравнения программа не будет отличаться от предыдущего примера.

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

Синхронная сортировка массивов

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

def BubbleSort(A, B):
for j in range(len(A) - 1, 0, -1):
for i in range(0, j):
if A[i] > A[i + 1]:
A[i], A[i + 1] = A[i + 1], A[i]
B[i], B[i + 1] = B[i + 1], B[i]
A = [4, 2, 5, 1]
B = ['Liza', 'Ivan', 'Andrey','Kolya']
BubbleSort(A, B)

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

Кортеж — это неизменяемый список. Кортеж не может быть изменён никаким способом после его создания, т. е. Вы не можете добавить элементы к кортежу, нет методов append() или extend(), нельзя удалять элементы из кортежа. Кортежи не имеют методов remove() или pop(). Вы можете искать элементы в кортежи, поскольку это не изменяет кортеж. Вы также можете использовать оператор in, чтобы проверить существует ли элемент в кортеже.

Сортировка пузырьком по значению первого элемента в кортеже:

def BubbleSort(A):
for j in range(len(A) - 1, 0, -1):
for i in range(0, j):
if A[i][0] > A[i + 1][0]: #сравниваем не кортежи целиком, а только ключи
A[i], A[i + 1] = A[i + 1], A[i]
A = [(4,'Liza'), (2,'Ivan'), (5,'Andrey'), (1,'Kolya')]
BubbleSort(A)

Сортировка по двум параметрам с использованием сложного условия:

N = int(input())
A = []
for k in range(N):
name, phone = input().split()
A.append((name, int(phone)))
for j in range(len(A)-1, 0, -1):
for i in range(j):
if A[i][0] > A[i+1][0] \
or A[i][0] == A[i+1][0] and A[i][1] > A[i+1][1]:
A[i], A[i+1] = A[i+1], A[i]
for k in range(N):
name, phone = A[k]
print(name, phone)

Устойчивость сортировок

Устойчивая сортировка не меняет взаимного расположения равных элементов.

Если элемент состоит только из одного ключа (т. е. значения, по которому и производится сортировка) то устойчивость сортировки не важна, но при сортировке списка, состоящего из кортежей (например, возраст и фамилия) в поддержании исходного порядка может быть смысл, так как равные по ключу элементы различны.

Устойчивые алгоритмы сортировки:

1. пузырьковая

2. вставкой

3. выбором

4. поразрядная

5. слиянием

6. Timsort

Неустойчивые алгоритмы сортировки:

1. быстрая сортировка Хоара

2. пирамидальная

3. Шелла

4. интроспективная

5. терпеливая

6. плавная

Сортировка выбором имеет как устойчивые, так и неустойчивые реализации.

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