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

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

HotLog


 

Сортировка - преобразование последовательности элементов в неубывающую (или невозрастающую) последовательность. Последовательность элементов {Ai} называют неубывающей, если для любых i и j, таких что i < j выполняется неравенство Ai <= Aj. Для строго возрастающей последовательности неравенство принимает вид Ai < Aj. Аналогичным образом определяется невозрастающая и убывающая последовательности.

Сортировка массива

При решении олимпиадных задач часто необходима сортировка данных. Обычно данные представлены в виде массива из N элементов, где элементы - это чаще всего числа или строки. Для этого существует множество алгоритмов, которые с помощью замены значений элементов исходного массива приводят его к отсортированному виду.

Для лучшего понимания того, в каких случаях нужно применить тот или иной алгоритм необходимо знать, что понимают под показателем сложности алгоритма. Речь идет о том, как зависит число операций, которые нужно произвести согласно алгоритму от объема данных, в нашем случае от количества элеменов массива N. Сложность задачи может быть логарифмической, линейной, квадратичной, экспонициальной и т.д., где для решения задачи необходимо выполнение O(ln(N)), O(N), O(N2) и O(eN) операций соответственно. Например, квадратичный порядок сложности O(N2) означает, что задача может использовать N2 операций, а может и 100*N2, здесь коэффициент перед N2 не имеет значения: важен порядок, важно знать во сколько раз программа будет работать дольше, если число N увеличится вдвое, втрое или в 10 раз. В нашем случае независимо от этого коэффициента получим, что программа будет выполняться соответственно в 4, 9 и 100 раз дольше.

Наилучшие универсальные алгоритмы сортировки имеют порядок сложности O(n*ln(n)), что позволяет в олимпиадных задачах сортировать массивы для N = 300 000 (приблизительно). В качестве примера подобных алгоритмов можно привести следующие сортировки: быстрая, пирамидальная, слиянием, бинарным деревом.

Простейшие алгоритмы сортировки имеют порядок O(N2), что позволяет решать задачу с сортировкой только для N <= 5000 (так же примерно). Несмотря на то, что квадратичные алгоритмы дают меньший эффект, их разумно использовать, когда скоростью сортировки данных можно принебречь, повысив скорость реализации программы. Примеры подобных сортировок: выбором, пузырьком, вставками.

В частных случаях отсортировать данные возможно с линейным порядком сложности, когда есть некоторые ограничения на данные (например, массив уже частично отсортирован или диапазон элементов массива ограничен). С таким порядком сложности возможна сортировка массива, состоящего из 107 элементов! Например, следующие алгоритмы дают такой результат: цифровая и пораздрядная сортировки.

Многие считают, что достаточно знания двух сотрировок (например, "пузырьком" и "быстрой"), чтобы решать любые олимпиадные задачи. Но на самом деле это далеко не так. Далее, рассмотрим алгоритмы сортировки, наиболее часто используемые программистами. Во всех примерах будем сортировать по неубыванию полагая, что a[i] - целочисленный массив, состоящий из n элементов, с индексами от 1 до n.

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

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

for i=1..n-1{
  for j=i+1..n{
    if(a[i] > a[j]) a[i] <---> a[j];
  }
}

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

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

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

for i=1..n-1{
  for j=n-1..i{
    if(a[j] > a[j+1]) a[j] <---> a[j+1];
  }
}

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

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

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

sub QuickSort(l,r){
  x=a[(l+r) div 2];
  i=l; j=r;
  while(i <= j){
    while(a[i] < x) i=i+1;
    while(a[j] > x) j=j-1;
    if (i <= j) {
      a[i] <---> a[j];
      i=i+1; j=j-1;
    }
  }
  if(j > l) QuickSort(l, j);
  if(r > i) QuickSort(i, r);
}

Для сортировки массива достаточно вызвать процедуру QuickSort(1,n). Подробнее о быстрой сортировке Вы можете прочитать здесь.

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

Красноярский краевой Дворец пионеров, (c)2006 - 2017, ICQ: 151483