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

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

← →
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]

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

---

← →
Хинт ©   (2005-06-06 16:42) [9]

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

---

← →
Digitman ©   (2005-06-06 17:08) [10]

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


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


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

---

← →
Digitman ©   (2005-06-06 17:10) [11]

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


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

---

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

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



Память: 0.47 MB
Время: 0.026 c