Сортировка Шелла (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). Вот почему, мне она нравится больше других квадратичных сортировок)

Сортировка вставками (Insert_sort)

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

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

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

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

Реализация:

1. void insert_sort(vector<int> &mas) {
2.   for (int i=1;i<n;++i) {
3.     for (int j=i;j>0;j--) {
4.       if (mas[j-1] > mas[j])
5.         swap(mas[j-1],mas[j]);
6.       else
7.         break;
8.     }
9.   }
10. }

* This source code was highlighted with Source Code Highlighter.

Шейкерная сортировка (Cocktail_sort)

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

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

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

Реализация:

1. void cocktail_sort(vector<int> &mas)
2. {
3.   int l = 0, r = mas.size()-1;
4.   while (l<=r)
5.   {
6.     // всплывает самый "легкий" элемент
7.     for (int i = r ;i>l;i--)
8.       if (mas[i-1]>mas[i])
9.         swap(mas[i-1],mas[i]);
10.     l++;
11.     // тонет самый "тяжелый элемент"
12.     for (int i=l; i<r; i++)
13.       if (mas[i]>mas[i+1])
14.         swap(mas[i],mas[i+1]);
15.     r--;
16.   }
17. }

* This source code was highlighted with Source Code Highlighter.

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

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

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

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

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

Реализация:

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

* This source code was highlighted with Source Code Highlighter.

N^N mod 10^P

[Вся длинная арифметика] 

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

По условию задачи 1<=N<=1e9 и 1<=P<=100.

Квадратный корень из длинного числа

[Вся длинная арифметика]

Эта задача далась мне тяжелее всех. Наверное потому, что я пытался зачесть ее на acm.sgu.ru и acmp.ru, где ограничения на количество разрядов в числе 1000 и 3000 соответственно. Для начала зачтем эту задачу на informatics.mccme.ru, где ограничение всего 100.

Здесь можно пойти двумя путями:

Длинное - короткое

[Вся длинная арифметика]

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

Приведенная реализация практически идентична с  реализацией операции “длинное + короткое”:

1. BigInt operator - (const BigInt &a, const int &b)
2. {
3.   BigInt res = a;
4.   int pos = 0;
5.   res.digits[0] -= b;
6.   while (res.digits[pos] < 0)
7.   {
8.     res.digits[pos+1] --;
9.     res.digits[pos++] +=osn;
10.   }
11.   if (res.amount && !res.digits[res.amount-1])
12.     res.amount--;
13.   return res;
14. }

* This source code was highlighted with Source Code Highlighter.

Сортировки

Квадратичные сортировки O(N*N):

Пузырьковая                (Bubble sort)     +
Шейкерная                  (Cocktail sort)   +
Вставками                  (Insert sort)     +
Гномья                     (Gnome sort)      +
Выбором                    (Selection sort)  +


Квазилинейные O(N*log(N)):

Слиянием                   (Merge sort)      +
С помощью двоичного дерева (Tree sort)       -
Сортировка Шелла           (Shell sort)      -
Пирамидальная              (Heap sort)       -
Плавная                    (Smooth sort)     -
Быстрая                    (Quick sort)      -
STL C++                    (Intro sort)      -
Python сортировка          (Tim sort)        +


Линейные O(N):

Подсчетом                  (Counting sort)   +
Карманная                  (Bucket sort)     +
Поразрядная                (Radix sort)      -




* Плюсом отмечены стабильные сортировки

Факториал короткого числа

[Вся длинная арифметика]  

Тип int может поместить в себя не больше 12!.А как же нам быть если нужно найти 100! ? Самое время обратиться к длинной арифметике.
Сама реализация не представляет для нас ничего нового:

1. BigInt fact(int n)
2. {
3.   BigInt res(1);
4.   for (int i=2;i<=n;i++)
5.     res = res * i;
6.   return res;
7. }

* This source code was highlighted with Source Code Highlighter.

По условию задачи n<=3000. В качестве osn лучше выбрать 10000, т.к. в таком случае мы сможем обойтись умножением длинного на короткое.

Пирамидальная сортировка (Heap Sort)

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

Теория: читаем дивную статью с картинками

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

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