TechCodeview

במדריך זה, ניישם את אלגוריתם מיון הבחירה ב-Python. זה אלגוריתם די פשוט המשתמש בפחות החלפות.

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

עבודה של מיון סלקציה

להלן השלבים כדי להסביר את פעולת מיון הבחירה ב- Python.

בואו ניקח מערך לא ממוין כדי להחיל את אלגוריתם מיון הבחירה.

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

שלב 1: קבל את אורך המערך.

אורך = len(מערך) → 6

שלב 2: ראשית, אנו מגדירים את האלמנט הראשון כאלמנט מינימום.

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

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

שלב 4: לאחר כל איטרציה, האלמנט המינימלי מוחלף מול המערך הלא ממוין.

שרשרת מחרוזת java

שלב - 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>

הסבר -

בואו נבין את הקוד לעיל -

• ראשית, אנו מגדירים את select_sort() פונקציה שלוקחת מערך כארגומנט.
• בפונקציה, אנו מקבלים את אורך המערך ששימש לקבוע את מספר המעברים שיש לבצע בהשוואת ערכים.
• כפי שאנו יכולים לראות את זה, אנו משתמשים בשתי לולאות - לולאה חיצונית ופנימית. הלולאה החיצונית משתמשת כדי לחזור על ערכי הרשימה. לולאה זו תחזור על 0 עד (אורך-1). אז האיטרציה הראשונה תתבצע (5-1) או 4 פעמים. בכל איטרציה, הערך של המשתנה i מוקצה למשתנה
• הלולאה הפנימית משתמשת כדי להשוות את כל ערך של אלמנט בצד ימין לערך השני באלמנט השמאלי ביותר. אז הלולאה השנייה מתחילה את האיטרציה שלה מ-i+1. זה יבחר רק את הערך שאינו ממוין.
• מצא את האלמנט המינימלי ברשימה הלא ממוינת ועדכן את מיקום minIndex.
• מקם את הערך בתחילת המערך.
• לאחר השלמת האיטרציה, המערך הממוין מוחזר.
• לבסוף אנחנו יוצרים מערך לא ממוין ועוברים ל- select_sort() הוא מדפיס את המערך הממוין.

מורכבות הזמן של מיון הבחירה

מורכבות הזמן היא חיונית במונחים של כמה זמן לוקח אלגוריתם למיין אותו. במיון הבחירה, יש שתי לולאות. הלולאה החיצונית פועלת במשך n פעמים (n הוא מספר כולל של אלמנט).

הלולאה הפנימית מבוצעת גם n פעמים. הוא משווה את שאר הערך לערך הלולאה החיצונית. אז, יש n*n פעמים של ביצוע. מכאן שמורכבות הזמן של אלגוריתם מיון מיזוג היא O(n²).

ניתן לסווג את מורכבות הזמן לשלוש קטגוריות.