Разбор классических алгоритмов и олимпиадных задач. (comp.soft.prog.fprogram) : Рассылка : Subscribe.Ru

Подписаться Бесплатная «Серебряная» новостная рассылка . Подписчиков 978 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

Статистика

978 подписчиков
0 за неделю

← Все выпуски →

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

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

От автора

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

ferrik@mail.ru

Теория

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

0)	33	72	14	84	91	27	50
1)	14	72	33	84	91	27	50
2)	14	72	33	84	91	27	50
3)	14	27	33	84	91	72	50
4)	14	27	33	50	91	72	84
5)	14	27	33	50	72	91	84
6)	14	27	33	50	72	84	91
end)	14	27	33	50	72	84	91

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

Ну и конечно же, код:
Замечу, что нулевой элемент массива я использую как временную переменную.
Использовать процедуру стоит так - 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;

Замеры

Кол-во	16	32	64	128	256	512	1024	2048	4096	8192	16384	32768	65536
Bubble	0.0025	0.0085	0.0323	0.1293	0.5214	2.0936	8.3018	32.793	130.88	532.87	2151.6	8685.4	47761
Shaker	0.0025	0.0080	0.0282	0.1092	0.4288	1.6955	6.7565	26.718	106.15	426.11	1716.6	6896.2	30936
Selection	0.0024	0.0070	0.0222	0.0772	0.2831	1.0826	4.1964	16.536	65.508	263.50	1054.2	4213.4	19436

http://subscribe.ru/
http://subscribe.ru/feedback/

Адрес подписки

Отписаться

В избранное