Сортировка пузырьком(BubbleSort) и ее улучшения.
Falk0ner, вс, 06/07/2008 - 15:35.
Анализ алгоритма простого пузырька:
Число сравнений
C = 1/2 (n^2 - n),
Числа пересылок:
Mmin = 0, Mсреднее = 3/4 (n^2 - n), Mmax = 3/2 (n^2 - n).
Анализ шейкер-сортировки (из книги Д.Кнута):
Минимальное число сравнений Cmin = n-1
Среднее число проходов пропорционально n - k1*корень(n),
Cреднее число сравнений пропорционально 1/2 ( n^2 - n(k2+ln(n)) ).
Hо, как видно, все предложенные усовершенствования не влияют на число
обменов. К сожалению, обмен - операция, как правило, гораздо более
медленная, чем сравнение ключей, поэтому реальный эффект улучшений
гораздо меньше, чем можно было бы ожидать.
Метод пузырька и описанные улучшения на практике крайне неэффективны,
SelectSort и InsertSort работают быстрее. Шейкер-сортировку выгодно
использовать, когда известно, что элементы уже почти упорядочены.
Hо даже в этом случае обычно применяют все же InsertSort, которая
менее чувствительна к степени упорядоченности.
http://algolist.manual.ru
Сортировка пузырьком(BubbleSort) и ее улучшения. Операция сравнения/перестановки выполняется для каждых двух стоящих рядом элементов. После первого прохода по массиву "вверху" оказывается самый "легкий" элемент. Следующий цикл сортировки выполняется начиная со второго элемента, в результате чего вторым в массиве оказывается второй наименьший по величине элемент, и так далее.
{ Сортируются записи типа item по ключу item.key }
{ для вспомогательных переменных используется тип index }
procedure BubbleSort;
var i,j: index; x:item;
begin for i:=2 to n do
begin for j:=n downto i do
if a[j-1].key > a[j].key then
begin x:=a[j-1]; a[j-1]:=a[j]; a[j]:=x;
end;
end;
end;
{ для вспомогательных переменных используется тип index }
procedure BubbleSort;
var i,j: index; x:item;
begin for i:=2 to n do
begin for j:=n downto i do
if a[j-1].key > a[j].key then
begin x:=a[j-1]; a[j-1]:=a[j]; a[j]:=x;
end;
end;
end;
Пример 1. Проходим по массиву снизу вверх. Меньшие/более легкие/
элементы 'всплывают' наверх, давая название методу.
Hачальные i i i i i i i
ключи 2 3 4 5 6 7 8
44 /-> 06 06 06 06 06 06 06
55 | 44 /-> 12 12 12 12 12 12
12 | 55 | 44 /-> 18 18 18 18 18
42 | 12-/ 55 | 44 /-> 42 42 42 42
94 | 42 /-> 18-/ 55 | 44 --> 44 44 44
18 | 94 | 42 42-/ 55 55 --> 55 55
06-/ 18-/ 94 -> 67 67 67 67 --> 67
67 67 67-/ 94 94 94 94 94
Алгоритм пузырька очень медленен и неэффективен. Тем не менее,
у него есть громадный плюс: он прост и его можно по-всякому улучшать.
Чем мы сейчас и займемся.
Посмотрите на пример 1. Три последних прохода никак не влияют на
порядок элементов, поскольку те уже отсортированы. Очевидный способ улучшить
алгоритм - запоминать, производился ли на данном проходе какой-либо обмен.
Если нет - это означает, что алгоритм может закончить работу.
Этот процесс улучшения можно продолжить, если запоминать не столько
сам файт обмена, но и место (индекс) последнего обмена. Ведь ясно, что
все пары соседих элементов с индексами, меньшими этого индекса k,
уже расположены в нужном порядке. Поэтому следующие прозоды можно заканчивать
на этом индексе, вместо того чтобы двигаться до установленной заранее
нижней границы i.
Пойдем дальше: внимательный человек легко может заметить странную
асимметрию: один неправильно расположенный 'пузырек' в 'тяжелом'
конце рассортированного массива всплывет за один проход, а неправильно
расположенный элемент в легком конце будет опускаться на правильное
место только на один шаг при каждом проходе.
Hапример, массив 12 18 42 44 55 67 94 06 будет отсортирован за 1 проход,
а сортировка массива 94 06 12 18 42 44 55 67 потребует 7 проходов.
Эта неестественная асимметрия подсказывает третье улучшение:
менять направление следующих один за другим проходов.
Получившийся алгоритм иногда называют 'шейкер-сортировкой'.
Пример его работы на том же входном массиве.
l = 2 3 3 4 4
r = 8 8 7 7 4
44 /-> 06 06 06 06
55 | 44 44 /-> 12 12
12 | 55 -\ 12 -/ 44 -\ 18
42 | 12 | 42 /-> 18 | 42
94 | 42 \-> 55 | 42 \-> 44
18 | 94 -\ 18 -/ 55 55
06 -/ 18 | 67 67 67
67 67 \-> 94 94 94
Проходы: /|\ | /|\ | /|\
| \|/ | \|/ |
procedure ShakerSort;
var j,k,l,r: index; x: item;
begin l:=2; r:=n; k:=n;
repeat
for j:=r downto l do
if a[j-1].key > a[j].key then
begin x:=a[j-1]; a[j-1]:=a[j]; a[j]:=x;
k:=j;
end;
l:=k+1;
for j:=l to r do
if a[j-1].key > a[j].key then
begin x:=a[j-1]; a[j-1]:=a[j]; a[j]:=x;
k:=j;
end;
r:=k-1;
until l>r;
end;
var j,k,l,r: index; x: item;
begin l:=2; r:=n; k:=n;
repeat
for j:=r downto l do
if a[j-1].key > a[j].key then
begin x:=a[j-1]; a[j-1]:=a[j]; a[j]:=x;
k:=j;
end;
l:=k+1;
for j:=l to r do
if a[j-1].key > a[j].key then
begin x:=a[j-1]; a[j-1]:=a[j]; a[j]:=x;
k:=j;
end;
r:=k-1;
until l>r;
end;
Анализ алгоритма простого пузырька:
Число сравнений
C = 1/2 (n^2 - n),
Числа пересылок:
Mmin = 0, Mсреднее = 3/4 (n^2 - n), Mmax = 3/2 (n^2 - n).
Анализ шейкер-сортировки (из книги Д.Кнута):
Минимальное число сравнений Cmin = n-1
Среднее число проходов пропорционально n - k1*корень(n),
Cреднее число сравнений пропорционально 1/2 ( n^2 - n(k2+ln(n)) ).
Hо, как видно, все предложенные усовершенствования не влияют на число
обменов. К сожалению, обмен - операция, как правило, гораздо более
медленная, чем сравнение ключей, поэтому реальный эффект улучшений
гораздо меньше, чем можно было бы ожидать.
Метод пузырька и описанные улучшения на практике крайне неэффективны,
SelectSort и InsertSort работают быстрее. Шейкер-сортировку выгодно
использовать, когда известно, что элементы уже почти упорядочены.
Hо даже в этом случае обычно применяют все же InsertSort, которая
менее чувствительна к степени упорядоченности.
http://algolist.manual.ru
{ **** UBPFD *********** by kladovka.net.ru ****
>> Обычная сортировка методом "пузырька"
ПРостой способ отсортировать массив данных
Зависимости: стандартный набор
Автор: Oleg Yu. Borodin AKA Cyber, ICQ:52779990, Tomsk
Copyright: Oleg Yu. Borodin AKA Cyber
Дата: 16 февраля 2004 г.
********************************************** }
var
l,m,mi,d:integer;
mWin:array [0..8] of integer;
begin
Randomize;
for l:=0 to 8 do mWin[l]:=Random(100);
for l:=0 to 7 do //последний элемент не считаем - он уже будет
//стоять на своем месте
begin
d:=0;
mi:=0;//ищем максимальный элемент
for m:=l to 8 do
if mWin[m]>mi then
begin
mi:=mWin[m];
d:=m;//находим позицию максимального элемента массива
end;
mi:=mWin[l];//текущий сохраняем
mWin[l]:=mWin[d];//вставляем максимальный
mWin[d]:=mi;//текущий переставляем на свободное место
end;
end;//все
>> Обычная сортировка методом "пузырька"
ПРостой способ отсортировать массив данных
Зависимости: стандартный набор
Автор: Oleg Yu. Borodin AKA Cyber, ICQ:52779990, Tomsk
Copyright: Oleg Yu. Borodin AKA Cyber
Дата: 16 февраля 2004 г.
********************************************** }
var
l,m,mi,d:integer;
mWin:array [0..8] of integer;
begin
Randomize;
for l:=0 to 8 do mWin[l]:=Random(100);
for l:=0 to 7 do //последний элемент не считаем - он уже будет
//стоять на своем месте
begin
d:=0;
mi:=0;//ищем максимальный элемент
for m:=l to 8 do
if mWin[m]>mi then
begin
mi:=mWin[m];
d:=m;//находим позицию максимального элемента массива
end;
mi:=mWin[l];//текущий сохраняем
mWin[l]:=mWin[d];//вставляем максимальный
mWin[d]:=mi;//текущий переставляем на свободное место
end;
end;//все
В основе алгоритма лежит обмен соседних элементов массива. Каждый элемент массива, начиная с первого, сравнивается со следующим, и если он больше следующего, то элементы меняются местами. Таким образом, элементы с меньшим значением продвигаются к началу массива (всплывают), а элементы с большим значением — к концу массива (тонут). Поэтому данный метод сортировки обменом иногда называют методом "пузырька". Этот процесс повторяется столько раз, сколько элементов в массиве, минус единица.
procedure TForm1.Button1Click(Sender: TObject);
const
SIZE = 5;
var
a: array[1..SIZE] of integer;
k: integer; // текущий элемент массива
i: integer; // индекс для ввода и вывода массива
changed: boolean; // TRUE, если в текущем цикле были обмены
buf: integer; // буфер для обмена элементами массива
begin
// ввод массива
for i := 1 to SIZE do
a[i] := StrToInt(StringGrid1.Cells[i - 1, 0]);
label2.caption := '';
// сортировка массива
repeat
Changed := FALSE; // пусть в текущем цикле нет обменов
for k := l to SIZE - 1 do
if a[k] > a[k + l] then
begin // обменяем k-й и k+1-й элементы
buf := a[k]; a[k] := a[k + l]; a[k + l] := buf;
changed := TRUE;
end;
// вывод массива
for i := l to SIZE do
Label2.caption := label2.caption + ' ' + IntTostr(a[i]);
Label2.caption := label2.caption + #13;
until
not changed; // если не было обменов, значит
// массив отсортирован
Label2.caption := label2.caption + #13 + 'Maccив отсортирован.';
end;
const
SIZE = 5;
var
a: array[1..SIZE] of integer;
k: integer; // текущий элемент массива
i: integer; // индекс для ввода и вывода массива
changed: boolean; // TRUE, если в текущем цикле были обмены
buf: integer; // буфер для обмена элементами массива
begin
// ввод массива
for i := 1 to SIZE do
a[i] := StrToInt(StringGrid1.Cells[i - 1, 0]);
label2.caption := '';
// сортировка массива
repeat
Changed := FALSE; // пусть в текущем цикле нет обменов
for k := l to SIZE - 1 do
if a[k] > a[k + l] then
begin // обменяем k-й и k+1-й элементы
buf := a[k]; a[k] := a[k + l]; a[k + l] := buf;
changed := TRUE;
end;
// вывод массива
for i := l to SIZE do
Label2.caption := label2.caption + ' ' + IntTostr(a[i]);
Label2.caption := label2.caption + #13;
until
not changed; // если не было обменов, значит
// массив отсортирован
Label2.caption := label2.caption + #13 + 'Maccив отсортирован.';
end;
Следует отметить, что максимальное необходимое количество циклов проверки соседних элементов массива равно количеству элементов массива минус один. Вместе с тем возможно, что массив реально будет упорядочен за меньшее число циклов. Например, последовательность чисел 5 1 2 3 4, если ее рассматривать как представление массива, будет упорядочена за один цикл, и выполнение оставшихся трех циклов не будет иметь смысла.
Поэтому в программу введена логическая переменная changed, которой перед выполнением очередного цикла присваивается значение FALSE. Процесс сортировки (цикл repeat) завершается, если после выполнения очередного цикла проверки соседних элементов массива (цикл for) ни один элемент массива не был обменен с соседним, и, следовательно, массив уже упорядочен.
DelphiWorld 6.0
Отправить комментарий