10 сент. 2010 г.

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

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

Сортировка вставками — простой алгоритм сортировки. Хотя этот метод сортировки намного менее эффективен, чем более сложные алгоритмы (такие как быстрая сортировка), у него есть ряд преимуществ:
  • прост в реализации;
  • эффективен на небольших наборах данных, на наборах данных до десятков элементов может оказаться лучшим;
  • эффективен на наборах данных, которые уже частично отсортированы;
  • это устойчивый алгоритм сортировки (не меняет порядок элементов, которые уже отсортированы);
  • может сортировать список по мере его получения;
  • не требует временной памяти, даже под стек.

Алгоритм

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

Реализация сортировки вставками на С++

view source
print?
01/*Сортировка вставками
02Было произведено три пункта оптимизации:
03    * нахождение минимального элемента и помещение его в первую позицию(это требуется для правильного функионирования второго пукта)
04    * выход из внутреннего цикла, когда элемент находится на требуемой позиции
05    * замена операции обмена(swap) операцией присваивания.*/
06
07template <class item="Item">
08void exch(Item &A, Item &B)
09{
10    Item t = A; A = B; B = t;
11}
12template <class item="Item">
13void compexch (Item &A, Item &B)
14{
15    if (B < A) exch(A, B) ;
16}
17template <class item="Item">
18void insertion_sort(Item a[], int L, int R)
19{
20    int i;
21    for(i = R; i > L; i--) compexch(a[i-1], a[i]);
22    for (i = L + 2; i  cur)
23        {
24            a[j] = a[j - 1];
25            j--;
26        }
27        a[j] = cur;
28    }
29}
30
31/******************/
32class>class>class>
в 16:54