StartprogrammingusingObjectPascal:SortAlgorithmsComparison
Jump to navigation
Jump to search
정렬 알고리즘 비교
이 예제에서는 큰 크기의 정수 배열을 가지고 이 장에서 언급한 세 가지 정렬 알고리즘을 비교할 것입니다. 각각의 알고리즘에 대해 걸린 시간을 측정하겠습니다.
program SortComparison;
{$mode objfpc}{$H+}
uses
{$IFDEF UNIX}{$IFDEF UseCThreads}
cthreads,
{$ENDIF}{$ENDIF}
Classes, SysUtils;
// Bubble sort
procedure BubbleSort(var X: array of Integer);
var
Temp: Integer;
i: Integer;
Changed: Boolean;
begin
repeat
Changed:= False;
for i:= 0 to High(X) - 1 do
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;
// Selection Sort
procedure SelectionSort(var X: array of Integer);
var
i: Integer;
j: Integer;
SmallPos: Integer;
Smallest: Integer;
begin
for i:= 0 to High(X) -1 do // Outer loop
begin
SmallPos:= i;
Smallest:= X[SmallPos];
for j:= i + 1 to High(X) do // Inner loop
if X[j] < Smallest then
begin
SmallPos:= j;
Smallest:= X[SmallPos];
end;
X[SmallPos]:= X[i];
X[i]:= Smallest;
end;
end;
// Shell Sort
procedure ShellSort(var X: array of Integer);
var
Done: Boolean;
Jump, j, i: Integer;
Temp: Integer;
begin
Jump:= High(X);
while (Jump > 0) do // Outer loop
begin
Jump:= Jump div 2;
repeat // Intermediate loop
Done:= True;
for j:= 0 to High(X) - Jump do // Inner loop
begin
i:= j + Jump;
if X[j] > X[i] then // Swap
begin
Temp:= X[i];
X[i]:= X[j];
X[j]:= Temp;
Done:= False;
end;
end; // inner loop
until Done; // innermediate loop end
end; // outer loop end
end;
// Randomize Data
procedure RandomizeData(var X: array of Integer);
var
i: Integer;
begin
Randomize;
for i:= 0 to High(X) do
X[i]:= Random(10000000);
end;
var
Numbers: array [0 .. 59999] of Integer;
i: Integer;
StartTime: TDateTime;
begin
Writeln('----------------- Full random data');
RandomizeData(Numbers);
StartTime:= Now;
Writeln('Sorting.. Bubble');
BubbleSort(Numbers);
Writeln('Bubble sort tooks (mm:ss): ',
FormatDateTime('nn:ss', Now - StartTime));
Writeln;
RandomizeData(Numbers);
Writeln('Sorting.. Selection');
StartTime:= Now;
SelectionSort(Numbers);
Writeln('Selection sort tooks (mm:ss): ',
FormatDateTime('nn:ss', Now - StartTime));
Writeln;
RandomizeData(Numbers);
Writeln('Sorting.. Shell');
StartTime:= Now;
ShellSort(Numbers);
Writeln('Shell sort tooks (mm:ss): ',
FormatDateTime('nn:ss', Now - StartTime));
Writeln;
Writeln('----------------- Nearly sorted data');
Numbers[0]:= Random(10000);
Numbers[High(Numbers)]:= Random(10000);
StartTime:= Now;
Writeln('Sorting.. Bubble');
BubbleSort(Numbers);
Writeln('Bubble sort tooks (mm:ss): ',
FormatDateTime('nn:ss', Now - StartTime));
Writeln;
Numbers[0]:= Random(10000);
Numbers[High(Numbers)]:= Random(10000);
Writeln('Sorting.. Selection');
StartTime:= Now;
SelectionSort(Numbers);
Writeln('Selection sort tooks (mm:ss): ',
FormatDateTime('nn:ss', Now - StartTime));
Writeln;
Numbers[0]:= Random(10000);
Numbers[High(Numbers)]:= Random(10000);
Writeln('Sorting.. Shell');
StartTime:= Now;
ShellSort(Numbers);
Writeln('Shell sort tooks (mm:ss): ',
FormatDateTime('nn:ss', Now - StartTime));
Write('Press enter key to close');
Readln;
end.