Отправляет 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


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


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

Автор
ferrik

Статистика

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

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


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

 Добрый день. Сегодня о сортировке методом вставок. С этим алгоритмом знакомо большинство из вас. Его вы встречаете во многих карточных играх.

ferrik@mail.ru


Теория

Допустим, нам надо отсортировать 7 чисел по возрастанию:
1.Сравним первые два элемента и расставим их в нужном порядке.
2.Посмотрим на третий элемент и вставим его в нужную позицию по отношению к первым двум элементам.
3.Посмотрим на четвёртый элемент и вставим его в нужную позицию по отношению к первым трём элементам.
...
7.Посмотрим на седьмой элемент и вставим его в нужную позицию по отношению к первым шести элементам.

0)
72331484912750
1)
33721484912750
2)
14337284912750
3)
14337284912750
4)
14337284912750
5)
14273372849150
6)
14273350728491
end)
14273350728491

Код:
procedure InsertionSort(var a:TMyArray;aStart,aEnd:integer);
var
i,j : integer;
null : integer;
begin
for i:=succ(aStart) to aEnd do
begin
null:=a[i];
j:=i;
while (j > aStart) and (null < a[j-1]) do
begin
a[j]:=a[j-1];
dec(j);
end;
a[j]:=null;
end;
end;

Попробуйте перед тем как сортировать, установить наименьший элемент на первое место(в таблице замеров такой способ стоит под именем InsertionO). Усовершенствованный код я выкладывать не буду.

Пример оптимизированной сортировки:
Аналогично первый таблице, только сначала число 14(минимальное) меняется с числом 72(стоящее на первом месте).
0)
72331484912750
1)
14337284912750
2)
14337284912750
3)
14337284912750
4)
14337284912750
5)
14337284912750
6)
14273372849150
7)
14273350728491
end)
14273350728491


Замеры

Результаты даны в мс.
Тест проводился с использованием внутреннего счётчика тактов.
При тестировании приоритет приложений был максимальный.
Кол-во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
Insertion0.00120.00340.01140.04160.15880.61692.44139.719338.740154.76618.772474.213597
InsertionO0.00130.00330.00990.03380.12380.47231.84817.326129.112116.23463.991855.511466
http://subscribe.ru/
http://subscribe.ru/feedback/		 Подписан адрес:
Код этой рассылки: comp.soft.prog.fprogram		 Отписаться
В избранное