Сортировка и ProgressBar

← →
vasIZmax © (2007-04-16 00:36) [0]

Никак не могу сообразить как реализовать что бы во время сортировки процесс отображался в ProgressBar. Т.е посмотрев на PB можно было сказать что скоро сортировка массива закончится.
Подскажите как реализовать?
Скорее всего нужно заранее определить время за которое будет выполнена сортировка. То же вопрос как?

Или может есть другой путь?

← →
Strate © (2007-04-16 00:41) [1]

Путь номер раз:

Внутри цикла сортировки писать код двигающий прогрессбар и Вставлять Application.ProcessMessages;

Путь номер два:

Сделать сортировку в отдельном потоке, внутри Thread.Execute вызывать процедуру отрисовки PB Synchronize(DrawProgressBar); (процедура без параметров должна быть, поэтому юзай глобальные переменные).

← →
Strate © (2007-04-16 00:42) [2]

Ах, да. Определить какое именно положение должен отображать ProgressBar в каждый момент времени? ДЛя сортировки пузырьком например так:

ProgressBar.Max := count;
for i := 1 to count-1 do
begin
ProgressBar.Position := i;
for j := i+1 to count do
....

← →
sniknik © (2007-04-16 00:53) [3]

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

> Или может есть другой путь?
просто сделать сортировку максимально быстрой, так чтобы никакого прогресс бара не нужно было. (небольшую задержку можно декорировать "часиками" в курсоре)

Strate © (16.04.07 00:41) [1]
вопрос не в том как двигать прогресс бар, вопрос в том какой предел ему ставить... как показывать где начало к примеру 10% выполнения, а где почти конец 90% например.

← →
vasIZmax © (2007-04-16 01:19) [4]

В общем задача такая: я пишу код для известных мне видов сортировки(по крайней мере те что я нашел и знал). Запускаю все сортировки. И пока я делаю доклад - прога сортирует массивы. Я дочитываю доклад - останавливаю прогу. И показываю что за время моего выступления пузырек отсортировал на столько-то процентов, а слияние на столько-то. А PB будет просто подтверждением моих слов - PB нужен именно для наглядности.

Засекать время и устанавливать пределы для PB - бесмысленно, потому что могут ввести относительно любое число. Хотя возможно, это роли не сыграет если заранее определить максимально возможное.

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

К примеру, насколько я понял - обычное окошко "Копирование" устанавливает границы по количеству копируемых файлов, так вот и подумал, может тоже так организовать все - по количеству элементов массива?! Хотя, такой вариант меня несколько смущает... что-то в нем неправильно, имхо.

ЗЫ. Strate ©, sniknik © - спс))).

← →
sniknik © (2007-04-16 02:01) [5]

> Засекать время и устанавливать пределы для PB - бесмысленно, потому что могут ввести относительно любое число.
дурная идея была в том чтобы делать сортировку 2 раза, раз высчитывая время и раз показывая прогрессом, для одних и тех же введенных значений.
по другому просто не узнаешь, ни время, ни количества итераций. (если только в какомнибудь, ну очень частном случае...)

> организовать все - по количеству элементов массива?!
количество проходов может быть различным в зависимости от того "как карта ляжет".

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

← →
vasIZmax © (2007-04-16 02:32) [6]

> для одних и тех же введенных значений.

Массивы заполняются случайными числами.

> в дельфях есть пример,

его и буду скорее всего юзать)

> результирующий сводный график

да, это тоже я решил включить(т.е. посмотреть как вели себя сортировки, но это уже после того как все отсортировали): и через равные промежутки времени (5 сек) выводить % отсортированности. И та же получается проблема(все зависит от конкретного вида сортировки): определить сколько отсортировано от общего количества элементов массива? По оси х -время, по оси у - количество. Это, имхо, в код самой сортировки нужно вставить.

ЗЫ. Вот что только что в голову пришло может и бред: после того как построен график из последней точки каждого опустить перпедикуляр на Ox - и думается получим многоугольник или нет? Если действительно многоугольник - то третьим (1.PB. 2. график) наглядным "представлением" о результатах сортировок будет сравнение площадей этих многоугольников. чем меньше - тем лучше. Или я заблуждаюсь в таких выводах?

← →
MBo © (2007-04-16 05:24) [7]

Разные виды сортировки имеют разную динамику. Если для вставок или выбор есть наглядный критерий (номер последнего элемента в уже упорядоченной послед.), то для быстрой - уже труднее (можно попробовать, например, максимум из размеров кусков рекурсивных веток отслеживать).
А сортировку кучей сначала почти в обратном порядке упорядочивает, затем прямой ход делает. Поскольку обратный ход занимает O(N), то можно только при прямом (O(NlogN)) прогресс смотреть.

← →
SlymRO © (2007-04-16 06:01) [8]

vasIZmax © (16.04.07 1:19) [4]
отсортировал на столько-то процентов
Унарно - либо отсортировано, либо нет :) и никаких %

← →
sniknik © (2007-04-16 08:31) [9]

> Массивы заполняются случайными числами.
прям упорно не хочеш понимать. ну и что что случайными, что мешает после заполнения сделать копию массива?
это единственная возможность узнать - выполнить (узнать время(приблизительное т.к. загрузка системы может быть разной), или количество итераций(на которые имхо и можно ориентироваться для прогресса))

и потом если у тебя всё заполняется случайными значениями, то о каком сравнении можно говорить? а я если случайно для пузырька выдаст уже отсортированный (один проход только чтобы убедится) а на быстрой будет максимально запутанный... и покажет тогда твоя программа, что самый быстрый это "пузырек"... убедительно покажет с графиками и прогресс баром, и в самый "подходящий" раз... а препод тогда скажет "сам дурак" и поставит неуд. (и будет прав).
сравнивать методы можно только для одинаково заполненных значениями массивов.

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

> Есть еще наглядный метод ...
именно так и делается в том примере из дельфей, что советовал ранее.

Простите за тупость:(, но че-то я не могу сообразить как реализовать для сортировок:

> посмотреть как вели себя сортировки,
> и через равные промежутки времени (5 сек) выводить какое количество элементов уже отсортировано

Как это можно сделать?

ЗЫ. еще раз сорри...

> vasIZmax © (18.04.07 20:59) [12]

> Простите за тупость:(, но че-то я не могу сообразить как

Find file: thrddemo.dpr

--
Regards, LVT.

Сортировка и ProgressBar Найти похожие ветки