الرئيسية › الدروس › الفرز (Les tris)

دروس هذا الفصل

1. الـ tri à bulles
2. الـ tri par sélection
3. الـ tri par insertion

الدرس 14.1 : الـ tri à bulles

10 دقيقة

نفرزو tableau معناها نرتّبو عناصرو بالترتيب التصاعدي (من الأصغر للأكبر) ولا التنازلي. الـ tri à bulles يقارن كل عنصر مع جارو: كان موش في الترتيب الصحيح، نبدّلو بيناتهم. العناصر الكبار يطلعو للآخر كيما الـ bulles.

• نمرّو على الـ tableau ونبدّلو كل زوز موش مرتّبين T[i] > T[i + 1].
• متغيّر booléen echange يتفكّر كان صار تبديل واحد على الأقل.
• نعاودو ما دام صار تبديل: Répéter … Jusqu'à echange = Faux.

باش نبدّلو زوز خانات، نعدّيو بمتغيّر مساعد: aux ← T[i]، T[i] ← T[i + 1]، T[i + 1] ← aux.

نصيحة : في Python، Répéter تتكتب بـ while والمتغيّر echange نحطّوه True قبل الـ boucle. ما يلزمش break.

بـ Python

نقراو 5 أعداد، نفرزوهم بالـ tri à bulles، وبعد نكتبوهم واحد في كل سطر.

n = 5
t = [0] * n
for i in range(n):
    t[i] = int(input())
echange = True
while echange:
    echange = False
    for i in range(n - 1):
        if t[i] > t[i + 1]:
            aux = t[i]
            t[i] = t[i + 1]
            t[i + 1] = aux
            echange = True
for i in range(n):
    print(t[i])

بـ algorithme

نفس الفكرة في algorithme، بـ Répéter … Jusqu'à.

Algorithme TriBulles
Début
  n ← 5
  Pour i de 1 à n Faire
    Lire(T[i])
  FinPour
  Répéter
    echange ← Faux
    Pour i de 1 à n - 1 Faire
      Si T[i] > T[i + 1] Alors
        aux ← T[i]
        T[i] ← T[i + 1]
        T[i + 1] ← aux
        echange ← Vrai
      FinSi
    FinPour
  Jusqu'à echange = Faux
  Pour i de 1 à n Faire
    Ecrire(T[i])
  FinPour
Fin

TDO
Objet | Type/Nature
n, i, aux | Entier
T | Tableau de 5 Entiers
echange | Booléen

الدرس 14.2 : الـ tri par sélection

10 دقيقة

الـ tri par sélection يلوّج على أصغر عنصر في الـ tableau ويحطّو في أول بلاصة. وبعد يلوّج على الأصغر في اللي قعدو ويحطّو في البلاصة الثانية، وهكّا.

• لكل بلاصة i من الأولى لقبل الأخيرة:
• نلقاو البلاصة pmin متاع الأصغر بين i والآخر؛
• كان pmin ≠ i، نبدّلو T[i] و T[pmin].

نصيحة : مع n عناصر، ديما فما n − 1 دورات، وتبديل واحد على الأكثر في كل دورة.

انتبه : نتفكّرو البلاصة متاع الأصغر (pmin)، موش القيمة برك: وإلا ما نعرفوش أنهي خانة نبدّلو.

بـ Python

خمسة نقاط نقراوهم، نفرزوهم بالـ sélection، وبعد نكتبوهم.

n = 5
t = [0] * n
for i in range(n):
    t[i] = int(input())
for i in range(n - 1):
    pmin = i
    for j in range(i + 1, n):
        if t[j] < t[pmin]:
            pmin = j
    if pmin != i:
        aux = t[i]
        t[i] = t[pmin]
        t[pmin] = aux
for i in range(n):
    print(t[i])

بـ algorithme

زوز boucles Pour وحدة في وحدة: الأولى تحدّد البلاصة، والثانية تلوّج على الأصغر.

Algorithme TriSelection
Début
  n ← 5
  Pour i de 1 à n Faire
    Lire(T[i])
  FinPour
  Pour i de 1 à n - 1 Faire
    pmin ← i
    Pour j de i + 1 à n Faire
      Si T[j] < T[pmin] Alors
        pmin ← j
      FinSi
    FinPour
    Si pmin ≠ i Alors
      aux ← T[i]
      T[i] ← T[pmin]
      T[pmin] ← aux
    FinSi
  FinPour
  Pour i de 1 à n Faire
    Ecrire(T[i])
  FinPour
Fin

TDO
Objet | Type/Nature
n, i, j, pmin, aux | Entier
T | Tableau de 5 Entiers

الدرس 14.3 : الـ tri par insertion

11 دقيقة

الـ tri par insertion يعمل كيما اللي يلعب الكارطة: ياخو العناصر واحد بواحد ويدخّل كل واحد في بلاصتو بين اللي مرتّبين على اليسار متاعو.

• لـ i من البلاصة الثانية للأخيرة: نحفظو v ← T[i].
• ما دام العنصر على اليسار أكبر من v، نزحزحوه خانة لليمين.
• نحطّو v في الخانة اللي تفرغت.

انتبه : في الـ condition j > 1 et T[j - 1] > v، الـ test j > 1 يجي الأول: يتجنّب قراءة خانة قبل بداية الـ tableau.

نصيحة : الفرز هذا سريع كي الـ tableau يكون تقريبا مرتّب: الزحزحات قلال.

بـ Python

في Python الخانة الأولى هي 0، إذن الـ condition تولّي j > 0.

n = 5
t = [0] * n
for i in range(n):
    t[i] = int(input())
for i in range(1, n):
    v = t[i]
    j = i
    while j > 0 and t[j - 1] > v:
        t[j] = t[j - 1]
        j = j - 1
    t[j] = v
for i in range(n):
    print(t[i])

بـ algorithme

boucle Pour لكل عنصر، و boucle Tant que للزحزحات.

Algorithme TriInsertion
Début
  n ← 5
  Pour i de 1 à n Faire
    Lire(T[i])
  FinPour
  Pour i de 2 à n Faire
    v ← T[i]
    j ← i
    Tant que (j > 1) et (T[j - 1] > v) Faire
      T[j] ← T[j - 1]
      j ← j - 1
    FinTantQue
    T[j] ← v
  FinPour
  Pour i de 1 à n Faire
    Ecrire(T[i])
  FinPour
Fin

TDO
Objet | Type/Nature
n, i, j, v | Entier
T | Tableau de 5 Entiers

تدرّب مجانًا

كل درس فيه 3 تمارين مجانية مع تلميحات باش تطبّق الفصل هذا مع هنّيبوت.

← الفصل اللي قبل : الاختيار المتعدّد: Selon · الفصل اللي بعد : البحث في tableau →

كل الفصول · شوف فروض 2 تكنولوجيا المصلّحة

الدروس كتبناها لـ Mission Carthage على أساس البرنامج الرسمي. الأستاذ متاعك يبقى المرجع.