Ставим рекорд!

← →
NoviceA (2003-10-31 11:26) [0]

Мастера, нужен алгоритм сортировки. Задача - отсортировать массив указателей на строки. Условие такое: конечно, рекурсия, и для подсчета итераций в функцию сортировки ставится глобальная переменная, увеличивающаяся на единицу при каждом обращении. Нужно разработать алгоритм, в котором эта переменная была бы минимальной. Размер функции не имеет значения. Выглядеть все это должно примерно так:
входные параметры Функции: указатель на массив указателей на строки и длина этого массива в элементах. Чтобы обеспечить гибкость (сортировать не только строки, а, допустим, числа), внутри этой функции вызывается функция сравнения (в нашем случае указателей на строки; если нужно будет отсортировать числа, вместо нее можно будет подставить функцию, которая сравнивала бы указатели на целые числа).
Помогите пожалуйста! Нужен оптимальный алгоритм с наименьшим числом итераций.

← →
Brahman © (2003-10-31 11:35) [1]

QuickSort

← →
Romkin © (2003-10-31 11:37) [2]

Вообще-то string сама по себе указателем является :)))
Во-вторых, почему обязательно рекурсия?
В-третьих, обычно алгоритмы оценивают по их асимптотике, так что я не совсем понял условие
В-четвертых, в demos/threads уже есть QuickSort с асимптотикой О(NlogN)
В-пятых, в частных случаях можно сделать O(N)
В-шестых, Кнута еще никто не отменял, рекомендую почитать третий том
В-седьмых...

← →
Romkin © (2003-10-31 11:38) [3]

В-седьмых, почему-бы не глянуть в UBPFD?

← →
pasha_golub © (2003-10-31 12:00) [4]

Сдается мне, что пришло время олимпиад. Сорри за оффтопик

← →
Думкин © (2003-10-31 12:17) [5]

В-восьмых, каков линейный порядок для указетелей на строки?

← →
NoviceA (2003-10-31 12:18) [6]

Мужики, вы в остроумии соревнуетесь?..
Или может, поймете, что мне это ПРОСТО НАДО и нет времени чтобы самому написать? Так бывает, уж поверьте. Попросту припело. Иначе бы я не стал сюда писать.
Разве сложно выложить алгоритм?

← →
Brahman © (2003-10-31 12:20) [7]

Еще раз
QuickSort в classes.pas

← →
Думкин © (2003-10-31 12:21) [8]

Мы тебе верим, и я удивлен, что это еще не в "Потрепаться".

← →
Zacho © (2003-10-31 12:21) [9]

> NoviceA (31.10.03 12:18) [6]

Зачем выкладывать ? Он у тебя уже есть, см. Romkin © (31.10.03 11:37) [2] В-четвертых, ...

>NoviceA (31.10.03 12:18) [6]

1. Перед такими заявлениями надо указывать сколько денег ты согласен за алгоритм заплатить.

2. Тут тусуются люди, которые могут помочь, но не обязаны это делать.

Sincerely mine.

← →
NoviceA (2003-10-31 12:42) [11]

>> VMcL: Я не плачу денег за то, что могу сделать сам. Это во-первых. Во-вторых, я не думаю, что ты настоолько крут, чтобы выступать с такими заявлениями про "заплатить".

Если совсем честно - позвонила знакомая, ей это нужно в течение 3-х часов. потому и написал. попросила, я всего лишь передаю ее просьбу. проверяться правильность будет в делфи, который сейчас у меня не установлен даже и посмотреть демки у меня сейчас негде.

HeapSort рулит.
algolist.manual.ru

← →
Serginio666 (2003-10-31 13:18) [13]

Вообще алгоритм вставками StaigthMerge по моему самый лучший.
Всего в 1.5 раза уступая QuickSort. Но у QuickSort есть один большой недостаток когда много дублей и поиск половмнного значения в алгоритме не срабатывает (то же и со строками начинающихся с одинаково).
У StaigthMerge количество переносов N *Lg(N) а сравнений дажк меньше. Минус нужен второй массив.
Нужно для каждого случая подбирать свой алгоритм.

Ставим рекорд! Найти похожие ветки