Очень сложная задача на сортировку

← →
Igorek © (2003-12-19 15:48) [0]

Дан массив из N элементов. Есть Boolean функция Max - сравнения двух элементов.

Написать процедуру, которая выдает массив индексов элементов по возрастанию, при этом минимально возможное колличество раз вызывая ф-цию Max.

← →
Семен Сорокин © (2003-12-19 15:52) [1]

Загнать массив в TList, обработать Sort...
Функция Max - ни разу не выховется :))

← →
MBo © (2003-12-19 15:55) [2]

Уточни - Max здесь означает
function AGreaterThanB(A,B:Integer):Boolean;
так?

И еще один момент - элементы массива - целые или любые, на которых определено отношение порядка (><=)?

← →
Igorek © (2003-12-19 16:26) [3]

> MBo © (19.12.03 15:55) [2]
> Уточни - Max здесь означает
> function AGreaterThanB(A,B:Integer):Boolean;
> так?

Да. Равно True, когда А >B, иначе False.

> И еще один момент - элементы массива - целые или любые,
> на которых определено отношение порядка (><=)?

Любые. Впрочем это нам неизвесно. Дана только функция сравнения и то, что для них справедливо отношение транзитивности.

← →
Romkin © (2003-12-19 16:32) [4]

ответ: N*Log(N) раз (логарифм по основанию 2)

QuickSort - достаточно оптимальный алгоритм, если распределение заранее неизвестно и не имеет заранее огрворенных закономерностей

ЭЭ! Он может и на N^2 выскочить

Очень сложная задача на сортировку Найти похожие ветки