Алгоритм сортировки 01

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

  • Разделите массив на два подмассива: отсортированный и несортированный подмассивы.
  • На каждой итерации найдите максимальный / минимальный элемент в несортированном подмассиве и замените его первым элементом несортированного подмассива. После замены первый элемент несортированного подмассива будет добавлен к отсортированному подмассиву. При замене минимального значения элементы будут отсортированы в порядке возрастания, а при замене максимального значения элементы будут отсортированы в порядке убывания.
  • Продолжайте итерацию до последнего элемента

Давайте посмотрим на пример для лучшего понимания.

Предположим, что массив чисел, который нужно отсортировать в порядке возрастания, равен (8,4,6,3,1,9,5)

Первоначально весь массив будет несортированным подмассивом, как показано на рисунке выше. Мы находим минимальное значение 1 и меняем его местами на 8, что является первым элементом несортированного подмассива. Сортированный подмассив выделяется желтым цветом. Следующее минимальное значение в несортированном подмассиве - 3. Мы меняем его местами на 4, что является первым элементом несортированного подмассива. Таким образом, на итерации i ᵗʰ мы меняем местами минимальное значение с элементом i ᵗʰ массива. После m количества итераций первые m элементов массива будут отсортированы.

Реализация на C

Анализ выборочной сортировки

  1. Сортировка по выбору - это алгоритм на месте, что означает, что ему не требуется дополнительное пространство памяти для выполнения сортировки.
  2. Временная сложность O (n²). Предположим, что количество сортируемых элементов равно n, изначально минимальное значение должно быть найдено среди n элементов, что требует (n-1) сравнений. На следующей итерации требуется (n-2) сравнений. На следующем рисунке показано количество сравнений, необходимых для каждой итерации.

Следовательно, общее количество требуемых сравнений будет (n-1) + (n-2) +… .. + 2 + 1, что может быть упрощено как n (n-1) / 2 → O (n²)

Поскольку его временная сложность квадратична, сортировка выбора была бы очень неэффективной, когда нужно отсортировать большое количество элементов. Однако, поскольку его пространственная сложность равна O (1), сортировка по выбору может быть полезна, когда объем доступной памяти очень ограничен.

Надеюсь, вам понравилась статья!