Оптимальная сортировка

← →
Mr.F © (2005-06-06 16:28) [0]

Есть такая задача: дан массив, в нем куча элементов в массиве... (> 10^9)
Надо их отсортировать. Элементы не повторяются. Одна операция сравнения = далеко не один цикл процессора, поскольку элементами массива являются указатели на строки с нулевым символом в конце.
Нужен реальный алгоритм (код), который сведет к минимуму операции сравнения элементов.

← →
Anatoly Podgoretsky © (2005-06-06 16:30) [1]

Такого массива в Дельфи быть не может.

← →
Digitman © (2005-06-06 16:31) [2]

> операция сравнения = далеко не один цикл процессора, поскольку
> элементами массива являются указатели на строки с нулевым
> символом в конце

целиком строки что ли сравниваешь ? или как ?

уважающие себя алгоритмы поступают иначе ..

← →
Digitman © (2005-06-06 16:32) [3]

> куча элементов в массиве... (> 10^9)

и точно) ... врешь и не моргаешь !)

← →
Mr.F © (2005-06-06 16:34) [4]

> Такого массива в Дельфи быть не может.
Бывают такие массивы... дело в том, что это всего лишь array of Char, в котором непрерывно записаны строки, разделенные нулевым символом
> уважающие себя алгоритмы поступают иначе ..
И как же они поступают???

← →
Mr.F © (2005-06-06 16:35) [5]

сорри... 10^6 :)))

← →
Digitman © (2005-06-06 16:37) [6]

> Бывают такие массивы

угу ... и ты, конечно же, готов дать голову на отсечение. что своими глазами видел length(такого_массива) >= 10^9 .. )

нельзя ли поскромней ?) ... не врать хотя бы ?)

> И как же они поступают

некоторые сравнивают сначала длину (если есть готовая)
далее посимвольно, в цикле, с учетом кодировки и case-условий..

← →
Digitman © (2005-06-06 16:39) [7]

> Элементы не повторяются

сразу квиксорт напрашивается

← →
Mr.F © (2005-06-06 16:40) [8]

> некоторые сравнивают сначала длину (если есть готовая)
Готовая - есть, но помочь она ничем не может... ведь проверка в алгоритмах не на равенство, а < или >...
Так какие все-таки алгоритмы уважают себя???

QuickSort (сортировка Хоара)

> Mr.F © (06.06.05 16:40) [8]

> ведь проверка в алгоритмах не на равенство, а < или >...

если 1-я строка короче 2-й, то в зависимости от КОНКРЕТНЫХ выбранных критериев "равенства" можно сразу утверждать, что 1-я > 2-й, или 2-я > 1-й

> какие все-таки алгоритмы уважают себя?

те самые, которые с учетом выбранной codepage и collation order спавнивают строки посимвольно

Оптимальная сортировка Найти похожие ветки