كيفية استخدام فرز التحديد

فرز التحديد هو أسلوب فرز يقوم بتحديد عنصر قائمة ثم تبديل مكانه بآخر. يقوم بتحديد العنصر الأكبر ثم مبادلته مع عنصر في أعلى فهرس في القائمة.

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

فرز التحديد: نظرة فاحصة

افترض أن لديك القائمة: [39 ، 82 ، 2 ، 51 ، 30 ، 42 ، 7]. لفرز القائمة باستخدام فرز التحديد ، يجب عليك أولاً العثور على أعلى رقم فيها.

مع القائمة المعطاة ، هذا الرقم هو 82. استبدل 82 بالرقم الموجود في أعلى مؤشر (أي 7).

بعد المرور الأول ، سيكون ترتيب القائمة الجديد: [39 ، 7 ، 2 ، 51 ، 30 ، 42 ، 82]. في كل مرة تمر الخوارزمية عبر القائمة بأكملها ، يُسمى ذلك "تمريرة".

لاحظ أن القائمة تحتفظ بقائمة فرعية مرتبة وقائمة فرعية غير مرتبة أثناء عملية الفرز.

متعلق ب: ما هو تدوين Big-O؟

تبدأ القائمة الأصلية بقائمة مصنفة من صفر عناصر وقائمة لم يتم فرزها لجميع العناصر. ثم بعد التمريرة الأولى ، تحتوي على قائمة مرتبة تحتوي على الرقم 82 فقط.

في التمريرة الثانية ، سيكون أعلى رقم في القائمة الفرعية غير المفروزة هو 51. سيتم استبدال هذا الرقم بالرقم 42 لإعطاء ترتيب القائمة الجديدة أدناه:

[39, 7, 2, 42, 30, 51, 82].

تتكرر العملية حتى يتم فرز القائمة بأكملها. يلخص الشكل أدناه العملية برمتها:

تظهر الأرقام باللون الأسود الغامق أعلى قيمة قائمة في ذلك الوقت. تظهر تلك الموجودة باللون الأخضر القائمة الفرعية التي تم فرزها.

تحليل الخوارزمية

للحصول على التعقيد (باستخدام تدوين Big-O) لهذه الخوارزمية ، اتبع أدناه:

في التمرير الأول ، يتم إجراء مقارنات (ن -1). في التمريرة الثانية ، (ن -2). في التمريرة الثالثة ، (n-3) وهكذا حتى المرور (n-1) الذي يقوم بإجراء مقارنة واحدة فقط.

يعطي تلخيص المقارنات على النحو التالي:

(ن -1) + (س -1) + (س -1) +... + 1 = ((س -1) ن) / 2.

لذلك يكون فرز الاختيار O (n²).

تنفيذ التعليمات البرمجية

يوضح الكود الوظائف التي يمكنك استخدامها لأداء فرز التحديد باستخدام Python و Java.

بايثون:

تحديد التحديدفرز (قائمتي):
لـ x في النطاق (len (mylist) - 1 ، 0 ، -1):
max_idx = 0
للوضع في النطاق (1 ، x + 1):
if mylist [posn]> mylist [max_idx]:
max_idx = posn
temp = قائمتي [x]
قائمتي [x] = قائمتي [max_idx]
mylist [max_idx] = temp

جافا:

اختيار باطل فرز (int my_array []) { 
لـ (int x = 0 ؛ س { 
مؤشر int = x ؛ 
لـ (int y = x + 1 ؛ y إذا (my_array [y] الفهرس = ص ؛ // اعثر على أدنى مؤشر 
} 
} 
int temp = my_array [index] ؛ // temp هو تخزين مؤقت
my_array [index] = my_array [x] ؛ 
my_array [x] = temp ؛ 
}}

الانتقال من فرز التحديد إلى دمج الفرز

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

من الأفضل استخدام خوارزمية هي دمج الفرز مع تعقيد O (nlogn). والآن أنت تعرف كيف يعمل فرز التحديد ، يجب أن يكون نوع الدمج التالي في قائمة الدراسة الخاصة بك لفرز الخوارزميات.

نبذة عن الكاتب