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

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

HotLog


 

В этом разделе рассмотрим алгоритмы быстрой сортировки и сортировки слиянием, имеющих асимптотику O(n×ln(n)). Также обратим внимание на возможность использования стандартных функций языка C++, которые можно использовать для сортировки массивов.

Быстрая сортировка

Этот алгоритм является одним из самых популярных и наиболее часто используемым среди алгоритмов, имеющих порядок сложности O(n×ln(n)). Сам алгоритм является рекурсивным и его идея заключается в следующем: для сортировки массива достаточно разбить его на две части так, чтобы все элементы левой части были меньше либо равны всех элементов правой части, далее следует выполнить подобную операцию с левой и правой частью, рассматривая их как отдельные массивы. Алгоритмическое представление функции, которая сортирует подмассив с l-го по r-й элемент можно представить следующим образом:

Быстрая сортировка

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

Сортировка слиянием

Данный алгоритм имеет рекурсивную основу и работает по принципу «разделяй и властвуй» c асимптотикой O(n×ln(n)). Основные его моменты можно описать следующими концепциями:

  1. Сортируемый массив разбивается на две части примерно одинакового размера.
  2. Каждая из получившихся частей сортируется отдельно, используя тот же алгоритм.
  3. Два упорядоченных массива половинного размера соединяются в один.

Следует отметить, что данный алгоритм является устойчивым, т.е. в результате сортировки равные элементы (по критерию сравнения) не меняют своего положения относительно друг друга. Алгоритмическое представление функции, которая сортирует подмассив с l-го по r-й элемент можно представить следующим образом:

Сортировка слиянием

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

Сортировка в C++

Для сортировки массива в большинстве случаев вовсе необязательно самостоятельно реализовывать алгоритмы сортировки. Дело в том, что многие языки программирования содержат встроенные средства сортировки данных. И язык C++ не является исключением. В библиотеке algorithm содержатся функции сортировки, которые вы можете использовать в своих программах. Так, приведем пример кода сортировки массива a[0..n-1], состоящего из n элементов на языке C++:

Следующий пример представляет собой целостный код программы на языке C++, реализующей чтение, сортировку и вывод элементов целочисленного массива:


Сортировка слиянием
 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Введение
 Условный оператор
 Операторы цикла
 Строковые типы данных
 Массивы
 Функции
 Сортировка
 Двумерные массивы
 Рекурсия
 Квадратичная сортировка
 Быстрая сортировка
 Сортировка структур
 A. Сортировка подсчетом
 B. Арифметическая прогрессия - 2
 C. Ближайшие точки
 D. Преобразование последовательности

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