مرتب‌سازی و جستجو

الگوریتم‌های کلاسیک علوم کامپیوتر

مرتب‌سازی و جستجو دو مسئله بنیادی‌اند. بیایید سه الگوریتم معروف را با پاسکال بنویسیم!

۱. جستجوی خطی (Linear Search)

از اول تا آخر آرایه را بگرد و مقایسه کن — ساده اما برای آرایه‌های بزرگ کند:

function LinearSearch(const a: array of integer; target: integer): integer;
var
  i: integer;
begin
  Result := -1;   { پیدا نشد }
  for i := 0 to high(a) do
    if a[i] = target then
    begin
      Result := i;
      break;
    end;
end;

۲. جستجوی دودویی (Binary Search)

فقط روی آرایه مرتب! هر بار ناحیه جستجو را نصف می‌کند — فوق‌العاده سریع:

function BinarySearch(const a: array of integer; target: integer): integer;
var
  lo, hi, mid: integer;
begin
  lo := 0;
  hi := high(a);
  Result := -1;
  while lo <= hi do
  begin
    mid := (lo + hi) div 2;
    if a[mid] = target then
    begin
      Result := mid;
      break;
    end
    else if a[mid] < target then
      lo := mid + 1
    else
      hi := mid - 1;
  end;
end;

۳. مرتب‌سازی حبابی (Bubble Sort)

عناصر مجاور را مقایسه و در صورت نیاز جابجا کنید — بزرگ‌ها مثل حباب به آخر می‌روند:

procedure BubbleSort(var a: array of integer);
var
  i, j, temp: integer;
begin
  for i := 0 to high(a) - 1 do
    for j := 0 to high(a) - 1 - i do
      if a[j] > a[j + 1] then
      begin
        temp := a[j];
        a[j] := a[j + 1];
        a[j + 1] := temp;
      end;
end;

مثال کامل

program SortSearch;
const
  N = 8;
var
  data: array[1..N] of integer;
  i, idx: integer;

procedure PrintArray;
var i: integer;
begin
  for i := 1 to N do
    write(data[i]:4);
  writeln;
end;

begin
  { داده نامرتب }
  data[1] := 42; data[2] := 7; data[3] := 99; data[4] := 13;
  data[5] := 55; data[6] := 1; data[7] := 68; data[8] := 25;

  writeln('Before: ');
  PrintArray;

  { مرتب‌سازی حبابی روی data }
  { ... کد بالا }

  writeln('After: ');
  PrintArray;
end.

پیچیدگی — چقدر سریع؟

خلاصه

• خطی: همه‌جا کار می‌کند، ساده، O(n)
• دودویی: فقط آرایه مرتب، فوق‌سریع، O(log n)
• حبابی: ساده برای یادگیری، کند برای بزرگ، O(n²)