Скачать: CL | DM;

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

← →
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: Продолжение ветки про калькулятор? :)

---

← →
Думкин ©   (2004-08-24 15:11) [9]

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

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

---

← →
Palladin ©   (2004-08-24 15:46) [10]

> NikotiN ©   (24.08.04 15:01)

В реальнисти операции проводятся в основном с Integer...

---

← →
Layner ©   (2004-08-25 13:22) [11]

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

---

← →
Думкин ©   (2004-08-25 13:28) [12]

> [11] Layner ©   (25.08.04 13:22)

На 286-м? Или как?

---

Страницы: 1 вся ветка

Скачать: CL | DM;



Память: 0.48 MB
Время: 0.021 c