Карманная сортировка — различия между версиями
Daniel (обсуждение | вклад) |
|||
| Строка 3: | Строка 3: | ||
== Алгоритм сортировки == | == Алгоритм сортировки == | ||
=== Принцип работы алгоритма вообщем === | === Принцип работы алгоритма вообщем === | ||
| + | [[Файл:Bucket-sort-example.jpg|right|300px|thumb|Пример работы рекурсивного Bucketsort.]] | ||
* элементы массива входных данных разбивается на <tex>k</tex> блоков("карманов","корзин"). | * элементы массива входных данных разбивается на <tex>k</tex> блоков("карманов","корзин"). | ||
| − | * | + | * каждый из блоков сортируется либо отдельной какой либо другой сортировкой, либо рекурсивно тем же методом разбиения. |
| − | * | + | * Из каждого отсортированного блока записываются в массив , в порядке разбиения на блоки. |
| − | Важно отметить , что разбиение на | + | Важно отметить , что разбиение на блоки производится таким образом, чтобы элементы каждого следующего блока были бы больше предыдущего. |
=== Реализация Алгоритма=== | === Реализация Алгоритма=== | ||
| − | Рассмотрим код работы алгоритма | + | Рассмотрим код работы алгоритма. |
| − | + | ||
<wikitex> | <wikitex> | ||
Bucketsort(A,j){ | Bucketsort(A,j){ | ||
| Строка 17: | Строка 18: | ||
строк. | строк. | ||
for i = 0 to A.length() - 1 | for i = 0 to A.length() - 1 | ||
| − | + | добавляем A[i] в конец массива buckets[partion(A[i],j)] | |
// partion функция которая по данному объекту и индексу возвращает число от 0 до Base - 1 | // partion функция которая по данному объекту и индексу возвращает число от 0 до Base - 1 | ||
// в случаи со строками функция partion возвращает код j-ого символа строки A[i]. | // в случаи со строками функция partion возвращает код j-ого символа строки A[i]. | ||
for i = 0 to Base - 1 | for i = 0 to Base - 1 | ||
buckets[i] = Bucketsort(buckets[i],j+1) | buckets[i] = Bucketsort(buckets[i],j+1) | ||
| − | answer <- инициализируем пустой массив | + | answer <- инициализируем пустой массив(в который записывается отсортированный набор данных) |
for i = 0 to Base - 1 | for i = 0 to Base - 1 | ||
for k = 0 to buckets[i].length() - 1 | for k = 0 to buckets[i].length() - 1 | ||
| − | + | добавляем buckets[i][k] в конец массива answer | |
return answer | return answer | ||
} | } | ||
| − | |||
| − | |||
</wikitex> | </wikitex> | ||
| − | Base - основание системы счисления в случаи со строками 256. | + | Base - основание системы счисления в случаи со строками Base = 256. |
| − | + | Приведенный код, работает не только для строк , а в принципе для любых объектов для которых можно определить порядок, системы счисления и функцию partion. | |
| − | |||
| − | |||
==Сложность== | ==Сложность== | ||
Версия 17:08, 10 июня 2012
Карманная сортировка(Bucket sort) — алгоритм сортировки , основанный на предположение о равномерном распределении входных данных.
Содержание
Алгоритм сортировки
Принцип работы алгоритма вообщем
- элементы массива входных данных разбивается на блоков("карманов","корзин").
- каждый из блоков сортируется либо отдельной какой либо другой сортировкой, либо рекурсивно тем же методом разбиения.
- Из каждого отсортированного блока записываются в массив , в порядке разбиения на блоки.
Важно отметить , что разбиение на блоки производится таким образом, чтобы элементы каждого следующего блока были бы больше предыдущего.
Реализация Алгоритма
Рассмотрим код работы алгоритма.
<wikitex>
Bucketsort(A,j){
if (A.length() < 2 || i == p + 1)
return A;
buckets <- инициализируем массив длины Base , где каждая ячейка список входных объектов (в нашем случаи
строк.
for i = 0 to A.length() - 1
добавляем A[i] в конец массива buckets[partion(A[i],j)]
// partion функция которая по данному объекту и индексу возвращает число от 0 до Base - 1
// в случаи со строками функция partion возвращает код 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. Приведенный код, работает не только для строк , а в принципе для любых объектов для которых можно определить порядок, системы счисления и функцию partion.
