Сортировка сравнением. Понятие инверсии. Сортировка пузырьком.

Определения

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

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

Понятие инверсии в сортировке означает пару элементов массива, которые находятся в неправильном порядке. Например, в массиве [3, 1, 2] имеется две инверсии: (3, 2) и (3, 1). Чем меньше инверсий в массиве, тем ближе он к отсортированному состоянию.

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

Идея - пока соседние элементы не в порядке, меняем их местами.

Работает путем последовательного сравнения соседних элементов массива и их перестановки, если они находятся в неправильном порядке. Алгоритм повторяет этот процесс несколько раз, пока массив не будет отсортирован. Сложность O(n^2)

def bubbleSort(arr):
	n = len(arr)
	for i in range(n - 1):
		for j in range(n - i - 1):
			if arr[j] > arr[j + 1]:
				arr[j], arr[j + 1] = arr[j + 1], arr[j]