ЛАБОРАТОРНАЯ РАБОТА №-

по дисциплине:

Структуры данных и алгоритмы 

Методы  сортировки данных

 
 
 
 
 
 
 
 

Выполнил:  

Проверил:  
 
 
 
 
 
 

Ташкент – 2010

    Введение 

    Задачей сортировки является преобразование исходной последовательности в последовательность, содержащую те же записи, но в порядке возрастания (или убывания) значений ключа. Метод сортировки называется устойчивым, если при его применении не изменяется относительное положение записей с равными значениями ключа.

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

    Естественным условием, предъявляемым к любому методу внутренней сортировки является то, что эти методы не должны требовать дополнительной памяти: все перестановки с целью упорядочения элементов массива должны производиться в пределах того же массива. Мерой эффективности алгоритма внутренней сортировки являются число требуемых сравнений значений ключа (C) и число перестановок элементов (M).

    Поскольку сортировка основана только на значениях ключа и никак не затрагивает оставшиеся поля записей, можно говорить о методе сортировка массивов ключей. 
1. Теоретическая часть 

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

    Идея  метода состоит в том, чтобы создавать  отсортированную последовательность путем присоединения к ней  одного элемента за другим в правильном порядке.

    Будем строить готовую последовательность, начиная с левого конца массива. Алгоритм состоит из n последовательных шагов, начиная от нулевого и заканчивая (n-1)-м.

    На i-м шаге выбираем наименьший из элементов a[i] ... a[n] и меняем его местами с a[i]. Последовательность шагов при n=5 изображена на рисунке ниже.

    

    Вне зависимости от номера текущего шага i, последовательность a[0]...a[i] (выделена курсивом) является упорядоченной. Таким  образом, на (n-1)-м шаге вся последовательность, кроме a[n] оказывается отсортированной, а a[n] стоит на последнем месте по праву: все меньшие элементы уже ушли влево.

    template<class T>

    void selectSort(T a[], long size) {

      long i, j, k;

      T x; 

      for( i=0; i < size; i++) {    // i - номер текущего шага

        k=i; x=a[i]; 

        for( j=i+1; j < size; j++) // цикл выбора наименьшего элемента

          if (  a[j] < x ) {

            k=j; x=a[j];         // k - индекс наименьшего элемента

          } 

        a[k] = a[i]; a[i] = x;    // меняем местами наименьший с a[i]

      }

    }

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

    n + (n-1) + (n-2) + (n-3) + ... + 1 = 1/2 * ( n²+n ) = Theta(n²).

    Таким образом, так как число обменов  всегда будет меньше числа сравнений, время сортировки растет квадратично  относительно количества элементов.

    Алгоритм  не использует дополнительной памяти: все операции происходят "на месте".

    Устойчив  ли этот метод ? Прежде, чем читать далее, попробуйте получить ответ самостоятельно. 
 
Рассмотрим последовательность из трех элементов, каждый из которых имеет два поля, а сортировка идет по первому из них.

    

    Результат ее сортировки можно увидеть уже  после шага 0, так как больше обменов  не будет. Порядок ключей 2a, 2b был  изменен на 2b, 2a, так что метод  неустойчив.

    Если  входная последовательность почти упорядочена, то сравнений будет столько же, значит алгоритм ведет себя неестественно.

Пузырьковая сортировка

    Самый известный (и пользующийся дурной славой) алгоритм — пузырьковая сортировка (bubble sort, сортировка методом пузырька, или просто сортировка пузырьком)^[1]. Его популярность объясняется интересным названием и простотой самого алгоритма. Тем не менее, в общем случае это один из самых худших алгоритмов сортировки.

    Пузырьковая сортировка относится к классу обменных сортировок, т.е. к классу сортировок методом обмена. Ее алгоритм содержит повторяющиеся сравнения (т.е. многократные сравнения одних и тех же элементов) и, при необходимости, обмен соседних элементов. Элементы ведут себя подобно пузырькам воздуха в воде — каждый из них поднимается на свой уровень. Простая форма алгоритма сортировки показана ниже:

/* Пузырьковая  сортировка. */

void bubble(char *items, int count)

{

  register int a, b;

  register char t; 

  for(a=1; a < count; ++a)

    for(b=count-1; b >= a; --b) {

      if(items[b-1] > items[b]) {

        /* exchange elements */

        t = items[b-1];

        items[b-1] = items[b];

        items[b] = t;

      }

    }

}

    Здесь items — указатель на массив символов, подлежащий сортировке, a count — количество элементов в массиве. Работа пузырьковой сортировки выполняется в двух циклах. Если количество элементов массива равно count, внешний цикл приводит к просмотру массива count - 1 раз. Это обеспечивает размещение элементов в правильном порядке к концу выполнения функции даже в самом худшем случае. Все сравнения и обмены выполняются во внутреннем цикле. (Слегка улучшенная версия алгоритма пузырьковой сортировки завершает работу, если при просмотре массива не было сделано ни одного обмена, но это достигается за счет добавления еще одного сравнения при каждом проходе внутреннего цикла.)   

      Сортировка Шелла

    Сортировка  Шелла является довольно интересной модификацией алгоритма сортировки простыми вставками.

    Рассмотрим  следующий алгоритм сортировки массива a[0].. a[15].

    

    1. Вначале сортируем простыми вставками  каждые 8 групп из 2-х элементов  (a[0], a[8[), (a[1], a[9]), ... , (a[7], a[15]).

    

    2. Потом сортируем каждую из  четырех групп по 4 элемента (a[0], a[4], a[8], a[12]), ..., (a[3], a[7], a[11], a[15]).

    

    В нулевой группе будут элементы 4, 12, 13, 18, в первой - 3, 5, 8, 9 и т.п.

    3. Далее сортируем 2 группы по 8 элементов, начиная с (a[0], a[2], a[4], a[6], a[8], a[10], a[12], a[14]).

    

    4. В конце сортируем вставками  все 16 элементов.

    

    Очевидно, лишь последняя сортировка необходима, чтобы расположить все элементы по своим местам. Так зачем нужны  остальные ?

    Hа  самом деле они продвигают  элементы максимально близко  к соответствующим позициям, так  что в последней стадии число перемещений будет весьма невелико. Последовательность и так почти отсортирована. Ускорение подтверждено многочисленными исследованиями и на практике оказывается довольно существенным.

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

    Использованный в примере набор ..., 8, 4, 2, 1 - неплохой выбор, особенно, когда количество элементов - степень двойки. Однако гораздо лучший вариант предложил Р.Седжвик. Его последовательность имеет вид

    

    При использовании таких приращений среднее количество операций: O(n^7/6), в худшем случае - порядка O(n^4/3).

    Обратим внимание на то, что последовательность вычисляется в порядке, противоположном  используемому: inc[0] = 1, inc[1] = 5, ... Формула дает сначала меньшие числа, затем все большие и большие, в то время как расстояние между сортируемыми элементами, наоборот, должно уменьшаться. Поэтому массив приращений inc вычисляется перед запуском собственно сортировки до максимального расстояния между элементами, которое будет первым шагом в сортировке Шелла. Потом его значения используются в обратном порядке. 
При использовании формулы Седжвика следует остановиться на значении inc[s-1], если 3*inc[s] > size.

int increment(long inc[], long size) {

  int p1, p2, p3, s; 

  p1 = p2 = p3 = 1;

  s = -1;

  do {

    if (++s % 2) {

      inc[s] = 8*p1 - 6*p2 + 1;

    } else {

      inc[s] = 9*p1 - 9*p3 + 1;

      p2 *= 2;

      p3 *= 2;

    }

      p1 *= 2;

  } while(3*inc[s] < size);   

  return s > 0 ? --s : 0;

} 

template<class T>

void shellSort(T a[], long size) {

  long inc, i, j, seq[40];

  int s; 

  // вычисление  последовательности приращений

  s = increment(seq, size);

  while (s >= 0) {

      // сортировка вставками с инкрементами inc[]

      inc = seq[s--]; 

    for (i = inc; i < size; i++) {

      T temp = a[i];

      for (j = i-inc; (j >= 0) && (a[j] > temp); j -= inc)

        a[j+inc] = a[j];

      a[j+inc] = temp;

    }

  }

} 

Часто вместо вычисления последовательности во время каждого  запуска процедуры, ее значения рассчитывают заранее и записывают в таблицу, которой пользуются, выбирая начальное приращение по тому же правилу: начинаем с inc[s-1], если 3*inc[s] > size. 
 
 
 

 

    2. Постановка задачи 

    Математическая  постановка задачи 

    По  методам сортировки данных (в данной лабораторной работе рассматривается три метода сортировки) написать программу на их выполнения.

    В соответствии с поставленной задачей будут проведены следующие действия:

1. Отсортировать структурный массив машин в порядке возрастания по номерам машин и вывести только машины марки Жигули по следующим методам сортировки:

• сортировка выбором;
• пузырьковая сортировка;
• сортировка Шелла.

 
 
 
 

                            Алгоритмическая постановка задачи 

    Разработать программу для выполнения следующих операций:

1. Отсортировать по возрастанию структурный массив машин методом выбора;

2. Отсортировать по возрастанию структурный массив машин  методом пузырьковой сортировки;

3. Отсортировать по возрастанию структурный массив машин методом Шелла;