расслабьтесь! ;)

← →
lak_b (2002-05-22 14:06) [0]

объявляется конкурс!!!
победителю - ... одна лишь слава!
конкурс в следующем - необходимо написать самый медленный алгоритм сортировки вектора(одномерного массива).
вот для затравки такой:
var
есть массив и индекс(изначально равный номеру первого элемента массива)
begin
проходим массив от индекса до конца - находим MAX, например, и переставляем его вначало массива, увеличиваем индекс на 1, походим массив от индекса до конца - находим MAX, ставим вторым, увеличиваем индекс на 1,
повторяем процедуру пока индекс неравен последнему индексу массива...
end

← →
Мальфет (2002-05-22 14:19) [1]

Fag := True; while Flag do begin A := Random(Max) + 1; B := Random(Max) + 1; if V[A] < V[B] then Swap(V[A], V[B]); for I := 1 to Max - 1 do if V[I] > V[I + 1] then Break else Flag := False; Sleep(1000); end;

← →
Виктор Щербаков (2002-05-22 14:22) [2]

> Sleep(1000);

Ээээ...
Так не честно!

← →
Lord Warlock (2002-05-22 14:24) [3]

> Sleep(1000);

писал бы сразу
Sleep(1000000) :)))

← →
Мальфет (2002-05-22 14:26) [4]

Тьфу, скосячил!
...
if V[I] > V[I + 1] then begin Flag := True; Break end else Flag := False;...

← →
Mike B. (2002-05-22 14:29) [5]

А еще можно вместо сравнения просто переставлять элементы случайным образом и каждый раз проверять не отсортировался ли :-)

← →
Виктор Щербаков (2002-05-22 14:33) [6]

Mike B. ©
Браво!!!
Только как оценить время, в течение которого он он отсортируется таким образом?

← →
Мальфет (2002-05-22 14:34) [7]

Я тоже так хотел сначала сделать, но тогда это удде не будет сортировкой, как таковой ;)

← →
Мальфет (2002-05-22 14:34) [8]

Я тоже так хотел сначала сделать, но тогда это уже не будет сортировкой, как таковой ;)

← →
Mike B. (2002-05-22 14:39) [9]

>Виктор Щербаков
Время будет зависеть от типа распределения случайной функции и размера массива

← →
kaif (2002-05-22 14:44) [10]

>Mike B. © (22.05.02 14:29)
>А еще можно вместо сравнения просто переставлять элементы >случайным образом и каждый раз проверять не отсортировался ли :-)

Этот алгоритм, по мнению дарвинистов, создал человека из неупорядоченного набора нуклеотидов. Я думаю, он самый быстрый, (если повезет!). Во всяком случае, к заведомо медленным его относить нельзя.
Для самого медленного алгоритма нужно каждое сравнение попросить юзера произвести:

function CustomCompare(x1,x2: integer): boolean;
begin
Result := MessageDlg(
format(
"%d больше %d. Если вы уверены нажмите OK",
mtConfirmation,
[mbOK, mbNo],0)) = mrOK;
end;

← →
Mike B. (2002-05-22 14:45) [11]

Например, в случае, если все перестановки равновероятны наиболее вероятное время сортировки ~ n!, где n - размер массива

← →
Мальфет (2002-05-22 14:48) [12]

Хех! Пардон, батеньк, это уже междумордие, а не алгоритм. :))

← →
Mike B. (2002-05-22 14:48) [13]

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

← →
lak_b (2002-05-22 14:52) [14]

2 all
алгоритмы надо писать честно! ни каких тут вам рендомов и подтверждеий быть не должно!!!

← →
Praco (2002-05-22 15:05) [15]

Каждый элемент массива писать в файл с тем же именем. Затем файлы отсортировать, элементы прочитать обратно в массив.

А можно так

динамически создать табличку с одним полем, перекачать туда массив, а потом бегать по ней пузырьковой сортировкой.

← →
fliz (2002-05-22 15:10) [16]

надо попросить уважаемого Хавка написать
эту программу. применный им алгоритм будет
уже не так важен.

← →
kaif (2002-05-22 15:18) [17]

Честно, так честно!

Перебираем все варианты перестановок в массиве X[0..N].
Для каждого случая вызываем функцию проверки, типа упорядочен массив или нет:

function IsSorted: boolean;
begin
Result := True;
for i := 0 to N - 1 do
if not (X[i] <= X[i+1]) then
Result := False;
end;

Эффективность посчитать не могу (не помню, как выражается полное число перестановок для N элементов). Наверно Mike B. сможет.
Это самый длинный и самый надежный алгоритм, ИМХО, так как он перебирает все возможные варианты. Я обычно именно его и использую, если хочу придать солидность своему продукту (вставляю перед SQL запросом).

← →
vopros (2002-05-22 15:22) [18]

>kaif © (22.05.02 15:18)
Не понятен смысл выражения самый длинный и надежный. Наверное долгий а вот с надежностью могу поспорить все остальные алгоритмы сортируют со 100% результатом.

← →
Mike B. (2002-05-22 15:27) [19]

← →
kaif (2002-05-22 15:31) [20]

Ладно, надежность беру назад. И длинность тоже. Вдруг повезет, и первая же попытка перестановки даст результат?
Наверное, самый длинный алгоритм должен от массива зависеть так, чтобы всегда в самом конце доходить до правильного решения.

← →
lak_b (2002-05-22 15:56) [21]

подводим предварительные итоги:
- мне пока больше всего нарвиться с файлами (Praco) и перебор перестановок (kaif)
- в форуме - разброд и шатания...

← →
Mike B. (2002-05-22 15:57) [22]

Еще такая идея. Нужно использовать сортировку с помощью бинарного дерева, только наоборот (т.е при обходе дерева каждый раз смещаться по узлам в порядке обратном упорядочению). Дерево как раз дает полный перебор, остается только выбрать наименее оптимальный вариант обхода

← →
Mike B. (2002-05-22 16:00) [23]

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

← →
[NIKEL] (2002-05-22 17:55) [24]

← →
Praco (2002-05-22 18:01) [25]

расслабьтесь! ;) Найти похожие ветки