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

← →
NikotiN © (2004-08-24 13:43) [0]

Мне вот интересно ваше мнение по поводу одного алгоритма сортировки.
Эффективность работы не зависит от длины массива!
звучит глупо, но вроде работает. Мы с другом довольно долго обсуждали это.
Формула проходов по массиву = 2*максимальный размер элемента(байты)
ЛЮБОЙ ДЛИНЫ массив из 1байтовых чисел сортируется за 2 прохода!
так вот его суть для однобайтовых(по размеру элемента) массивов:
создаём таблицу статистики (0-255) и инкрементируем элемент таблицы с номером = значению элемента массива. Т.е. мы создаём таблицу статистики встречаемости чисел. Пример: при числе = 37, мы увеличим на один 37ой элемент таблицы и т.д.
Теперь же разворачиваем таблицу, т.е. создав массив, где вначале идут Nное количество 0, потом 1, ... - ВСЁ! сортировали по возрастанию (вернее по неубыванию).

Как же получаем N? Берём из таблицы статистики.
Рассмотрим таблицу статистики:
НомерЭлемента-Значение
0-0
1-5
2-3
3-0
...

что это показывает:
чисел 0 в исходном массиве нет.
чисел 1 в исходном массиве 5.
чисел 2 в исходном массиве 3.
чисел 3 в исходном массиве нет.
...
N-это и есть количество чисел (т.е. сначала 0, потом 5, 3, 0...)

Думаю понятно выразился.

Сортировка массивов с элементами из 2 и более байт, заключается в сортировке сначала по первому байту, потом уже сортировка ГРУПП по второму байту....

Каково ваше мнение? сильно не ругайте. ошибок вроде нет.

← →
Думкин © (2004-08-24 13:50) [1]

Отсортировать так массив из 10 чисел с диапазоном от 1 до 4*10^9.
Или строки с 10 буквенными словами.

← →
Думкин © (2004-08-24 13:51) [2]

А вообще - http://delphimaster.ru/articles/dsort/index.html

← →
Palladin © (2004-08-24 13:52) [3]

Оригинально но не практично...

← →
Romkin © (2004-08-24 13:55) [4]

Это как же от длины-то не зависит?! Проходишь же весь массив. Хочешь сказать, ты одинаковое время на 10 и на 1000000 элементов потратишь? :))
А вообще - то, что ты привел, это упрощенная сортировка подсчетом ;)

← →
Romkin © (2004-08-24 14:09) [5]

А вообще, молодец, если сам придумал :))

← →
NikotiN © (2004-08-24 14:57) [6]

2 Romkin
я имел ввиду что длина массива не так сильно сказывается на производительности, как в других методах сортировки

← →
NikotiN © (2004-08-24 15:01) [7]

2 Думкин
//Отсортировать так массив из 10 чисел с диапазоном от 1 до 4*10^9.
//Или строки с 10 буквенными словами
А в чём проблема?

2 Palladin
//Оригинально но не практично....
Почему?

← →
Kerk © (2004-08-24 15:06) [8]

> NikotiN © (24.08.04 15:01) [7]

Тебе же ссылку дали.. ну почитай... :)

2 ALL: Продолжение ветки про калькулятор? :)

> [7] NikotiN © (24.08.04 15:01)

Это уже в приписке с разрядами не проблема.
А в изначальном, верхнем - очень даже проблема.

А вот ABBYY Lingvo между прочим сортирует 100000 записей в доли секунды :)

Алгоритм сортировки Найти похожие ветки