воскресенье, 19 сентября 2010 г.

Сортировка Шелла (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.

суббота, 18 сентября 2010 г.

воскресенье, 12 сентября 2010 г.

Гномья сортировка (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.

суббота, 11 сентября 2010 г.

Пузырьковая сортировка (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.

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

воскресенье, 5 сентября 2010 г.

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

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

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

Приведенная реализация практически идентична с  реализацией операции “длинное + короткое”:
  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]