StartprogrammingusingObjectPascal:BubbleSortAlgorithm

버블 정렬 알고리즘

이 알고리즘은 단순한 정렬 알고리즘 중 하나입니다. 배열의 첫 번째 요소를 두 번째 요소와 비교해서 오름차순에서는 첫 번째 요소가 두 번째 요소보다 클 경우 서로 바꿉니다. 그 다음 두 번째 요소와 세 번째 요소를 비교하고, 이런식으로 배열의 마지막에 도달하기 전까지 계속 진행합니다. 그 후 배열이 이미 정렬되었다는 의미로 바꾸기 동작이 안 일어날 때까지 이 동작을 반복합니다.

배열에 다음 6개의 값을 지니고 있다고 가정해봅니다.

7
10
2
5
6
3

정렬을 하기 위해 한 바퀴 이상 돌아야 한다는 것을 알 것입니다.

첫 번째 숫자를 두 번째 것과 비교할 것이고 처음 것이 두 번째 것보다 크면 바꾸기 동작이 일어날 것이며, 다섯 번째 요소를 여섯 번째 요소와 비교하기 전까지 두 번째를 세 번째와 비교할 것입니다.

처음 한 바퀴를 돌고 나면 배열은 다음과 같이 될 것입니다.

7
2
5
6
3
10

두 번째 바퀴 다음순서

2
5
6
3
7
10

세 번째

2
5
3
6
7
10

네 번째

2
3
5
6
7
10

네 바퀴를 돌고 나서 정렬된 배열을 얻게 되는데, 네 바퀴 째에서는 바꾸기 동작이 일어나지 않기 때문입니다. 이는 이들 데이터를 정렬하는데 세 바퀴만 도는 것이 필요하지만, 네 번째는 정렬의 발생을 확인하기 위해 사용한다는 것을 의미합니다.

작은 수가 큰 수 위로 거품처럼 떠다니는 것을 눈여겨 보도록 합니다.

다음은 버블 정렬 프로그램입니다.

program BubbleSortProj;

{$mode objfpc}{$H+}

uses
    {$IFDEF UNIX}{$IFDEF UseCThreads}
    cthreads,
    {$ENDIF}{$ENDIF}
    Classes;

procedure BubbleSort(var X: array of Integer);
var
    Temp: Integer;
    i: Integer;
    Changed: Boolean;
begin
    repeat // Outer loop
        Changed:= False;
        for i:= 0 to High(X) - 1 do // Inner loop
            if X[i] > X[i + 1] then
            begin
                Temp:= X[i];
                X[i]:= X[i + 1];
                X[i + 1]:= Temp;
                Changed:= True;
            end;
    until not Changed;
end;

var
    Numbers: array [0 .. 9] of Integer;
    i: Integer;
begin
    Writeln('Please input 10 random numbers');
    for i:= 0 to High(Numbers) do
    begin
        Write('#', i + 1, ': ');
        Readln(Numbers[i]);
    end;
    BubbleSort(Numbers);
    Writeln;
    Writeln('Numbers after sort: ');
    for i:= 0 to High(Numbers) do
    begin
        Writeln(Numbers[i]);
    end;
    Write('Press enter key to close');
    Readln;
end.

보다 큰(>) 연산자를 보다 작은(<) 연산자로 바꾸어서 내림차순 정렬로 정렬 방식을 수정할 수 있습니다.

if X[i] > X[i + 1] then