Отправляет email-рассылки с помощью сервиса Sendsay

Разбор классических алгоритмов и олимпиадных задач.

Подписаться Бесплатная «Серебряная» новостная рассылка . Подписчиков 977 RSS
  Август 2004   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


За последние 60 дней ни разу не выходила


Открыта: 01-08-2004

Автор
ferrik

Статистика

977 подписчиков
0 за неделю
←   Все выпуски   →

Разбор классических алгоритмов и олимпиадных задач.


Информационный Канал Subscribe.Ru
От автора

 Добрый день. Сегодня о сортировке методом выбора.

ferrik@mail.ru


Теория

Допустим, нам надо отсортировать 7 чисел по возрастанию:
1.Просмотрим все элементы и найдём наименьший.
2.Поменяем местами наименьший элемент и первый(в нашем случае: наименьший - 14).
3.Просмотрим элементы со второгопо седьмойи найдём наименьший(игнорируя первый).
4.Поменяем местами наименьший и второй(в нашем случае: наименьший - 27).
5.Просмортим все элементы с третьегопо седьмойи найдём наименьший(игнорирая первые два).
6.Поменяем местами наименьший и третий(в нашем случае он уже на месте).
7.Продолжим до тех пор пока элементы не будут отсортированы...

0)
33721484912750
1)
14723384912750
2)
14723384912750
3)
14273384917250
4)
14273350917284
5)
14273350729184
6)
14273350728491
end)
14273350728491

 Таблица получилась очень маленькой. Говорит ли это о том, что алгоритм достаточно быстр? Конечно же, нет. Всё дело в том, что по числу перестановок данный алгоритм принадлежит к классу O(n), а по числу сравнений к O(n2). Что это даёт на практике? Если "вес" сравнения гораздо меньше, чем перестановки, то данный алгоритм будет достаточно эффективным. В противном же случае этот метод сродни пузырьковой, хотя и немного быстрее.

Ну и конечно же, код:
Замечу, что нулевой элемент массива я использую как временную переменную.
Использовать процедуру стоит так - SelectionSort(MyArr,Low(MyArr)+1,High(MyArr)).
aStart - начальный индекс, aEnd - конечный.
procedure SelectionSort(var a:TMyArray;aStart,aEnd:integer);
var
i,j : integer;
IndexMin : integer;
begin
for i:=aStart to pred(aEnd) do
begin
IndexMin:=i;
for j:=succ(i) to aEnd do
if a[j]<a[IndexMin] then
IndexMin:=j;
if (IndexMin<>i) then
begin
a[0]:=a[i];
a[i]:=a[IndexMin];
a[IndexMin]:=a[0];
writeArray(IndexMin,i,true);
end;
end;
end;


Замеры
Кол-во1632641282565121024204840968192163843276865536
Bubble0.00250.00850.03230.12930.52142.09368.301832.793130.88532.872151.68685.447761
Shaker0.00250.00800.02820.10920.42881.69556.756526.718106.15426.111716.66896.230936
Selection0.00240.00700.02220.07720.28311.08264.196416.53665.508263.501054.24213.419436
http://subscribe.ru/
http://subscribe.ru/feedback/		 Адрес подписки
 Отписаться
В избранное