מיון בחירה - מדריך 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 הוא הערך הקטן ביותר.

אילו חודשים הם q1

אז, החלף 12 ב-8. לאחר האיטרציה הראשונה, 8 יופיע במיקום הראשון במערך הממוין.

עבור המיקום השני, שבו 29 מאוחסן כעת, אנו שוב סורקים ברצף את שאר הפריטים של מערך לא ממוין. לאחר הסריקה, אנו מגלים ש-12 הוא האלמנט השני הנמוך ביותר במערך שאמור להופיע במיקום השני.

כעת, החליפו 29 ב-12. לאחר האיטרציה השנייה, 12 יופיע במיקום השני במערך הממוין. אז, לאחר שתי איטרציות, שני הערכים הקטנים ביותר ממוקמים בהתחלה בצורה ממוינת.

אותו תהליך מוחל על שאר רכיבי המערך. כעת, אנו מציגים ייצוג ציורי של תהליך המיון כולו.

כעת, המערך ממוין לחלוטין.

מורכבות מיון הבחירה

כעת, בואו נראה את מורכבות הזמן של מיון הבחירה במקרה הטוב, במקרה הממוצע, ובמקרה הגרוע ביותר. נראה גם את מורכבות החלל של מיון הבחירה.

1. מורכבות זמן

מקרה	מורכבות זמן
המקרה הטוב ביותר	עַל²)
מקרה ממוצע	עַל²)
במקרה הגרוע ביותר	עַל²)

עַל²)

2. מורכבות החלל

מורכבות החלל	O(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;>

תְפוּקָה:

לאחר ביצוע הקוד לעיל, הפלט יהיה -

אז, זה הכל לגבי המאמר. מקווה שהמאמר יהיה מועיל ואינפורמטיבי עבורך.

מאמר זה לא היה מוגבל רק לאלגוריתם. דנו גם במורכבות מיון הבחירה, העבודה והיישום בשפות תכנות שונות.