فرز التحديد في بيثون

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

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

العمل على فرز الاختيار

فيما يلي الخطوات لشرح عمل نوع التحديد في بايثون.

لنأخذ مصفوفة غير مصنفة لتطبيق خوارزمية فرز التحديد.

[30، 10، 12، 8، 15، 1]

الخطوة 1: احصل على طول المصفوفة.

مقارنة جافا

الطول = لين (مصفوفة) → 6

الخطوة 2: أولاً، قمنا بتعيين العنصر الأول كحد أدنى للعنصر.

الخطوه 3: الآن قارن الحد الأدنى بالعنصر الثاني. إذا كان العنصر الثاني أصغر من الأول، فإننا نعينه كحد أدنى.

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

الخطوة - 4: بعد كل تكرار، يتم تبديل الحد الأدنى من العناصر أمام المصفوفة غير المصنفة.

الخطوة - 5: يتم تكرار الخطوات من الثانية إلى الثالثة حتى نحصل على المصفوفة التي تم فرزها.

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

خوارزمية فرز الاختيار على النحو التالي.

خوارزمية

عفوا في جافا

 selection_sort(array) repeat (0, length - 1) times set the first unsorted element as the minimum for each of the unsorted elements if element <currentminimum set element as new minimum swap with first unsorted position end selection_sort < pre> <h2>Selection Sort Program using Python</h2> <p>The following code snippet shows the selection sort algorithm implementation using Python.</p> <p> <strong>Code -</strong> </p> <pre> def selection_sort(array): length = len(array) for i in range(length-1): minIndex = i for j in range(i+1, length): if array[j] <array[minindex]: minindex="j" array[i], array[minindex]="array[minIndex]," array[i] return array print('the sorted is: ', selection_sort(array)) < pre> <p> <strong>Output:</strong> </p> <pre> The sorted array is: [3, 6, 9, 21, 33] </pre> <p> <strong>Explanation -</strong> </p> <p>Let&apos;s understand the above code -</p> <ul> <li>First, we define the <strong>selection_sort()</strong> function that takes array as an argument.</li> <li>In the function, we get the length of the array which used to determine the number of passes to be made comparing values.</li> <li>As we can see that, we use two loops - outer and inner loop. The outer loop uses to iterate through the values of the list. This loop will iterate to 0 to (length-1). So the first iteration will be perform (5-1) or 4 times. In each iteration, the value of the variable i is assigned to the variable</li> <li>The inner loop uses to compare the each value of right-side element to the other value on the leftmost element. So the second loop starts its iteration from i+1. It will only pick the value that is unsorted.</li> <li>Find the minimum element in the unsorted list and update the minIndex position.</li> <li>Place the value at the beginning of the array.</li> <li>Once the iteration is completed, the sorted array is returned.</li> <li>At last we create an unsorted array and pass to the <strong>selection_sort()</strong> It prints the sorted array.</li> </ul> <h2>Time Complexity of Selection Sort</h2> <p>Time complexity is an essential in term of how much time an algorithm take to sort it. In the selection sort, there are two loops. The outer loop runs for the n times (n is a total number of element).</p> <p>The inner loop is also executed for n times. It compares the rest of the value to outer loop value. So, there is n*n times of execution. Hence the time complexity of merge sort algorithm is O(n<sup>2</sup>).</p> <p>The time complexity can be categorized into three categories.</p> <hr></array[minindex]:></pre></currentminimum>

توضيح -

دعونا نفهم الكود أعلاه -

أولا نحدد اختيار نوع() الدالة التي تأخذ المصفوفة كوسيطة.
في الدالة، نحصل على طول المصفوفة المستخدمة لتحديد عدد التمريرات التي سيتم إجراؤها لمقارنة القيم.
كما نرى، نستخدم حلقتين - الحلقة الخارجية والداخلية. تستخدم الحلقة الخارجية للتكرار عبر قيم القائمة. سوف تتكرر هذه الحلقة من 0 إلى (الطول -1). لذلك سيتم تنفيذ التكرار الأول (5-1) أو 4 مرات. في كل تكرار، يتم تعيين قيمة المتغير i للمتغير
تستخدم الحلقة الداخلية لمقارنة كل قيمة من عناصر الجانب الأيمن بالقيمة الأخرى في العنصر الموجود في أقصى اليسار. لذا فإن الحلقة الثانية تبدأ تكرارها من i+1. سيتم فقط اختيار القيمة التي لم يتم فرزها.
ابحث عن الحد الأدنى للعنصر في القائمة غير المصنفة وقم بتحديث موضع minIndex.
ضع القيمة في بداية المصفوفة.
بمجرد اكتمال التكرار، يتم إرجاع المصفوفة التي تم فرزها.
أخيرًا قمنا بإنشاء مصفوفة غير مصنفة وتمريرها إلى اختيار نوع() يقوم بطباعة المصفوفة التي تم فرزها.

التعقيد الزمني لفرز التحديد

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

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

يمكن تصنيف التعقيد الزمني إلى ثلاث فئات.