فرز التحديد: شرح الخوارزمية باستخدام Python مثال رمز

ما هو فرز التحديد؟

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

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

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

كيف يعمل فرز التحديد؟

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

مثال

• على سبيل المثال، إذا كان فهرس القيمة الدنيا هو 3، فسيتم وضع قيمة العنصر ذو الفهرس 3 في الفهرس 0 بينما القيمة التي كانت في الفهرس 0 يتم وضعها في الفهرس 3. إذا كان العنصر الأول في القسم غير المصنف هو الحد الأدنى للقيمة، ثم تقوم بإرجاع مواقعها.
• يتم بعد ذلك نقل العنصر الذي تم تحديده باعتباره الحد الأدنى للقيمة إلى القسم الموجود على الجانب الأيسر، وهو القائمة التي تم فرزها.
• يحتوي الجانب المقسم الآن على عنصر واحد، بينما يحتوي الجانب غير المقسم على عناصر (n - 1) حيث n هو إجمالي عدد العناصر في القائمة. تتكرر هذه العملية مرارًا وتكرارًا حتى تتم مقارنة جميع العناصر وفرزها بناءً على قيمها.

تعريف المشكلة

يجب فرز قائمة العناصر التي توجد في ترتيب عشوائي بترتيب تصاعدي. فكر في القائمة التالية كمثال.

[21,6,9,33,3]

ينبغي فرز القائمة أعلاه لإنتاج النتائج التالية

[3,6,9,21,33]

الحل (الخوارزمية)

الخطوة 1) احصل على قيمة n التي تمثل الحجم الإجمالي للمصفوفة

الخطوة 2) تقسيم القائمة إلى أقسام مرتبة وغير مرتبة. يكون القسم الذي تم فرزه فارغًا في البداية بينما يحتوي القسم الذي لم يتم فرزه على القائمة بأكملها

الخطوة 3) اختر الحد الأدنى للقيمة من القسم غير المقسم ووضعه في القسم المفرز.

الخطوة 4) كرر العملية (ن – 1) مرات حتى يتم فرز كافة العناصر الموجودة في القائمة.

التمثيل المرئي

بالنظر إلى قائمة مكونة من خمسة عناصر، توضح الصور التالية كيفية تكرار خوارزمية فرز التحديد عبر القيم عند فرزها.

الصورة التالية توضح القائمة غير المفرزة

الخطوة 1)

تتم مقارنة القيمة الأولى 21 مع بقية القيم للتحقق مما إذا كانت هي القيمة الدنيا.

3 هو الحد الأدنى للقيمة، لذلك يتم تبديل المواضع 21 و 3. تمثل القيم ذات الخلفية الخضراء القسم المفرز من القائمة.

الخطوة 2)

تتم مقارنة القيمة 6 وهي العنصر الأول في القسم غير المصنف مع باقي القيم لمعرفة ما إذا كانت هناك قيمة أقل

القيمة 6 هي القيمة الدنيا، لذا فهي تحافظ على مكانتها.

الخطوة 3)

تتم مقارنة العنصر الأول من القائمة غير المصنفة بقيمة 9 مع بقية القيم للتحقق مما إذا كان يمثل الحد الأدنى للقيمة.

القيمة 9 هي القيمة الدنيا، لذا فهي تحافظ على مكانها في القسم المفرز.

الخطوة 4)

وتتم مقارنة القيمة 33 مع باقي القيم.

القيمة 21 أقل من 33، لذلك يتم تبديل المواضع لإنتاج القائمة الجديدة أعلاه.

الخطوة 5)

لدينا قيمة واحدة فقط متبقية في القائمة غير المقسمة. ولذلك، تم فرزها بالفعل.

القائمة النهائية هي مثل تلك الموضحة في الصورة أعلاه.

اختيار فرز البرنامج باستخدام Python 3

يُظهر الكود التالي تنفيذ فرز الاختيار باستخدام Python 3

def selectionSort( itemsList ):
    n = len( itemsList )
    for i in range( n - 1 ): 
        minValueIndex = i

        for j in range( i + 1, n ):
            if itemsList[j] < itemsList[minValueIndex] :
                minValueIndex = j

        if minValueIndex != i :
            temp = itemsList[i]
            itemsList[i] = itemsList[minValueIndex]
            itemsList[minValueIndex] = temp

    return itemsList


el = [21,6,9,33,3]

print(selectionSort(el))

يؤدي تشغيل الكود أعلاه إلى النتائج التالية

[3, 6, 9, 21, 33]

شرح الكود

شرح الكود هو كما يلي

إليك شرح الكود:

1. يحدد وظيفة تسمى التحديدالفرز
2. الحصول على العدد الإجمالي للعناصر في القائمة. نحتاج إلى ذلك لتحديد عدد التمريرات التي يجب إجراؤها عند مقارنة القيم.
3. الحلقة الخارجية. يستخدم الحلقة للتكرار عبر قيم القائمة. عدد التكرارات هو (ن – 1). قيمة n هي 5، لذا (5 - 1) تعطينا 4. وهذا يعني أنه سيتم تنفيذ التكرارات الخارجية 4 مرات. في كل تكرار، يتم تعيين قيمة المتغير i للمتغير minValueIndex
4. الحلقة الداخلية. يستخدم الحلقة لمقارنة القيمة الموجودة في أقصى اليسار بالقيم الأخرى الموجودة على الجانب الأيمن. ومع ذلك، فإن قيمة j لا تبدأ عند الفهرس 0. بل تبدأ عند (i + 1). وهذا يستبعد القيم التي تم فرزها بالفعل بحيث نركز على العناصر التي لم يتم فرزها بعد.
5. يبحث عن الحد الأدنى للقيمة في القائمة غير المصنفة ويضعها في موضعها الصحيح
6. يقوم بتحديث قيمة minValueIndex عندما يكون شرط المبادلة صحيحًا
7. يقارن قيم أرقام الفهرس minValueIndex و i لمعرفة ما إذا كانت غير متساوية
8. يتم تخزين القيمة الموجودة في أقصى اليسار في متغير زمني
9. القيمة السفلية من الجانب الأيمن تأخذ المركز الأول
10. يتم تخزين القيمة التي تم تخزينها في القيمة الزمنية في الموضع الذي كان يحتفظ به سابقًا بالحد الأدنى للقيمة
11. إرجاع القائمة التي تم فرزها كنتيجة للوظيفة
12. إنشاء قائمة تحتوي على أرقام عشوائية
13. قم بطباعة القائمة التي تم فرزها بعد استدعاء وظيفة الفرز المحددة وتمرير el كمعلمة.

تعقيد الوقت لفرز الاختيار

يتم استخدام تعقيد الفرز للتعبير عن عدد مرات التنفيذ التي يستغرقها فرز القائمة. يتضمن التنفيذ حلقتين.

يتم تنفيذ الحلقة الخارجية التي تختار القيم واحدًا تلو الآخر من القائمة n مرات حيث n هو إجمالي عدد القيم في القائمة.

يتم تنفيذ الحلقة الداخلية، التي تقارن القيمة من الحلقة الخارجية مع بقية القيم، أيضًا n مرة حيث n هو العدد الإجمالي للعناصر في القائمة.

ولذلك، فإن عدد عمليات التنفيذ هو (n * n)، والذي يمكن التعبير عنه أيضًا بـ O(n²).

يتضمن فرز الاختيار ثلاث فئات من التعقيد وهي:

• الحالة الأسوأ - هذا هو المكان الذي تكون فيه القائمة المقدمة بترتيب تنازلي. تنفذ الخوارزمية الحد الأقصى لعدد عمليات التنفيذ التي يتم التعبير عنها بـ [Big-O] O(n²)
• افضل حالة – يحدث هذا عندما تكون القائمة المقدمة مرتبة بالفعل. تقوم الخوارزمية بتنفيذ الحد الأدنى لعدد عمليات التنفيذ والتي يتم التعبير عنها بـ [Big-Omega] ?(n²)
• حالة متوسطة – يحدث هذا عندما تكون القائمة مرتبة بشكل عشوائي. يتم التعبير عن متوسط ​​التعقيد على أنه [Big-theta] ?(n²)

تتمتع عملية الفرز الانتقائي بتعقيد مكاني يبلغ O(1) حيث تتطلب متغيرًا زمنيًا واحدًا يستخدم لتبادل القيم.

متى يتم استخدام فرز التحديد؟

من الأفضل استخدام فرز التحديد عندما تريد:

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

مزايا فرز التحديد

وفيما يلي مزايا فرز الاختيار

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

مساوئ فرز الاختيار

وفيما يلي عيوب الفرز الاختياري.

• يكون أداؤه سيئًا عند العمل على قوائم ضخمة.
• عدد التكرارات التي تم إجراؤها أثناء الفرز هو n-squared، حيث n هو إجمالي عدد العناصر في القائمة.
• تتمتع الخوارزميات الأخرى، مثل الفرز السريع، بأداء أفضل مقارنة بالفرز بالتحديد.

الملخص

• الفرز الانتقائي هو خوارزمية مقارنة في المكان تُستخدم لفرز قائمة عشوائية إلى قائمة مرتبة. ولديها تعقيد زمني يبلغ O(n)²)
• وتنقسم القائمة إلى قسمين، مرتبة وغير مرتبة. يتم اختيار الحد الأدنى للقيمة من القسم الذي لم يتم فرزه ووضعه في القسم الذي تم فرزه.
• يتكرر هذا الشيء حتى يتم فرز جميع العناصر.
• تنفيذ الكود الزائف في Python 3 يتضمن استخدام حلقتين for وعبارات if للتحقق مما إذا كان التبديل ضروريًا
• تقيس تعقيد الوقت عدد الخطوات المطلوبة لفرز القائمة.
• يحدث أسوأ تعقيد زمني عندما تكون القائمة بترتيب تنازلي. ولديها تعقيد زمني [Big-O] O(n)²)
• تحدث أفضل حالة تعقيد زمني عندما تكون القائمة بالفعل في ترتيب تصاعدي. ولديها تعقيد زمني [Big-Omega] ?(n²)
• يحدث تعقيد الوقت للحالة المتوسطة عندما تكون القائمة مرتبة بشكل عشوائي. ولها تعقيد زمني [Big-theta] ?(n²)
• من الأفضل استخدام فرز التحديد عندما يكون لديك قائمة صغيرة من العناصر المطلوب فرزها، ولا تهم تكلفة تبديل القيم، ويكون التحقق من جميع القيم إلزاميًا.
• لا يؤدي فرز التحديد أداءً جيدًا في القوائم الضخمة
• تتمتع خوارزميات الفرز الأخرى، مثل الفرز السريع، بأداء أفضل عند مقارنتها بفرز التحديد.