Метод пузырька.

[prowoke]

Делаю сейчас лабы к зачёту, и там сортировка массивов и обьясняется сортировка пузырьком. Так вот дан такой код в примере ( сортирует по возрастанию 10 рандомных чисел):

Код: Выделить всё

program puzirok;
uses crt;
conts n=10;
vat i,j: word;
s: word;
a: array[1..n] of word;
begin
clrscr;
randomize;
for i:=1 to n-1 do
for j:=i+1 to n do
if a[i]>= a [j] then
begin
s:=a[i]; a[i]:=a[j]; a[j]:=s;
end;
for i:=1 to n do write(a[i]:5);
writeln;
readln;
end.


вопрос именно к этому куску

Код: Выделить всё

for i:=1 to n-1 do
for j:=i+1 to n do
if a[i]>= a [j] then
begin
s:=a[i]; a[i]:=a[j]; a[j]:=s;
end;


Как я понимаю метод пузырька работает так:
Имееем массив (1, 3, 17, 20, 4, 7, 9, 13, 11, 1) И этот алгоритм сортирует его таким образом:
a) 1, 3, 17, 4, 7, 9, 13, 11, 1, 20; { Это первый проход}
b)1, 3, 4, 7, 9, 13, 11, 1, 17, 20; { Второй проход }
c)1, 3, 4, 7, 9, 11, 1, 13, 17, 20; { Третий} и т.д.
Ну вот в этом коде я не понимаю как это реализуется, сколько пытался понять, не понимаю как это в нём работает ( или я неправильно алгоритм понял?)
Если кому несложно и кто меня понял, обьясните мне пожалуйста или дайте ссылочку, где можно почитать об этом. Просто я жалкий и унылый недоWEBер и => я глуп.

[скалогрыз]

эпичная тема!
http://ru.wikipedia.org/wiki/Метод_пузырька

http://www.sorting-algorithms.com/ см Bubble метод

[prowoke]

лол)
но вопрос немного в другом

Добавлено спустя 4 минуты 3 секунды:

лол)
но вопрос немного в другом, или в том, чёт я запутался.

[скалогрыз]

попей пива! определишься с тем что ты хочешь!

[prowoke]

Я хочу узнать, правильно ли я понял сортировку, на пример:
Имееем массив (1, 3, 17, 20, 4, 7, 9, 13, 11, 1) И этот алгоритм сортирует его таким образом:
a) 1, 3, 17, 4, 7, 9, 13, 11, 1, 20; { Это первый проход}
b)1, 3, 4, 7, 9, 13, 11, 1, 17, 20; { Второй проход }
c)1, 3, 4, 7, 9, 11, 1, 13, 17, 20; { Третий} и т.д.
Да/нет? Вот так вот поконкретнее вроде).

Добавлено спустя 28 минут 10 секунд:
Всё, разобрался вроде.
Я тут сам с собой разговариваю походу.

[Timid]

Вообще-то это не метод пузырька, а, скорее, "осаждения".
В методе пузырька проводится парное сравнение ближайших членов массива и производится перестановка. Большое число как-бы убегает вверх.
У тебя сравнивается нижний элемент с остальными.

Примерно будет так:

Код: Выделить всё

for i:=0 to 5 do begin
  for j:=1 to 5 do begin
    if a[j-1]>a[j] then begin
      a_swap:=a[j];
      a[j]:=a[j-1];
      a[j-1]:=a_swap;
    end;
  end;
end;


Метод самый медленный из известных. Оптимизируется только если можно счетчик делать отрицательным - for i:=5 downto 0 do begin

Кстати, это единственный метод сортировки, применимый в случае, если отношения между дальними членами массива установить невозможно. Например, в экспертных системах.

[Vadim]

prowoke
Если коротко, то после первого цикла сравнения получается что самый большой (самый маленький ) элемент массива выталкивается наверх (вниз), поэтому его сравнивать и сортировать больше не надо. Следующий цикл попарного сравнения пойдёт для количества элементов на 1 меньше, чем это было для предыдущего цикла. И так до тех пор, пока не будут перебраны все элементы массива.