Олимпиады по информатике (ХМАО - Югра)

   
 
Югорский НИИ ИТ, Югорский ФМЛ
Логин:   Пароль:    
 
   
 
Новости
О проекте
Регистрация
Гостевая книга
Форум
Архив задач
Состояние системы
Олимпиады
Работа в системе
Рейтинг
Новичкам
Методическое пособие
Дистанционное обучение
Дистрибутивы
Ссылки

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). Подробнее о быстрой сортировке Вы можете прочитать здесь.

Список задач

Задача 1: Сортировка времени
Задача 2: Свадьба
Задача 3: Сортировка подсчетом
Задача 4: Выборы
Задача 5: Арифметическая прогрессия - 2
Задача 6: Преобразование последовательности
Задача 7: Ближайшие точки
Задача 8: Сортировка масс
Задача 9: Годовой баланс

Вернуться

 
     
Югорский НИИ ИТ, Югорский ФМЛ


Антиплагиат БМИТ посмотреть.   подключение электричества раменское