Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Рассмотрим самые простые алгоритмы сортировки, используемые в обучении и тех случаях, когда асимптотикой при решении задачи можно пренебречь. Речь идет об алгоритмах сортировки "пузырьком" и "выбором". Далее, будем работать с некоторым массивом a[0..n-1], состоящим из n элементов сравнимого типа.

Сортировка выбором

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

Подробнее о сортировке выбором можно прочитать здесь.

Сортировка пузырьком

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

Подробнее о сортировке пузырьком можно прочитать здесь.

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Введение
 Условный оператор
 Операторы цикла
 Строковые типы данных
 Массивы
 Функции
 Сортировка
 Двумерные массивы
 Рекурсия
 Квадратичная сортировка
 Быстрая сортировка
 Сортировка структур
 A. Сортировка пузырьком
 B. Сортировка выбором
 C. Азартный Шрэк
 D. Сортировка времени
 E. Выборы
 F. Свадьба
 G. Годовой баланс
 H. Сортировка масс
 I. Рабочее время

Красноярский краевой Дворец пионеров, (c)2006 - 2020, E-mail: admin@acmp.ru