خوارزمية فرز الإدراج باستخدام لغة C، C++, Java, Python أمثلة

ما هو فرز الإدراج؟

يُعد فرز الإدراج أحد خوارزميات فرز المقارنة المستخدمة لفرز العناصر عن طريق التكرار على عنصر واحد في كل مرة ووضع العنصر في موضعه الصحيح داخل منطقة مرتبة بالفعل.

يُضاف كل عنصر بالتتابع إلى قائمة مُرتبة مسبقًا. حجم القائمة المُرتبة مسبقًا هو واحد في البداية. تضمن خوارزمية فرز الإدراج أن تكون العناصر k الأولى مُرتبة بعد التكرار k للحلقة الخارجية.

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

خصائص خوارزمية فرز الإدراج

تتميز خوارزمية فرز الإدراج بالخصائص المهمة التالية التي تفسر سلوكها في أحمال العمل الحقيقية:

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

مع وضع هذه السمات في الاعتبار، يشرح القسم التالي عملية الإدخال الأساسية التي تدعم كل دورة من دورات الخوارزمية.

كيف يتم إدراج Operaالعمل نشوئها؟

في خوارزمية فرز الإدراج، تُستخدم عملية الإدراج لفرز العناصر غير المرتبة. فهي تساعد على إدراج عنصر جديد في قائمة مرتبة مسبقًا مع الحفاظ على الترتيب الحالي للمنطقة المرتبة.

الشفرة الزائفة لعملية الإدراج:

النظر في قائمة A من العناصر N.

// Insert A[N-1] into sorted sublist A[0..N-2]
for i = N-1 to 1:
    if A[i] < A[i-1], then swap A[i] and A[i-1]
    else stop

في المثال أعلاه، يتم إدراج عنصر جديد رقم 6 في قائمة مرتبة مسبقًا. الخطوات التالية trace الحلقة الداخلية بينما ينتقل العنصر الجديد إلى اليسار نحو موضعه الصحيح.

الخطوة 1) بالمقارنة مع العنصر المجاور الأيسر لـ A[5]، 9 > 6، نقوم بتبديل الموضع 9 و6. الآن يتم نقل العنصر 6 إلى A[4].

الخطوة 2) الآن، نقارن A[4] و A[3]، ونجد أن A[3] > A[4]، لذلك نقوم مرة أخرى بتبديل موضع 6 و 8.

الخطوة 3) والآن قارن بين A[3] و A[2]. بما أن A[2] > A[3]، فإننا نبدل موضع الرقمين 7 و 6.

الخطوة 4) نقارن A[1] و A[2]. بما أن A[1] < A[2]، فإن العنصر المجاور الأيسر لم يعد أكبر. نستنتج أن 6 قد أُدخل بشكل صحيح، ونوقف الحلقة الداخلية هنا.

كيف يعمل فرز الإدراج

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

يوضح الشكل أعلاه آلية عمل خوارزمية فرز الإدراج في بنية البيانات. في البداية، يوجد عنصر واحد فقط في القائمة الفرعية المرتبة، أي 4. بعد إدراج العنصر A[1]، أي 3، يزداد حجم القائمة الفرعية المرتبة إلى 2، وتستمر الخوارزمية في هذا النمط حتى يتم وضع جميع العناصر.

بعد وضع التدفق المفاهيمي، توضح الأقسام التالية تطبيقات عملية في C++، ج، و Python حتى تتمكن من مقارنة هياكل الحلقات عبر اللغات المختلفة.

C++ برنامج لفرز الإدراج

استخدم C++ يستخدم التنفيذ أدناه حلقتين متداخلتين: تقوم الحلقة الخارجية بتحديد العنصر غير المصنف التالي، وتقوم الحلقة الداخلية بتحريكه إلى اليسار حتى يتم العثور على الموضع الصحيح.

#include <iostream>
using namespace std;

int main(){
    //unsorted list
    int unsorted[] = {9,8,7,6,5,4,3,3,2,1};

    //size of list
    int size_unsorted = sizeof(unsorted) / sizeof(unsorted[0]);

    //printing unsorted list
    cout << "\nUnsorted: ";
    for(int i = 0 ; i < size_unsorted ; i++){
        cout << unsorted[i] << " ";
    }

    int current_element,temp;

    for(int i = 1; i < size_unsorted; i++){
        current_element = unsorted[i];
        for(int j = i-1; j >= 0 && unsorted[j] > current_element; j--){
            //swapping if current element is lesser
            temp = unsorted[j+1];
            unsorted[j+1] = unsorted[j];
            unsorted[j] = temp;
        }
    }

    //printing sorted list
    cout << "\nSorted: ";
    for(int i = 0 ; i < size_unsorted ; i++){
        cout << unsorted[i] << " ";
    }

    return 0;
}

الإخراج:

Unsorted: 9 8 7 6 5 4 3 3 2 1
Sorted: 1 2 3 3 4 5 6 7 8 9

C Code لفرز الإدراج

وينطبق المنطق نفسه مباشرة على لغة C. المعيار printf تستدعي هذه العملية مخرجات التدفق، لكن نمط التبديل داخل الحلقة الداخلية مطابق لـ C++ الإصدار.

#include <stdio.h>
int main() {
    //unsorted list
    int unsorted[] = {9,8,7,6,5,4,3,3,2,1};

    //size of list
    int size_unsorted = sizeof(unsorted) / sizeof(unsorted[0]);

    //printing unsorted list
    printf("\nUnsorted: ");
    for(int i = 0 ; i < size_unsorted ; i++){
        printf("%d ", unsorted[i]);
    }

    int current_element, temp;

    for(int i = 1; i < size_unsorted; i++){
        current_element = unsorted[i];
        for(int j = i-1; j >= 0 && unsorted[j] > current_element; j--){
            //swapping if current element is lesser
            temp = unsorted[j+1];
            unsorted[j+1] = unsorted[j];
            unsorted[j] = temp;
        }
    }

    //printing sorted list
    printf("\nSorted: ");
    for(int i = 0 ; i < size_unsorted ; i++){
        printf("%d ", unsorted[i]);
    }

    return 0;
}

الإخراج:

Output:
Unsorted: 9 8 7 6 5 4 3 3 2 1
Sorted: 1 2 3 3 4 5 6 7 8 9

Python برنامج لفرز الإدراج

Python يدعم تبديل الصفوفping في تعبير واحد، لذا فإن الحلقة الداخلية أكثر إيجازًا من حلقتها الأصلية. C++ نظائر مع الحفاظ على نفس السلوك الخوارزمي.

#unsorted list
unsorted = [9,8,7,6,5,4,3,3,2,1]

#size of list
size_unsorted = len(unsorted)

#printing unsorted list
print("\nUnsorted: ", end="")
for i in range(size_unsorted):
    print(unsorted[i], end=" ")

for i in range(1, size_unsorted):
    current_element = unsorted[i]
    j = i - 1
    while j >= 0 and unsorted[j] > current_element:
        #swapping if current element is lesser
        unsorted[j+1], unsorted[j] = unsorted[j], unsorted[j+1]
        j -= 1

#printing sorted list
print("\nSorted: ", end="")
for i in range(size_unsorted):
    print(unsorted[i], end=" ")

الإخراج:

Unsorted: 9 8 7 6 5 4 3 3 2 1
Sorted: 1 2 3 3 4 5 6 7 8 9

خصائص فرز الإدراج

فيما يلي خصائص مهمة لخوارزمية فرز الإدراج تساعدك على تحديد متى تكون الأداة المناسبة:

• عبر الانترنت: تستطيع خوارزمية فرز الإدراج فرز العناصر فور استلامها. فإذا كنا قد فرزنا قائمة من العناصر مسبقًا وأضفنا إليها عناصر أخرى، فلا داعي لإعادة تنفيذ عملية الفرز بالكامل، بل نكتفي بتكرار العملية على العناصر المضافة حديثًا.
• في المكان: تتميز خوارزمية فرز الإدراج بتعقيد مكاني ثابت ولا تتطلب مساحة إضافية. تقوم هذه الخوارزمية بفرز العناصر في مكانها.
• مستقر: في خوارزمية فرز الإدراج، لا نبدل العناصر إذا كانت قيمها متساوية. على سبيل المثال، إذا كان العنصران x و y متساويين، وكان x يظهر قبل y في القائمة غير المرتبة، فسيظل x يظهر قبل y في القائمة المرتبة. وهذا ما يجعل خوارزمية فرز الإدراج مستقرة.
• تكيفي: A خوارزمية الفرز تُعتبر خوارزمية فرز الإدراج تكيفية إذا استغرقت وقتًا أقل عندما تكون عناصر الإدخال أو مجموعة فرعية منها مُرتبة مسبقًا. وكما ذكرنا سابقًا، فإن أفضل وقت تشغيل لها هو O(N)، وأسوأ وقت تشغيل هو O(N²). تُعدّ خوارزمية فرز الإدراج إحدى خوارزميات الفرز التكيفية.

تعقيد فرز الإدراج

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

تعقيد الفضاء

لا تتطلب خوارزمية فرز الإدراج مساحة إضافية لفرز العناصر. فتعقيد المساحة ثابت، أي O(1)، لأنه لا يتم استخدام سوى عدد قليل من المتغيرات المؤقتة بغض النظر عن حجم المدخلات.

تعقيد الوقت

بما أن خوارزمية فرز الإدراج تُكرر العملية على عنصر واحد في كل مرة، فإنها تتطلب N-1 دورة لفرز N عنصرًا. في كل دورة، قد لا تُجري أي تبديلات إذا كانت العناصر مُرتبة بالفعل، أو قد تحتاج إلى العديد من التبديلات إذا كانت العناصر مُرتبة تنازليًا.

• بالنسبة للتمرير 1، الحد الأدنى المطلوب للمقايضات هو صفر، والحد الأقصى للمقايضات المطلوبة هو 1.
• بالنسبة للتمرير 2، الحد الأدنى المطلوب للمقايضات هو صفر، والحد الأقصى للمقايضات المطلوبة هو 2.
• بالنسبة للتمرير N، الحد الأدنى المطلوب للمبادلة هو صفر، والحد الأقصى للمبادلة المطلوبة هو N.
• الحد الأدنى للتبديل هو صفر، وبالتالي فإن أفضل تعقيد زمني هو O(N) لتكرار N تمريرة.
• إجمالي عمليات التبديل القصوى هو (1+2+3+4+…+N) أي N(N+1)/2، لذا فإن أسوأ تعقيد زمني هو O(N^2).

فيما يلي أهم تعقيد زمني لخوارزمية فرز الإدراج:

• أسوأ حالة تعقيدO(n^2): فرز مصفوفة بترتيب تنازلي عندما يكون المطلوب ترتيبها تصاعديًا هو أسوأ سيناريو.
• أفضل تعقيد للحالة: O(n): أفضل حالة تحدث عندما تكون المصفوفة مرتبة بالفعل؛ حيث تُنفَّذ الحلقة الخارجية n مرة، بينما لا تُنفَّذ الحلقة الداخلية على الإطلاق. يوجد n مقارنة فقط، لذا فإن التعقيد خطي.
• متوسط ​​تعقيد الحالة: O(n^2): يحدث هذا عندما تظهر عناصر المصفوفة بترتيب عشوائي ليس تصاعديًا ولا تنازليًا.

الأسئلة الشائعة