اختيار نوع - دروس DS

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

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

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

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

يتم استخدام فرز التحديد بشكل عام عندما -

يجب فرز مجموعة صغيرة
تكلفة المبادلة لا يهم
من الضروري التحقق من جميع العناصر

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

خوارزمية

 SELECTION SORT(arr, n) Step 1: Repeat Steps 2 and 3 for i = 0 to n-1 Step 2: CALL SMALLEST(arr, i, n, pos) Step 3: SWAP arr[i] with arr[pos] [END OF LOOP] Step 4: EXIT SMALLEST (arr, i, n, pos) Step 1: [INITIALIZE] SET SMALL = arr[i] Step 2: [INITIALIZE] SET pos = i Step 3: Repeat for j = i+1 to n if (SMALL &gt; arr[j]) SET SMALL = arr[j] SET pos = j [END OF if] [END OF LOOP] Step 4: RETURN pos

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

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

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

دع عناصر المصفوفة هي -

الآن، بالنسبة للموضع الأول في المصفوفة التي تم فرزها، يجب فحص المصفوفة بأكملها بالتسلسل.

في الوقت الحالي، 12 تم تخزينه في الموضع الأول، وبعد البحث في المصفوفة بأكملها، وجد ذلك 8 هي أصغر قيمة.

كيفية تحويل شار إلى سلسلة

لذلك، قم بتبديل 12 بـ 8. بعد التكرار الأول، سيظهر 8 في الموضع الأول في المصفوفة التي تم فرزها.

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

الآن، قم بتبديل 29 بـ 12. بعد التكرار الثاني، سيظهر 12 في الموضع الثاني في المصفوفة التي تم فرزها. لذلك، بعد تكرارين، يتم وضع القيمتين الأصغر في البداية بطريقة مرتبة.

يتم تطبيق نفس العملية على بقية عناصر المصفوفة. الآن، نعرض تمثيلًا مصورًا لعملية الفرز بأكملها.

الآن، تم فرز المصفوفة بالكامل.

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

الآن، دعونا نرى التعقيد الزمني لفرز التحديد في أفضل الأحوال، وفي الحالة المتوسطة، وفي أسوأ الحالات. سنرى أيضًا مدى تعقيد مساحة فرز التحديد.

1. تعقيد الوقت

قضية	تعقيد الوقت
أفضل حالة	على²)
متوسط الحالة	على²)
الحالة الأسوأ	على²)

على²)

2. تعقيد الفضاء

تعقيد الفضاء	يا(1)
مستقر	نعم

التعقيد المكاني لفرز التحديد هو O(1). وذلك لأنه، في عملية فرز التحديد، يلزم وجود متغير إضافي للتبديل.

تنفيذ فرز الاختيار

الآن، دعونا نرى فرز البرامج المختارة بلغات البرمجة المختلفة.

برنامج: اكتب برنامجًا لتنفيذ الفرز الاختياري بلغة C.

 #include void selection(int arr[], int n) { int i, j, small; for (i = 0; i <n-1; 17 i++) one by move boundary of unsorted subarray { small="i;" minimum element in array for (j="i+1;" j < n; j++) if (arr[j] arr[small]) swap the with first int temp="arr[small];" arr[small]="arr[i];" arr[i]="temp;" } void printarr(int a[], n) * function to print i; (i="0;" i printf('%d ', a[i]); main() a[]="{" 12, 31, 25, 8, 32, }; n="sizeof(a)" sizeof(a[0]); printf('before sorting elements are - 
'); printarr(a, n); selection(a, printf('
after return 0; pre> <p> <strong>Output:</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-7.webp" alt="selection Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement selection sort in C++ language.</p> <pre> #include using namespace std; void selection(int arr[], int n) { int i, j, small; for (i = 0; i <n-1; 15 i++) one by move boundary of unsorted subarray { small="i;" minimum element in array for (j="i+1;" j < n; j++) if (arr[j] arr[small]) swap the with first int temp="arr[small];" arr[small]="arr[i];" arr[i]="temp;" } void printarr(int a[], n) * function to print i; (i="0;" i cout<< a[i] <<' '; main() a[]="{" 80, 10, 29, 11, 8, 30, }; n="sizeof(a)" sizeof(a[0]); 'before sorting elements are - '<<endl; printarr(a, n); selection(a, '
after return 0; pre> <p> <strong>Output:</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-8.webp" alt="selection Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement selection sort in C# language.</p> <pre> using System; class Selection { static void selection(int[] arr) { int i, j, small; int n = arr.Length; for (i = 0; i <n-1; i++) one by move boundary of unsorted subarray { small="i;" minimum element in array for (j="i+1;" j < n; j++) if (arr[j] arr[small]) swap the with first int temp="arr[small];" arr[small]="arr[i];" arr[i]="temp;" } static void printarr(int[] a) * function to print i; n="a.Length;" (i="0;" i console.write(a[i] + ' '); main() int[] a="{" 85, 50, 29, 18, 7, 30, 3}; console.write('before sorting elements are - printarr(a); selection(a); console.write('
after pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-9.webp" alt="selection Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement selection sort in python.</p> <pre> def selection(a): # Function to implement selection sort for i in range(len(a)): # Traverse through all array elements small = i # minimum element in unsorted array for j in range(i+1, len(a)): if a[small] &gt; a[j]: small = j # Swap the found minimum element with # the first element a[i], a[small] = a[small], a[i] def printArr(a): # function to print the array for i in range(len(a)): print (a[i], end = &apos; &apos;) a = [69, 14, 1, 50, 59] print(&apos;Before sorting array elements are - &apos;) printArr(a) selection(a) print(&apos;
After sorting array elements are - &apos;) selection(a) printArr(a) </pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-10.webp" alt="selection Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement selection sort in Java.</p> <pre> public class Selection { void selection(int a[]) /* function to sort an array with selection sort */ { int i, j, small; int n = a.length; for (i = 0; i <n-1; 21 i++) { small="i;" minimum element in unsorted array for (j="i+1;" j < n; j++) if (a[j] a[small]) swap the with first int temp="a[small];" a[small]="a[i];" a[i]="temp;" } void printarr(int a[]) * function to print i; n="a.length;" (i="0;" i system.out.print(a[i] + ' '); public static main(string[] args) a[]="{" 91, 49, 4, 19, 10, }; selection i1="new" selection(); system.out.println('
before sorting elements are - i1.printarr(a); i1.selection(a); system.out.println('
after system.out.println(); pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-11.webp" alt="selection Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement selection sort in PHP.</p> <pre> <?php function selection(&$a, $n) /* function to sort an array with selection sort */ { for ($i = 0; $i < $n; $i++) { $small = $i; //minimum element in unsorted array for ($j = $i+1; $j < $n; $j++) if ($a[$j] < $a[$small]) $small = $j; // Swap the minimum element with the first element $temp = $a[$small]; $a[$small] = $a[$i]; $a[$i] = $temp; } } function printArray($a, $n) { for($i = 0; $i < $n; $i++) { print_r($a[$i]); echo ' '; } } $a = array( 90, 48, 3, 18, 9, 20 ); $n = count($a); echo 'Before sorting array elements are - <br>&apos;; printArray($a, $n); selection($a, $n); echo &apos; <br> After sorting array elements are - <br>&apos;; printArray($a, $n); ?&gt; </pre> <p> <strong>Output:</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-12.webp" alt="selection Sort Algorithm"> <p>So, that&apos;s all about the article. Hope the article will be helpful and informative to you.</p> <p>This article was not only limited to the algorithm. We have also discussed the Selection sort complexity, working, and implementation in different programming languages.</p> <hr></n-1;></pre></n-1;></pre></n-1;></pre></n-1;>

انتاج:

برنامج: اكتب برنامجًا لتنفيذ الفرز بالاختيار في Java.

 public class Selection { void selection(int a[]) /* function to sort an array with selection sort */ { int i, j, small; int n = a.length; for (i = 0; i <n-1; 21 i++) { small="i;" minimum element in unsorted array for (j="i+1;" j < n; j++) if (a[j] a[small]) swap the with first int temp="a[small];" a[small]="a[i];" a[i]="temp;" } void printarr(int a[]) * function to print i; n="a.length;" (i="0;" i system.out.print(a[i] + \' \'); public static main(string[] args) a[]="{" 91, 49, 4, 19, 10, }; selection i1="new" selection(); system.out.println(\'
before sorting elements are - i1.printarr(a); i1.selection(a); system.out.println(\'
after system.out.println(); pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-11.webp" alt="selection Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement selection sort in PHP.</p> <pre> <?php function selection(&$a, $n) /* function to sort an array with selection sort */ { for ($i = 0; $i < $n; $i++) { $small = $i; //minimum element in unsorted array for ($j = $i+1; $j < $n; $j++) if ($a[$j] < $a[$small]) $small = $j; // Swap the minimum element with the first element $temp = $a[$small]; $a[$small] = $a[$i]; $a[$i] = $temp; } } function printArray($a, $n) { for($i = 0; $i < $n; $i++) { print_r($a[$i]); echo \' \'; } } $a = array( 90, 48, 3, 18, 9, 20 ); $n = count($a); echo \'Before sorting array elements are - <br>&apos;; printArray($a, $n); selection($a, $n); echo &apos; <br> After sorting array elements are - <br>&apos;; printArray($a, $n); ?&gt; </pre> <p> <strong>Output:</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-12.webp" alt="selection Sort Algorithm"> <p>So, that&apos;s all about the article. Hope the article will be helpful and informative to you.</p> <p>This article was not only limited to the algorithm. We have also discussed the Selection sort complexity, working, and implementation in different programming languages.</p> <hr></n-1;>

انتاج:

بعد تنفيذ التعليمات البرمجية أعلاه، سيكون الإخراج -

لذلك، هذا كل ما في هذه المادة. نأمل أن تكون المقالة مفيدة وغنية بالمعلومات لك.

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