الرئيسية › الدروس › فرز Shell، الفرز بالعدّ، والدمج

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

1. فرز Shell
2. الفرز بالعدّ
3. دمج زوز جداول مرتّبين

الدرس 24.1 : فرز Shell

12 دقيقة

فرز Shell يحسّن الـ tri par insertion. الـ tri par insertion بطيء كي عنصر صغير يكون بعيد على اليمين: يتقدّم خانة بخانة. فرز Shell يعمل الأول إدخالات بين عناصر متباعدين بـ h خانات، وبعد يصغّر h حتى لـ 1. التعدية الأخيرة (h = 1) هي tri par insertion عادي، أما تقريبا كل شيء في بلاصتو من قبل.

• الخطوة الأولى: المتتالية h = 1، 4، 13، 40… (h ← 3 × h + 1) ما دام h < n.
• لكل h: tri par insertion نقارنو فيه T[j − h] عوض T[j − 1].
• وبعد h ← h div 3، حتى h = 1 محسوبة.

نصيحة : بـ h = 1، الـ boucle الداخلية هي بالضبط متاع الـ tri par insertion: فرز Shell هو insertion « محضّرة ».

بـ Python

فرز Shell لـ 8 أعداد مقرية.

n = 8
t = [0] * n
for i in range(n):
    t[i] = int(input())
h = 1
while h < n:
    h = 3 * h + 1
while h > 1:
    h = h // 3
    for i in range(h, n):
        v = t[i]
        j = i
        while j >= h and t[j - h] > v:
            t[j] = t[j - h]
            j = j - h
        t[j] = v
for i in range(n):
    print(t[i])

بـ algorithme

بـ indices من 1 لـ n، الـ condition تولّي j > h.

Algorithme TriShell
Début
  n ← 8
  Pour i de 1 à n Faire
    Lire(T[i])
  FinPour
  h ← 1
  Tant que h < n Faire
    h ← 3 * h + 1
  FinTantQue
  Tant que h > 1 Faire
    h ← h div 3
    Pour i de h + 1 à n Faire
      v ← T[i]
      j ← i
      Tant que (j > h) et (T[j - h] > v) Faire
        T[j] ← T[j - h]
        j ← j - h
      FinTantQue
      T[j] ← v
    FinPour
  FinTantQue
  Pour i de 1 à n Faire
    Ecrire(T[i])
  FinPour
Fin

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

الدرس 24.2 : الفرز بالعدّ

10 دقيقة

كي تكون القيم أعداد صحيحة في مجال صغير (نقاط من 0 لـ 20)، نجمو نفرزو من غير مقارنة: نعدّو قدّاش من مرّة تظهر كل قيمة، وبعد نعاودو نكتبو الـ tableau بترتيب القيم.

• tableau nb فيه 21 خانة بـ 0: nb[v] تعدّ النقاط اللي تساوي v.
• وبعد لـ v من 0 لـ 20: نكتبو v، nb[v] مرّات.

انتبه : الفرز هذا يخدم كان لأعداد صحيحة في مجال معروف وموش كبير برشا: للـ réels ولا الأسامي، يلزم فرز آخر.

بـ Python

نفرزو 8 نقاط صحيحة (0 لـ 20) بالعدّ.

n = 8
t = [0] * n
for i in range(n):
    t[i] = int(input())
nb = [0] * 21
for i in range(n):
    nb[t[i]] = nb[t[i]] + 1
k = 0
for v in range(21):
    for c in range(nb[v]):
        t[k] = v
        k = k + 1
for i in range(n):
    print(t[i])

بـ algorithme

في الـ algorithme، الـ tableau NB يمشي من 0 لـ 20: نعرّفوه بـ 21 خانة ونزحزحو بـ 1.

Algorithme TriComptage
Début
  n ← 8
  Pour i de 1 à n Faire
    Lire(T[i])
  FinPour
  Pour v de 1 à 21 Faire
    NB[v] ← 0
  FinPour
  Pour i de 1 à n Faire
    NB[T[i] + 1] ← NB[T[i] + 1] + 1
  FinPour
  k ← 1
  Pour v de 0 à 20 Faire
    Pour c de 1 à NB[v + 1] Faire
      T[k] ← v
      k ← k + 1
    FinPour
  FinPour
  Pour i de 1 à n Faire
    Ecrire(T[i])
  FinPour
Fin

TDO
Objet | Type/Nature
T | Tableau de 8 Entiers
NB | Tableau de 21 Entiers
n, i, v, c, k | Entier

الدرس 24.3 : دمج زوز جداول مرتّبين

11 دقيقة

زوز tableaux A و B مرتّبين من قبل. باش نلقاو tableau C مرتّب فيه العناصر الكل، ما يلزمش نعاودو نفرزو كل شيء: نتقدّمو في الزوز tableaux في نفس الوقت وكل مرّة ناخذو الأصغر من العنصرين اللي في الراس.

• ثلاثة indices: i في A، j في B، k في C.
• ما دام الزوز tableaux فيهم عناصر: ننسخو الأصغر ونقدّمو الـ indice متاعو.
• وبعد ننسخو اللي قعد في واحد من الزوز tableaux.

نصيحة : الدمج يمرّ على كل عنصر مرّة وحدة: أسرع برشا من فرز جديد.

بـ Python

دمج زوز listes مرتّبين معطيين.

A = [2, 7, 11, 20]
B = [3, 5, 12, 18, 25]
na = 4
nb = 5
C = [0] * (na + nb)
i = 0
j = 0
k = 0
while i < na and j < nb:
    if A[i] <= B[j]:
        C[k] = A[i]
        i = i + 1
    else:
        C[k] = B[j]
        j = j + 1
    k = k + 1
while i < na:
    C[k] = A[i]
    i = i + 1
    k = k + 1
while j < nb:
    C[k] = B[j]
    j = j + 1
    k = k + 1
for k in range(na + nb):
    print(C[k])

بـ algorithme

الثلاثة boucles Tant que: الدمج، وبعد اللي قعد من A ومن B.

Algorithme Fusion
Début
  A[1] ← 2
  A[2] ← 7
  A[3] ← 11
  A[4] ← 20
  B[1] ← 3
  B[2] ← 5
  B[3] ← 12
  B[4] ← 18
  B[5] ← 25
  na ← 4
  nb ← 5
  i ← 1
  j ← 1
  k ← 1
  Tant que (i ≤ na) et (j ≤ nb) Faire
    Si A[i] ≤ B[j] Alors
      C[k] ← A[i]
      i ← i + 1
    Sinon
      C[k] ← B[j]
      j ← j + 1
    FinSi
    k ← k + 1
  FinTantQue
  Tant que i ≤ na Faire
    C[k] ← A[i]
    i ← i + 1
    k ← k + 1
  FinTantQue
  Tant que j ≤ nb Faire
    C[k] ← B[j]
    j ← j + 1
    k ← k + 1
  FinTantQue
  Pour k de 1 à na + nb Faire
    Ecrire(C[k])
  FinPour
Fin

TDO
Objet | Type/Nature
A | Tableau de 4 Entiers
B | Tableau de 5 Entiers
C | Tableau de 9 Entiers
na, nb, i, j, k | Entier

تدرّب مجانًا

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

← الفصل اللي قبل : الملفات (Fichiers) · الفصل اللي بعد : JavaScript: الأساسيات →

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

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