Sắp xếp mảng là một thao tác thường được dùng rất nhiều trong các thuật toán như tìm kiếm nhị phân, tìm cặp gần nhất, tìm các giá trị lớn nhất, nhỏ nhất (ví dụ như các bài NHGA, CASO, LUTA, ...). Thuật toán đơn giản nhất để sắp xếp một mảng n phần tử là:
for i:=1 to n do
for j:=i+1 to n do
if(a[i]> a[j]) then swap(a[i],a[j]);
Thuật toán sắp xếp trên, cũng như một số thuật toán sắp xếp khác như SelectionSort, InsertionSort, BubbleSort có độ phức tạp là O(n2) - khoảng n(n+1)/2 bước thực hiện. Nếu n= 1.000 thì số bước thực hiện là 500.000, máy tính có thể thực hiện nhanh. Tuy nhiên, nếu n = 100.000 thì số bước thực hiện là 5.000.000.000, máy tính không thể thực hiện được trong khoảng vài giây.
Tuy nhiên có những thuật toán khác giúp cho việc sắp xếp có độ phức tạp O(nlog2n) như QuickSort, HeapSort, MergeSort. Nếu n = 100.000 thì số bước sắp xếp khoảng 1.700.000, máy tính hoàn toàn có thể thực hiện dưới 1 giây.
Trong Free Pascal, người ta cung cấp sẵn một chương trình mẫu trong thư mục C:\FPC\3.0.4\demo\text ta có thể tìm thấy file qsort.pp có sẵn thuật toán để sắp xếp mảng với độ phức tạp O(nlog2n). Ta có thể sử dụng lại chương trình sau cho phù hợp với nhu cầu của mình:
{QuickSort Example}
program quicksort;
const
max = 100000;
type
tlist = array[1..max] of longint;
var
data : tlist;
procedure qsort(var a : tlist);
procedure sort(l,r: longint);
var
i,j,x,y: longint;
begin
i:=l;
j:=r;
x:=a[(l+r) div 2];
repeat
while a[i]<x do
inc(i);
while x<a[j] do
dec(j);
if not(i>j) then
begin
y:=a[i];
a[i]:=a[j];
a[j]:=y;
inc(i);
j:=j-1;
end;
until i>j;
if l<j then
sort(l,j);
if i<r then
sort(i,r);
end;
begin
sort(1,max);
end;
var
i : longint;
begin
write('Creating ',Max,' random numbers between 1 and 500000');
randomize;
for i:=1 to max do
data[i]:=random(500000);
writeln;
writeln('Sorting...');
qsort(data);
writeln;
for i:=1 to max do
begin
write(data[i]:7);
if (i mod 10)=0 then
writeln;
end;
end.
