Onionmixer: SPOP 버블정렬알고리즘 페이지 추가

2012-07-26T10:44:28Z

SPOP 버블정렬알고리즘 페이지 추가

New page

===버블 정렬 알고리즘===

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

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

<syntaxhighlight lang="c">
7
10
2
5
6
3
</syntaxhighlight>

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

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

처음 한 바퀴를 돌고 나면 배열은 다음과 같이 될 것입니다.
<syntaxhighlight lang="c">
7
2
5
6
3
10
</syntaxhighlight>

두 번째 바퀴 다음순서
<syntaxhighlight lang="c">
2
5
6
3
7
10
</syntaxhighlight>

세 번째
<syntaxhighlight lang="c">
2
5
3
6
7
10
</syntaxhighlight>

네 번째
<syntaxhighlight lang="c">
2
3
5
6
7
10
</syntaxhighlight>

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

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

다음은 ''버블 정렬'' 프로그램입니다.
<syntaxhighlight lang="pascal">
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.
</syntaxhighlight>

보다 큰(>) 연산자를 보다 작은(<) 연산자로 바꾸어서 내림차순 정렬로 정렬 방식을 수정할 수 있습니다.
<syntaxhighlight lang="pascal">
if X[i] > X[i + 1] then
</syntaxhighlight>
[[Category:StartprogrammingusingObjectPascal]]

StartprogrammingusingObjectPascal:BubbleSortAlgorithm - Revision history

Onionmixer: SPOP 버블정렬알고리즘 페이지 추가