Re: быстpая соpтиpовка

From

Oleg Khovayko ()

To

Alexx Ovodov

Date

2002-12-26T08:04:23Z

Area

RU.ALGORITHMS

From: Oleg Khovayko <olegh@hotpop.com>

Alexx Ovodov wrote:

Вообще говоря, все эти сортировки хорошо описаны в 3-м томе Кнута.
Том так и называется: Поиск и сортировка.
В электронном виде, по-моему, есть у Мошкова: www.lib.ru

Но судя по твоим высказываниям типа:

 > памяти очень мало, я пpогy для микpоконтpоллеpа мк51 пишy.
 > ок, поищy описание пpиведенных тобой алгоpитмов в инете
...
 >128 байт с пpямой адpесацией и 128 с косвенной адpесацией
 > pеально могy отвести байт 10-15 пpямой памяти и 40-50 косвенной

Похоже, что тебе надо использовать побитовую сортировку.
Почему именно побитовую? Отвечаю:

1. Время сортировки пропорционально N*Log(N)
2. Не требует подготовительных операций типа пре-сканирования
массива для поиска медианы.
3. Не требует дополнительной памяти для данных
4. Количество уровней рекурсии НИКОГДА не превысит количества бит
в твоем сортируемом слове - то есть уровней рекурсии будет не более 16, 
тогда как для quicksort-a возможен такой набор данных,
что число уровней рекурсии станет равно длине сортируемого массива.
У тебя в микроконтроллере стек ограничен, поэтому данное свойство
алгоритма становится очень важным.
5. Нет такого набора данных, который заваливает алгоритм в N*N,
тогда как для классического quicksort-a без доп. примочек такой
набор данных есть - это уже отсортированый массив, или же массив с 
большим количеством повторов.
6. При программировании сортировки 16-битовых чисел
на ассемблере для машины с 8-разрядной шиной (а я так понимаю, что
у тебя именно этот случай) возможен такой способ ускорения:
На последних фазах сортировки, когда сортировка идет в битах младшего 
байта, алгоритм гарантирует, что содержимое старшего байта одинаково у
всех элементов в сортируемом подблоке. Это позволяет использовать вместо
сравнения и перестановки 16-битовых int-ов сравнение/перестановку их
младших байтов, что вдвое снизит загрузку 8-битового процессора на
этих этапах сортировки. То есть это при прочих равных даст где-то 20%
выигрыша в скорости.

Про то, как устроена пробитовая сортировка,
и как ее реализовать, читай тут:

http://www.codenet.ru/progr/alg/11.php
http://home.pride-net.ru/~pkolledz/nepi/departments/inf_sub_fac/str_alg/7.html
http://jsf.boom.ru/programm/algoritm/index.htm
http://www.helloworld.ru/texts/comp/algor/data/sfaq/index.htm

--- ifmail v.2.15dev5
 * Origin: Demos online service (2:5020/400)