Отправляет 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 за неделю
←   Все выпуски   →

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


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

 Добрый день. Сегодня, как и обещал о сортировке. В прошлом выпуске я давал задачу, но никому не захотелось её решать, поэтому задачи будут даваться в случае крайней необходимости. Также прошу написать свои отзывы и предложение: что непонятно, о чём надо поподробней, а о чём и вовсе не надо.

ferrik@mail.ru


Теория

O-нотация.
 Начиная разговор о сортировке, хотелось бы вспомнить о прошлых выпусках. В них мы изучили два метода для эмпирического анализа алгоритмов. Подходя к теме сортировке хотелось бы отметить один теоретический метод анализа, называемый O-нотацией(big-Oh notation).Это специальная математическая функция от n(количество элементов). Говорят, что алгоритм принадлежит к классу O(f(n)), f(n) - это какая-либо функция. Более просто, можно сказать, что быстродействие алгоритма пропорционально f(n). Примеры:
 1. Пример очень условен. Вам надо подсчитать сумму элементов массива. Для этого вам надо обойти все элементы. Следовательно, мы можем предположить, что алгоритм относится к классу O(n) - линейный. На практике - это один цикл, с числом итераций n.
 2. Допустим, Вы экспереминтально установили, что алгоритм принадлежит к классу O(n3+n). При сравнительно больших n мы заметим, что влияние +n очень незначительное(n3поглощает +n). Следовательно при больших n, O(n3+n) эквивалентно O(n3).
Использование O-нотации предполагает, что мы имеем дело с довольно большими значениями n.
Сортировка
Начнём с пузырьковой сортировки(bubble sort).
Эта самая известная сортировка и в то же время самая медленная.
Давайте разбираться на примере:
Допустим у нас имеется 7 чисел, которые нужно отсортировать. Сначала мы сравним 7-ое и 6-ое числа, и если 7-ое меньше, то поменяем их местами. Затем мы сравниваем 6-ое и 5-ое, и т. д. После первого прохода, мы видим, что число 29(наименьшее) оказалось на первой позиции, иначе говоря, число 29 "всплыло" на первую позицию. При последующих прохождениях мы уже не обращаемся к первой позиции.

0)
1239710058692955
1)
1239710058692955
2)
1239710058296955
3)
1239710029586955
4)
1239729100586955
5)
1232997100586955
6)
2912397100586955
7)
2912397100585569
8)
2912397100555869
9)
2912397551005869
10)
2912355971005869
11)
2955123971005869
12)
2955123971005869
13)
2955123975810069
14)
2955123589710069
15)
2955581239710069
16)
2955581239769100
17)
2955581236997100
18)
2955586912397100
19)
2955586912397100
20)
2955586997123100
21)
2955586997100123
end)
2955586997100123
Ох, и утомительное это занятие!
Вернёмся к О-нотации. При первом прохождении у нас n-1 сравнений, при втором n-2 и т. д. Общее кол-во сравнений получается
(n-1)+(n-2)+...+1 = n(n-1)/2= (n2-n)/2

Для конкретного случая: n=7, f(n)=(49-7)/2=21.
При больших n, O((n2-n)/2) эквивалентно O(n2).
Пузырьковая сортировка принадлежит к классу O(n2).

Что ж, приступим к реализации.
Чтобы что-то отсортировать, надо найти что-то не отсортированное. Давайте напишем процедуру, генерирующую массив случайных чисел:

procedure IncrementRange(var a:TMyArray;aStart,aEnd:integer);
//Процедура, которая заполняет массив числами
var
 i : integer;
begin
  for i:=aStart to aEnd do
  a[i]:=i-aStart+1;
end;

procedure RandomRange(var a:TMyArray;aStart,aEnd:integer);
//Процедура, которая перетасовывает элементы массива
var
  Range : integer;
  Inx : integer;
  RandomInx : integer;
begin
  IncrementRange(MyArr,aStart,aEnd);
//Заполним массив
  for Inx:=aEnd downto aStart+1 do
//Цикл по всем элементам
  begin
    RandomInx:=aStart+Random(Inx-aStart);
//Случайный номер элемента, от нального до текущего-1
    if RandomInx<>Inx then
//Меняем местами, используя 0 элемент как временную переменную
    begin
      a[Low(a)]:=a[Inx];
      a[Inx]:=a[RandomInx];
      a[RandomInx]:=a[Low(a)];
    end;
  end;
end;

Собственно как это работает:


0)12345678910
1)12345678109
2)11034567829
3)11038567429
4)17385610429
5)17365810429
6)17563810429
7)67153810429
end)67153810429

Перейдём к основной теме, реализуем процедуру сортировки:

const
  MaxLength=10;
type
  TMyArray=array[0..MaxLength] of integer;
var
  MyArr : TMyArray;
{...............}
procedure BubbleSort(var a:TMyArray; aStart,aEnd:integer);
var
  i,j : integer;
  Stop : boolean;
begin
  for i:=aStart to pred(aEnd) do
  begin
    Stop:=true;
    for j:=aEnd downto succ(i) do
    begin
      if a[j-1]>a[j] then
      begin
        a[Low(a)]:=a[j];
        a[j]:=a[j-1];
        a[j-1]:=a[Low(a)];
        Stop:=false;
      end;
    end;
    if Stop then exit;
  end;
end;
Код полностью я не привожу. Если будут вопросы, то пишите.

Хотелось бы рассмотреть одну модификацию пузырьковой сортировки - Шейкер-сортровка(shaker sort).
При её реализации требуется чередовать направление проходов.

0)
9735776164463
1)
9735776164463
2)
9735776164463
3)
9735776164463
4)
9735677164463
5)
9763577164463
6)
6973577164463
7)
6359777164463
8)
6357797164463
9)
6357716974463
10)
6357716449763
11)
6357716446397
12)
6357716446397
13)
6357716446397
14)
6351677446397
15)
6163577446397
16)
6163577446397
17)
6163544776397
18)
6163544637797
19)
6163544637797
20)
6163544637797
21)
6163544637797
end)
6163544637797


Так как пузырьковая сортировка относится к алгоритмам класса O(n2), то при увеличении числа элементов в 2 раза, длительность увеличивается в 4 раза. Приведу таблицу моих замеров. Значения в мс.

Кол-во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

http://subscribe.ru/
http://subscribe.ru/feedback/		 Адрес подписки
 Отписаться
В избранное