Сортировка Шелла (Shell_sort)

[Все сортировки]

Теория: Общая информация изложена здесь

Практика: informatics.mccme.ru

Визуализатор: rain.ifmo.ru  [Java]

Реализация:
Данная сортировка является модификацией сортировки вставками.

Сортировка с помощью бинарного дерева (Tree_sort)

[Все сортировки]

Теория: Общая информация изложена здесь

Практика: informatics.mccme.ru

Реализация:

В своей реализации эта сортировка использует структуру данных: бинарное дерево, каждый элемент которого можно описать следующим образом:

1. struct tree
2. {
3.   tree* left; // левый сын
4.   tree* right; // правый сын
5.   int value;  // значение
6. };

* This source code was highlighted with Source Code Highlighter.

Сортировка слиянием (Merge_sort)

[Все сортировки]

Теория: Общая информация изложена здесь

Практика: informatics.mccme.ru

Визуализатор: rain.ifmo.ru  [Java]

Гномья сортировка (Gnome_sort)

[Все сортировки]

Теория: Общая информация изложена здесь

Практика: informatics.mccme.ru

Реализация:

1. void gnome_sort(vector<int> &mas)
2. {
3.   int cur = 0;
4.   while (cur + 1 < mas.size())
5.   {
6.     if (mas[cur]<=mas[cur+1])
7.       cur++;
8.     else
9.     {
10.       swap(mas[cur],mas[cur+1]);
11.       cur--;
12.       if (cur<0) cur = 0;
13.     }
14.   }
15. }

* This source code was highlighted with Source Code Highlighter.

Сортировка выбором(Selection_sort)

[Все сортировки]

Теория: Общая информация изложена здесь

Практика: informatics.mccme.ru

Визуализатор: rain.ifmo.ru  [Java]

Реализация:

1. void selection_sort(vector<int> &mas)
2. {
3.   for (int i=0;i<mas.size();i++)
4.     for (int j=i+1;j<mas.size();j++)
5.       if (mas[i]>mas[j])
6.         swap(mas[i],mas[j]);
7. }

* This source code was highlighted with Source Code Highlighter.

UPD[29.09.2011]

1. void selection_sort(vector<int> &mas) {
2.   for(int i=0;i<mas.size();i++) {
3.     int minPos = i;
4.     for(int j=i+1;j<mas.size();j++)
5.       if(mas[minPos] > mas[j])
6.         minPos = j;
7.     swap(mas[minPos],mas[i]);
8.   }
9. }

* This source code was highlighted with Source Code Highlighter.

P.S: Из всех квадратичных сортировок сортировка выбором имеет самую локаничную запись и сложность O(n*(n-1)/2). Вот почему, мне она нравится больше других квадратичных сортировок)