Главная страница
Top.Mail.Ru    Яндекс.Метрика
Текущий архив: 2009.01.04;
Скачать: CL | DM;

Вниз

Сортировка выбором   Найти похожие ветки 

 
ИванН   (2008-11-09 15:50) [0]

У меня есть код сортировки выбором http://ru.wikipedia.org/wiki/Сортировка_выбором , но в коде есть странное место, не соответствующее алгоритму описанному на википедии, а именно:

for i := 1 to n - 1 do
begin
 min := i;
 Flag := False;
 for j := i + 1 to n do
   if a[min] > a[j] then
   begin
     min := j;
     Flag := True;
   end;
 if Flag then
 begin

   t := a[i];
   a[i] := a[min];
   a[min] := t;
 end;  
end;


Вопрос - зачем сделана такая проверка?

Спасибо.


 
palva ©   (2008-11-09 16:21) [1]

Если первый элемент и так оказался минимальным, то переставлять элементы не надо. Можно было не заморачиваться с флагом, а проверять равенство min = i. Если оно выполняется, то это эквивалентно Flag = False.


 
ИванН   (2008-11-09 16:24) [2]

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


 
palva ©   (2008-11-09 18:52) [3]

Это зависит от того, сколько стоит эта пустая перестановка. Если мы занимаемся сортировкой блоков, расположенных на диске, (какая-нибудь дефрагментация), да еще если обычно блоки УЖЕ лежат как надо, и перемещать их не требуется, то такая проверка будет уместна для эффективности работы, хотя на результат работы она не повлияет.


 
TUser ©   (2008-11-09 20:50) [4]

Добавлю, что если речь идет о лбой сортиовке, где важно время, такой алгоритм всегда крайне неэффективен. Хоть бы даже  с флагом.



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

Текущий архив: 2009.01.04;
Скачать: CL | DM;

Наверх




Память: 0.47 MB
Время: 0.011 c
15-1226027966
Slider007
2008-11-07 06:19
2009.01.04
С днем рождения ! 7 ноября 2008 пятница


1-1202899639
Darvin
2008-02-13 13:47
2009.01.04
Приложение с несколькими chm файлами справки


2-1227220027
bbk
2008-11-21 01:27
2009.01.04
как проверить создан ли TFileStream;


2-1227265093
DeadMeat
2008-11-21 13:58
2009.01.04
Динамические массивы


15-1225877553
ANB
2008-11-05 12:32
2009.01.04
А чего мы отмечали 4 ноября ?