Сортировка пузырьком, серьезно? - EcsFlash/DataTypes GitHub Wiki

Самая базовая сортировка, которую может написать даже слепая собака-поводырь.

image

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

func bubbleSort(items []int) []int {
	for i := 0; i < len(items)-1; i++ {
		for j := 0; j < len(items)-1-i; j++ {
			if items[j] > items[j+1] {
				swap(&items[j], &items[j+1])
			}
		}
	}
	return items
}

Ну и немного статистики:

┌────────────┬───────────────┬────────────────┬──────────────┐
│ Сложность  │ Лучший случай │ Средний случай │ Худший случай│
├────────────┼───────────────┼────────────────┼──────────────┤
│   Время    │     O(n)***   │      O(n²)     │     O(n²)    │
├────────────┼───────────────┼────────────────┼──────────────┤
│   Память   │     O(1)      │      O(1)      │     O(1)     │
└────────────┴───────────────┴────────────────┴──────────────┘
*** ВАЖНООО: O(n) - для оптимизированного алгоритма и в случае уже отсортированного массива, а в нашем случае O(n^2)

Анализ сложности

Временная сложность

  • Внешний цикл: выполняется ( n-1 ) раз, где ( n ) — количество элементов в массиве.
  • Внутренний цикл: для каждого шага внешнего цикла, внутренний цикл выполняется ( n-i-1 ) раз.
  • Основная операция: сравнение

image