Карманная сортировка — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 35: Строка 35:
 
Пусть <tex>n</tex> — количество элементов в массиве, <tex>k</tex> — основание системы исчисления и  
 
Пусть <tex>n</tex> — количество элементов в массиве, <tex>k</tex> — основание системы исчисления и  
 
<tex>p</tex> — количество разрядов в объекте.
 
<tex>p</tex> — количество разрядов в объекте.
Тогда алгоритм "Bucket sort" в процессе работы, сделает не более чем <Tex>O(p * (n + k))</Tex> итераций.
+
Тогда алгоритм "Bucket sort" в процессе работы сделает не более чем <Tex>O(p * (n + k))</Tex> итераций.
Заметим ,что в случае случайного распределения мат. ожидания количество элементов в каждом блоке <tex> n/k</tex>. Следовательно в средним алгоритм "карманной сортировки" совершает <Tex>O(n * log_k n)</Tex> действий.При этом на некотором множестве наборов, где <tex> k = O(n)</tex> , алгоритм отработает за линейное время.
+
Заметим ,что в случае случайного распределения мат. ожидания количество элементов в каждом блоке <tex> n/k</tex>. Следовательно, в средним алгоритм "карманной сортировки" совершает <Tex>O(n \cdot log_k n)</Tex> действий. При этом на некотором множестве наборов, где <tex> k = O(n)</tex>, алгоритм отработает за линейное время.
В худшем случаи , сортировка работает за <tex>O(n^2)</tex>.
+
В худшем случае сортировка работает за <tex>O(n^2)</tex>.
 
==Примечания==
 
==Примечания==
Сортировка быстро работает для равновероятного распределения значений разрядов объектов в заданной для них системы счисления.
+
Сортировка быстро работает для равновероятного распределения значений разрядов объектов в заданной для них системе счисления.
[[Быстрая сортировка|быстрая сортировка]] является частным случаем "карманной" сортировкой, в случаи разбиения всех элементов на <tex>2 </tex> "кармана".Также стоит отметить, что по принципу своей работы Bucket sort схожа с [[Цифровая сортировка|Цифровой сортировкой]].
+
[[Быстрая сортировка|Быстрая сортировка]] является частным случаем "карманной" сортировки, в случае разбиения всех элементов на <tex>2 </tex> "кармана". Также стоит отметить, что по принципу своей работы Bucket sort схожа с [[Цифровая сортировка|Цифровой сортировкой]].
 
==Ссылки==
 
==Ссылки==
 
* http://en.wikipedia.org/wiki/Bucket_sort
 
* http://en.wikipedia.org/wiki/Bucket_sort

Версия 19:05, 10 июня 2012

Карманная сортировка(Bucket sort) — алгоритм сортировки , основанный на предположении о равномерном распределении входных данных.

Алгоритм сортировки

Принцип работы

Пример работы рекурсивного Bucketsort.
  • элементы массива входных данных разбиваются на [math]k[/math] блоков ("карманов","корзин").
  • каждый из блоков сортируется либо другой сортировкой, либо рекурсивно тем же методом разбиения.
  • из каждого отсортированного блока данные записываются в массив в порядке разбиения на блоки.

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

Реализация

Рассмотрим код работы алгоритма, где [math] p [/math] — длина каждой строки. <wikitex>

Bucketsort(A, j){ // A - массив данных, j - текущий разряд
    if (A.length() < 2 || j == p + 1)
        return A;
    buckets <- инициализируем массив длины Base, где каждая ячейка — список входных объектов (в нашем случае    
    строк).
    for i = 0  to A.length() - 1  
      добавляем A[i] в конец массива buckets[partition(A[i],j)] 
    // partition — функция которая по данному объекту и индексу возвращает число от 0 до Base - 1
    // в случае со строками функция partition возвращает код j-ого символа строки A[i].  
    for i = 0 to Base - 1
       buckets[i] = Bucketsort(buckets[i],j+1)
    answer <- инициализируем пустой массив (в который записывается отсортированный набор данных)
    for i = 0 to Base - 1
       for k = 0 to buckets[i].length() - 1
          добавляем  buckets[i][k] в конец массива answer
    return answer
}

</wikitex> Base - основание системы счисления в случае со строками Base = 256.

Приведенный код работает не только для строк, а для любых объектов для которых можно определить порядок, систему счисления и функцию partition.

Асимптотика

Пусть [math]n[/math] — количество элементов в массиве, [math]k[/math] — основание системы исчисления и [math]p[/math] — количество разрядов в объекте. Тогда алгоритм "Bucket sort" в процессе работы сделает не более чем [math]O(p * (n + k))[/math] итераций. Заметим ,что в случае случайного распределения мат. ожидания количество элементов в каждом блоке [math] n/k[/math]. Следовательно, в средним алгоритм "карманной сортировки" совершает [math]O(n \cdot log_k n)[/math] действий. При этом на некотором множестве наборов, где [math] k = O(n)[/math], алгоритм отработает за линейное время. В худшем случае сортировка работает за [math]O(n^2)[/math].

Примечания

Сортировка быстро работает для равновероятного распределения значений разрядов объектов в заданной для них системе счисления. Быстрая сортировка является частным случаем "карманной" сортировки, в случае разбиения всех элементов на [math]2 [/math] "кармана". Также стоит отметить, что по принципу своей работы Bucket sort схожа с Цифровой сортировкой.

Ссылки