В чем суть сортировки пузырьком? Какова ее сложность?

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

Название связано с аналогией: большие элементы постепенно всплывают к концу массива, как пузырьки.

Идея алгоритма

Пусть нужно отсортировать массив по возрастанию.

На каждом проходе сравниваются пары соседних элементов:

• если левый элемент больше правого, они меняются местами;
• если порядок правильный, пара остается как есть.

После первого полного прохода самый большой элемент окажется в конце массива.

После второго прохода второй по величине элемент окажется перед ним, и так далее.

Пример

Исходный массив:

[5, 2, 4, 1]

Первый проход:

5 и 2 меняем: [2, 5, 4, 1]
5 и 4 меняем: [2, 4, 5, 1]
5 и 1 меняем: [2, 4, 1, 5]

Число 5 оказалось в конце.

Код

function bubbleSort(values) {
  const result = [...values];

  for (let i = 0; i < result.length - 1; i++) {
    for (let j = 0; j < result.length - 1 - i; j++) {
      if (result[j] > result[j + 1]) {
        const temp = result[j];
        result[j] = result[j + 1];
        result[j + 1] = temp;
      }
    }
  }

  return result;
}

function bubbleSort(values: number[]): number[] {
  const result = [...values];

  for (let i = 0; i < result.length - 1; i++) {
    for (let j = 0; j < result.length - 1 - i; j++) {
      if (result[j] > result[j + 1]) {
        const temp = result[j];
        result[j] = result[j + 1];
        result[j + 1] = temp;
      }
    }
  }

  return result;
}

func bubbleSort(values []int) []int {
  result := append([]int(nil), values...)

  for i := 0; i < len(result)-1; i++ {
    for j := 0; j < len(result)-1-i; j++ {
      if result[j] > result[j+1] {
        result[j], result[j+1] = result[j+1], result[j]
      }
    }
  }

  return result
}

public class Example {
  static int[] bubbleSort(int[] values) {
    int[] result = java.util.Arrays.copyOf(values, values.length);

    for (int i = 0; i < result.length - 1; i++) {
      for (int j = 0; j < result.length - 1 - i; j++) {
        if (result[j] > result[j + 1]) {
          int temp = result[j];
          result[j] = result[j + 1];
          result[j + 1] = temp;
        }
      }
    }

    return result;
  }
}

def bubble_sort(values):
  result = values.copy()

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

  return result

Оптимизация

Если за проход не было ни одной перестановки, массив уже отсортирован. Тогда алгоритм можно завершить раньше.

function bubbleSortOptimized(values) {
  const result = [...values];

  for (let i = 0; i < result.length - 1; i++) {
    let swapped = false;

    for (let j = 0; j < result.length - 1 - i; j++) {
      if (result[j] > result[j + 1]) {
        const temp = result[j];
        result[j] = result[j + 1];
        result[j + 1] = temp;
        swapped = true;
      }
    }

    if (!swapped) {
      break;
    }
  }

  return result;
}

function bubbleSortOptimized(values: number[]): number[] {
  const result = [...values];

  for (let i = 0; i < result.length - 1; i++) {
    let swapped = false;

    for (let j = 0; j < result.length - 1 - i; j++) {
      if (result[j] > result[j + 1]) {
        const temp = result[j];
        result[j] = result[j + 1];
        result[j + 1] = temp;
        swapped = true;
      }
    }

    if (!swapped) {
      break;
    }
  }

  return result;
}

func bubbleSortOptimized(values []int) []int {
  result := append([]int(nil), values...)

  for i := 0; i < len(result)-1; i++ {
    swapped := false

    for j := 0; j < len(result)-1-i; j++ {
      if result[j] > result[j+1] {
        result[j], result[j+1] = result[j+1], result[j]
        swapped = true
      }
    }

    if !swapped {
      break
    }
  }

  return result
}

public class Example {
  static int[] bubbleSortOptimized(int[] values) {
    int[] result = java.util.Arrays.copyOf(values, values.length);

    for (int i = 0; i < result.length - 1; i++) {
      boolean swapped = false;

      for (int j = 0; j < result.length - 1 - i; j++) {
        if (result[j] > result[j + 1]) {
          int temp = result[j];
          result[j] = result[j + 1];
          result[j + 1] = temp;
          swapped = true;
        }
      }

      if (!swapped) {
        break;
      }
    }

    return result;
  }
}

def bubble_sort_optimized(values):
  result = values.copy()

  for i in range(len(result) - 1):
    swapped = False

    for j in range(len(result) - 1 - i):
      if result[j] > result[j + 1]:
        result[j], result[j + 1] = result[j + 1], result[j]
        swapped = True

    if not swapped:
      break

  return result

Сложность

В худшем и среднем случае сортировка пузырьком выполняет порядка n² сравнений.

Сложность:

• худший случай: O(n²);
• средний случай: O(n²);
• лучший случай с оптимизацией: O(n);
• дополнительная память: O(1), если сортировать на месте.

Особенности

Преимущества:

• очень простая идея;
• легко реализовать;
• подходит для обучения.

Недостатки:

• медленная на больших массивах;
• выполняет много лишних сравнений и обменов;
• редко используется в реальных производительных системах.

Вывод

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