Сортировка выбором - EcsFlash/DataTypes GitHub Wiki

Как работает:

Берем первый элемент списка, идем дальше по списку, если встречаем элемент больше выбранного, берем тот, который больше. Как только дошли до конца - остановились, сдвинули правую границу на 1 элемент влево. Опять берем первый элемент и всё по новой. Можно сделать и так, что искать будем наименьший элемент, а двигать левую границу на 1 элемент вправо.

Если проще - на каждом проходе выбираем максимальный/минимальный элемент и меняем его местами с крайним правым/левым.

gif

Статистика:

┌────────────┬───────────────┬────────────────┬──────────────┐
│ Сложность  │ Лучший случай │ Средний случай │ Худший случай│
├────────────┼───────────────┼────────────────┼──────────────┤
│   Время    │     O(n²)     │      O(n²)     │     O(n²)    │
├────────────┼───────────────┼────────────────┼──────────────┤
│   Память   │     O(1)      │      O(1)      │     O(1)     │
└────────────┴───────────────┴────────────────┴──────────────┘

На плюсиках(вариант с выбором наименьшего):

void selectionSort(vector<int> &arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; ++i) {
        int min_idx = i;
        for (int j = i + 1; j < n; ++j) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j; 
            }
        }
        swap(arr[i], arr[min_idx]);
    }
}

Псевдокод(вариант с выбором наибольшего):

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

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

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

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

image

Это приводит к временной сложности ( O(n^2) ) в худшем, среднем и лучшем случаях, так как независимо от начальной упорядоченности массива, оба цикла будут выполняться указанное количество раз.

⚠️ **GitHub.com Fallback** ⚠️