Одномерные массивы: задачи сортировок элементов массива

Цель лекции: изучить понятия и классификацию алгоритмов сортировок массивов, реализацию алгоритмов простых сортировок и научиться решать задачи на сортировку одномерных массивов с помощью алгоритмов простых сортировок в языке C++.

Задача сортировки является такой же базовой, как задача поиска. В практических условиях эти задачи взаимосвязаны. Решению проблем, связанных с сортировкой, посвящено множество фундаментальных научных исследований, разработано множество алгоритмов.

В общем случае сортировку следует понимать как процесс перегруппировки заданного множества объектов в определенном порядке. Часто при сортировке больших объемов данных нецелесообразно переставлять сами элементы, поэтому для решения задачи выполняется упорядочивание элементов по индексам. То есть индексы элементов выстраивают в такой последовательности, что соответствующие им значения элементов оказываются отсортированными по условию задачи.

Сортировка применяется для облегчения поиска элементов в упорядоченном множестве. Задача сортировки одна из фундаментных в программировании.

Сортировка – это упорядочивание набора однотипных данных по возрастанию или убыванию.

Чаще всего при сортировке данных лишь часть их используется в качестве ключа сортировки. Ключ сортировки – это часть данных, определяющая порядок элементов. Таким образом, ключ участвует в сравнениях, но при обмене элементов происходит перемещение всей структуры данных. Например, в списке почтовой рассылки в качестве ключа может использоваться почтовый индекс, но сортируется весь адрес. При решении задач сортировок массивов ключ и данные совпадают.

Для того, чтобы отсортировать данные, можно вызывать стандартную функцию qsort(), входящую в библиотеку С++. Однако различные подходы к сортировке обладают разными характеристиками. Несмотря на то, что некоторые способы сортировки могут быть в среднем лучше, чем другие, ни один алгоритм не является идеальным для всех случаев.

Использование функции qsort() не является универсальным решением для всех задач сортировки. Во-первых, функцию общего назначения, такую как qsort(), невозможно применить во всех ситуациях. Например, данная функция сортирует только массивы в памяти и не может сортировать данные, хранящиеся в связанных списках. Во-вторых, qsort() – параметризованная функция, благодаря чему она может обрабатывать широкий набор типов данных, но вследствие этого она работает медленнее, чем эквивалентная функция, рассчитанная на какой-то один тип данных. В-третьих, алгоритм быстрой сортировки, примененный в функции qsort(), может оказаться не самым эффективным алгоритмом в некоторых конкретных ситуациях.

Оценка алгоритмов сортировки

Существует множество различных алгоритмов сортировки. Все они имеют свои положительные и отрицательные стороны. Перечислим общие критерии оценки алгоритмов сортировки.

Различные сортировки массивов отличаются по быстродействию. Существуют простые методы сортировок, которые требуют порядка n*n сравнений, где n – количество элементов массива и быстрые сортировки, которые требуют порядка n*ln(n) сравнений. Простые методы удобны для объяснения принципов сортировок, т.к. имеют простые и короткие алгоритмы. Усложненные методы требуют меньшего числа операций, но сами операции более сложные, поэтому для небольших массивов простые методы более эффективны.

Простые методы сортировки можно разделить на три основные категории:

Сортировка методом "пузырька" (простого обмена)

Самый известный алгоритм – пузырьковая сортировка (bubble sort, сортировка методом пузырька или просто сортировка пузырьком). Его популярность объясняется интересным названием и простотой самого алгоритма.

Алгоритм попарного сравнения элементов массива в литературе часто называют "методом пузырька", проводя аналогию с пузырьком, поднимающимся со дна бокала с газированной водой. По мере всплывания пузырек сталкивается с другими пузырьками и, сливаясь с ними, увеличивается в объеме. Чтобы аналогия стала очевидной, нужно считать, что элементы массива расположены вертикально друг над другом, и их нужно так упорядочить, чтобы они увеличивались сверху вниз.

Алгоритм состоит в повторяющихся проходах по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает – массив отсортирован. При проходе алгоритма элемент, стоящий не на своём месте, "всплывает" до нужной позиции (рис 12.1).

//Описание функции сортировки методом "пузырька"
void BubbleSort (int k,int x[max]) {
  int i,j,buf;
  for (i=k-1;i>0;i--)
    for (j=0;j<i;j++)
    if (x[j]>x[j+1]) {
      buf=x[j];
      x[j]=x[j+1];
      x[j+1]=buf;
     }    
}

В пузырьковой сортировке количество сравнений всегда одно и то же, поскольку два цикла for повторяются указанное количество раз независимо от того, был список изначально упорядочен или нет. Это значит, что алгоритм пузырьковой сортировки всегда выполняет$$\frac{(n^2-n)}{2}$$ сравнений, где n – количество сортируемых элементов. Данная формула выведена на том основании, что внешний цикл выполняется n-1 раз, а внутренний выполняется в среднем n/2 раз.

Пузырьковая сортировка имеет такую особенность: неупорядоченные элементы на "большом" конце массива занимают правильные положения за один проход, но неупорядоченные элементы в начале массива поднимаются на свои места очень медленно. Поэтому, вместо того чтобы постоянно просматривать массив в одном направлении, в последовательных проходах можно чередовать направления. Таким образом, элементы, сильно удаленные от своих положений, быстро станут на свои места. Данная версия пузырьковой сортировки носит название шейкер-сортировки (shaker sort сортировка перемешиванием, сортировка взбалтыванием, сортировка встряхиванием), поскольку действия, производимые ею с массивом, напоминают взбалтывание или встряхивание. Ниже показана реализация шейкер-сортировки.

//Описание функции шейкер-сортировки
void Shaker(int k,int x[max]){
  int i,t;
  bool exchange;
  do {
    exchange = false;
    for(i=k-1; i > 0; --i) {
      if(x[i-1] > x[i]) {
        t = x[i-1];
        x[i-1] = x[i];
        x[i] = t;
        exchange = true;
      }
    }
    for(i=1; i < k; ++i) {
      if(x[i-1] > x[i]) {
        t = x[i-1];
        x[i-1] = x[i];
        x[i] = t;
        exchange = true;
      }
    }
  } while(exchange); 
    //сортировать до тех пор, пока не будет обменов
}

Хотя шейкер-сортировка и является улучшенным вариантом по сравнению с пузырьковой сортировкой, она по-прежнему имеет время выполнения порядка N2. Это объясняется тем, что количество сравнений не изменилось, а количество обменов уменьшилось лишь на относительно небольшую величину.

Сортировка методом простого выбора (простой перебор)

Это наиболее естественный алгоритм упорядочивания. При данной сортировке из массива выбирается элемент с наименьшим значением и обменивается с первым элементом. Затем из оставшихся )

Шаги алгоритма:

//Описание функции сортировки методом простого выбора
void SelectionSort (int k,int x[max]) {
  int i,j,min,temp;
  for (i=0;i<k-1;i++) {
  //устанавливаем начальное значение минимального индекса
    min=i; 
    //находим минимальный индекс элемента
    for (j=i+1;j<k;j++){
      if (x[j]<x[min])
        min=j;
      //меняем значения местами 
      }
      temp=x[i];
      x[i]=x[min];
      x[min]=temp;
  }
}

Как и в пузырьковой сортировке, внешний цикл выполняется n-1 раз, а внутренний – в среднем n/2 раз. Следовательно, сортировка методом простого выбора требует$$\frac{(n^2-n)}{2}$$ сравнений. Таким образом, это алгоритм порядка n2, из-за чего он считается слишком медленным для сортировки большого количества элементов. Несмотря на то, что количество сравнений в пузырьковой сортировке и сортировке простым выбором одинаковое, в последней количество обменов в среднем случае намного меньше, чем в пузырьковой сортировке.

Сортировка методом простого включения (сдвиг-вставка, вставками, вставка и сдвиг)

Хотя этот метод сортировки намного менее эффективен, чем сложные алгоритмы (такие как быстрая сортировка), у него есть ряд преимуществ:

На каждом шаге алгоритма выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированной последовательности до тех пор, пока набор входных данных не будет исчерпан. Метод выбора очередного элемента из исходного массива произволен; может использоваться практически любой алгоритм выбора (рис 12.3).

//Описание функции сортировки методом простого включения
void InsertSort (int k,int x[max]) {
  int i,j, temp;
  for (i=0;i<k;i++) {
  //цикл проходов, i - номер прохода
    temp=x[i]; 
    //поиск места элемента
    for (j=i-1; j>=0  x[j]>temp; j--)
      x[j+1]=x[j];//сдвигаем элемент вправо, пока не дошли
      //место найдено, вставить элемент 
      x[j+1]=temp;  
  }
}

В отличие от пузырьковой сортировки и сортировки простого выбора, количество сравнений в сортировке вставками зависит от изначальной упорядоченности списка. Если список уже отсортирован, количество сравнений равно n-1 ; в противном случае его производительность является величиной порядка n2.

Ключевые термины

Ключ сортировки – это часть данных, определяющая порядок элементов.

Сортировка – это упорядочивание набора однотипных данных по возрастанию или убыванию.

Сортировка методом "пузырька" – это алгоритм попарного сравнения элементов одномерного массива.

Сортировка методом простого включения – это алгоритм последовательного помещения элемента массива в отсортированную часть в соответствии с ключом сортировки.

Сортировка методом простого выбора – это алгоритм последовательного обмена минимального и первого элементов неотсортированной части массива.

Краткие итоги

Лабораторная работа 12. Одномерные массивы: задачи сортировок элементов массива

Цель работы: изучить понятия и классификацию алгоритмов сортировок массивов, реализацию алгоритмов простых сортировок и научиться решать задачи на сортировку одномерных массивов с помощью алгоритмов простых сортировок в языке C++.

При выполнении лабораторной работы для каждого задания требуется написать программу на языке С++, которая получает на входе числовые данные (в зависимости от постановки задачи), выполняет генерацию и вывод одномерного массива указанного типа. В задачах необходимо выполнить сортировку данных массива простыми методами и реализовать алгоритмы сортировок в виде отдельных функций. Ввод данных осуществляется с клавиатуры с учетом требований к входным данным, содержащихся в постановке задачи. Ограничениями на входные данные является диапазон используемого числового типа данных в языке С++ и максимально допустимый размер объявляемого одномерного массива.

Теоретические сведения.

Ознакомьтесь с материалом лекции 12.

Задания к лабораторной работе.

Выполните приведенные ниже задания.

Указания к выполнению работы.

Каждое задание необходимо решить в соответствии с изученными методами объявления, генерации и вывода одномерных массивов в языке С++. Обработку данных необходимо выполнить, используя алгоритмы простых сортировок данных в одномерных массивах. При разработке программного кода требуется использовать метод процедурной абстракции и комментировать фрагменты кода.

Следует реализовать каждое задание в соответствии с приведенными этапами:

Требования к отчету.

Отчет по лабораторной работе должен соответствовать следующей структуре.

Контрольные вопросы