Простые методы сортировки (метод пузырька, метод выбора, сортировка вставками)

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

Метод пузырька последовательно сравнивает пары соседних элементов и меняет их местами, если они расположены не в том порядке. За несколько проходов по списку самые большие элементы «всплывают» в конец массива, напоминают движение пузырьков в воде.

Алгоритм:

1. Для каждого элемента списка:

  a. Сравнить текущий элемент со следующим.
  b. Если порядок неправильный, поменять их местами.

2. Повторять шаг 1, пока список не будет отсортирован.

Псевдокод:

for i from 1 to n-1:
    for j from 1 to n-i:
        if A[j] > A[j+1]:
            swap A[j] and A[j+1]

Сложность:

• в худшем и среднем случаях: ${\displaystyle O(n^{2})}$;
• в лучшем случае (уже отсортированный список): ${\displaystyle O(n)}$.

Метод выбора заключается в поиске на каждом шаге минимального элемента в неотсортированной части списка и перемещении его в начало.

Алгоритм:

1. Для каждого индекса i от 1 до n-1:

  a. Найти минимальный элемент в подсписке от i до n.
  b. Поменять местами A[i] и найденный минимальный элемент.

2. Повторять, пока весь список не будет отсортирован.

Псевдокод:

for i from 1 to n-1:
    min_index = i
    for j from i+1 to n:
        if A[j] < A[min_index]:
            min_index = j
    if min_index != i:
        swap A[i] and A[min_index]

Сложность:

• в худшем, лучшем и среднем случаях: ${\displaystyle O(n^{2})}$.

Сортировка вставками формирует отсортированный список, вставляя каждый новый элемент в подходящее место.

Алгоритм:

1. Считать первый элемент отсортированным.

2. Для каждого следующего элемента:

  a. Сравнивать его с предыдущими элементами в отсортированной части.
  b. Вставлять элемент на нужную позицию, сдвигая большие элементы вправо.

Псевдокод:

for i from 2 to n:
    key = A[i]
    j = i - 1
    while j > 0 and A[j] > key:
        A[j+1] = A[j]
        j = j - 1
    A[j+1] = key

Сложность:

• в худшем и среднем случаях: ${\displaystyle O(n^{2})}$;
• в лучшем случае (почти отсортированный список): ${\displaystyle O(n)}$.

Простые методы сортировки, такие как метод пузырька, метод выбора и сортировка вставками, являются базовыми алгоритмами для упорядочивания данных. Они легко понимаются и реализуются, что делает их полезными для обучения основам алгоритмов. Однако из-за квадратичной сложности ${\displaystyle O(n^{2})}$ они неэффективны для больших наборов данных, и в таких случаях предпочтительно использовать другие алгоритмы сортировки.