خوارزميات الترتيب في لغة Pascal: الترتيب الفقاعي (Bubble Sort) وترتيب الإدراج (Insertion Sort) مع تمارين محلولة — الإعلام الآلي — الثانية ثانوي — المنهاج الجزائري

خوارزميات الترتيب في لغة Pascal: الترتيب الفقاعي (Bubble Sort) وترتيب الإدراج (Insertion Sort) مع تمارين محلولة

الأهداف التعليمية:

• فهم مفهوم ترتيب البيانات وأهميته في البرمجة
• دراسة آلية عمل خوارزمية الترتيب الفقاعي (Bubble Sort)
• دراسة آلية عمل خوارزمية ترتيب الإدراج (Insertion Sort)
• مقارنة بين خوارزميات الترتيب من حيث الكفاءة
• تنفيذ الخوارزميات بلغة Pascal

1. تمهيد

تعتبر عمليات ترتيب البيانات من أهم العمليات في علوم الحاسوب. ففي التطبيقات العملية، نحتاج دائماً إلى ترتيب القوائم والأسطر والمعلومات لتسهيل البحث والوصول إليها. هناك عدة خوارزميات للترتيب، تختلف في كفاءتها وسرعتها وطريقة عملها. سنتناول في هذا الدرس أشهر خوارزميتين: الترتيب الفقاعي وترتيب الإدراج.

2. مفهوم ترتيب البيانات

3. الترتيب الفقاعي (Bubble Sort)

المبدأ: سميت بهذا الاسم لأن العناصر الكبيرة “تطفو” إلى الأعلى مثل الفقاعات. تقوم الخوارزمية بمقارنة كل عنصر مع العنصر الذي يليه، وتقوم بتبديلهما إذا كانا غير مرتبين، وتكرر هذه العملية حتى تصبح القائمة مرتبة.

الخوارزمية:

الإجراء BubbleSort (مصفوفة T من N عنصر):
   لكل i من 0 إلى N-2:
      لكل j من 0 إلى N-2-i:
         إذا كان T[j] > T[j+1]:
            بدل (T[j], T[j+1])
      نهاية لكل
   نهاية لكل
نهاية الإجراء

التنفيذ بلغة Pascal:

Procedure BubbleSort(Var T: Tab; N: Integer);
Var
  i, j, temp: Integer;
Begin
  For i := 0 To N-2 Do
    For j := 0 To N-2-i Do
      If T[j] > T[j+1] Then
      Begin
        temp := T[j];
        T[j] := T[j+1];
        T[j+1] := temp;
      End;
End;

4. ترتيب الإدراج (Insertion Sort)

المبدأ: تشبه طريقة ترتيب البطاقات في اليد. نأخذ كل عنصر بدوره وندرج (نضع) في المكان المناسب بين العناصر المرتبة السابقة له. تفترض الخوارزمية أن العنصر الأول مرتب، ثم تبدأ بإدراج العناصر المتبقية في مواضعها الصحيحة.

الخوارزمية:

الإجراء InsertionSort (مصفوفة T من N عنصر):
   لكل i من 1 إلى N-1:
      القيمة_الحالية := T[i]
      j := i - 1
      طالما (j >= 0) و (T[j] > القيمة_الحالية):
         T[j+1] := T[j]
         j := j - 1
      نهاية طالما
      T[j+1] := القيمة_الحالية
   نهاية لكل
نهاية الإجراء

التنفيذ بلغة Pascal:

Procedure InsertionSort(Var T: Tab; N: Integer);
Var
  i, j, valeur: Integer;
Begin
  For i := 1 To N-1 Do
  Begin
    valeur := T[i];
    j := i - 1;
    While (j >= 0) And (T[j] > valeur) Do
    Begin
      T[j+1] := T[j];
      j := j - 1;
    End;
    T[j+1] := valeur;
  End;
End;

5. مقارنة بين الخوارزميتين

6. تمارين محلولة

التمرين 1: طبق خوارزمية الترتيب الفقاعي على المصفوفة التالية: [8, 3, 5, 1, 9] خطوة بخطوة.

الحل:

البداية: [8, 3, 5, 1, 9]
الممر 1: [3, 5, 1, 8, 9]  ← قورن 8>3 ← بدل، 8>5 ← بدل، 8>1 ← بدل، 8<9 ← لا تبديل
الممر 2: [3, 1, 5, 8, 9]  ← 3<5 ← لا بدل، 5>1 ← بدل، 5<8 ← لا بدل
الممر 3: [1, 3, 5, 8, 9]  ← 3>1 ← بدل، 3<5 ← لا بدل
الممر 4: [1, 3, 5, 8, 9]  ← 1<3 ← لا بدل
النتيجة: [1, 3, 5, 8, 9] ✅ مرتبة تصاعدياً

التمرين 2: كم عدد المقارنات التي تجريها خوارزمية Bubble Sort لمصفوفة من 10 عناصر في أسوأ حالة؟

الحل: عدد المقارنات = (N-1) + (N-2) + ... + 1 = N(N-1)/2
عدد المقارنات = 10 × 9 / 2 = 45 مقارنة

التمرين 3: اكتب برنامجاً كاملاً بلغة Pascal يعرّف مصفوفة من 7 أعداد صحيحة يدخلها المستخدم، ثم يرتبها تصاعدياً باستخدام Insertion Sort ويطبع النتيجة.

الحل:

Program TriInsertion;
Const
  N = 7;
Type
  Tab = Array[1..N] Of Integer;
Var
  T: Tab;
  i: Integer;

Procedure InsertionSort(Var T: Tab);
Var
  i, j, valeur: Integer;
Begin
  For i := 2 To N Do
  Begin
    valeur := T[i];
    j := i - 1;
    While (j >= 1) And (T[j] > valeur) Do
    Begin
      T[j+1] := T[j];
      j := j - 1;
    End;
    T[j+1] := valeur;
  End;
End;

Begin
  Writeln('أدخل ', N, ' أعداد:');
  For i := 1 To N Do Readln(T[i]);
  InsertionSort(T);
  Writeln('المصفوفة بعد الترتيب:');
  For i := 1 To N Do Write(T[i], ' ');
  Readln;
End.

7. خلاصة

دروس مشابهة:

• خوارزميات البحث: البحث التسلسلي والبحث الثنائي في Pascal — الثانية ثانوي — الإعلام الآلي
• هياكل التحكم في لغة Pascal (If, Case, For, While, Repeat) — الثانية ثانوي — الإعلام الآلي
• الخوارزميات وهياكل البيانات (مقدمة) — الثانية ثانوي — الإعلام الآلي