Let's learn C

מיון בחירה

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

מיון זה עובד בצורה הבאה:

נחפש כל פעם את הערך המינימלי.
לאחר שעברנו על כל המערך נחליף את הערך המינימלי באיבר הראשון*.
*בכל פעם האיבר הראשון מתקדם תא אחד במערך עד שנעבור על כולו.
כלומר, במעבר הראשון על המערך האיבר הראשון יהיה האיבר בתא 0.
במעבר השני על המערך האיבר הראשון יהיה האיבר בתא 1.
וכן הלאה עד שנגיע לאיבר הn-1.

תהליך המיון

דוגמה עם מערך בגודל 6 (n=6):

Current Parameters:i=0 ,j=1 ,min=0
בסבב הראשון i מתחיל מ0 ו j מתחיל מ 1 (כדי למנוע בדיקה על אותו המספר בריצה הראשונה).
נגדיר את min להיות התא הראשון שממנו אנו מתחילים (כלומר 0).
כעת, אנו נעבור על כל המערך ונחפש את האיבר המינימלי.
(נשווה את ערך התא שבתוך המשתנה min לבין שאר הערכים ובמידת הצורך נשנה את הערך של min בהתאם).
לאחר שעברנו על כל המערך בפעם הראשונה גילינו כי האיבר המינימלי נמצא בתא מספר 5.
לכן, נחליף ביניהם.

לאחר ההחלפה המערך יראה כך:

Current Parameters: i=1 ,j=2 ,min=1
בסבב השני i גדל ב1 (כי אנחנו יודעים שערך הכי קטן נמצא כבר במיקום שלו), נשווה את הערך שבmin אליו (min=1)
כלומר, אנו מחפשים כעת את האיבר השני הכי קטן.
נגדיר את j להיות 2 (כדי למנוע בדיקה על אותו המספר בריצה הראשונה).
לאחר שרצנו על כל המערך ראינו כי האיבר שנמצא בתא מספר 1 הוא עצמו המינימלי ולכן לא נבצע החלפה.
כלומר המערך ישאר כך:

Current Parameters: i=2 ,j=3 ,min=2
בסבב השלישי i גדל ב1 (כי אנחנו יודעים שכל הערכים לפניו ממוינים), נשווה את הערך שבmin אליו (min=2) כלומר, אנו מחפשים כעת את האיבר השלישי הכי קטן.
נגדיר את j להיות 3 (כדי למנוע בדיקה על אותו המספר בריצה הראשונה).
לאחר שרצנו על כל המערך ראינו כי האיבר שנמצא בתא מספר 4 הוא המינימלי ולכן נחליף אותו עם תא מספר 2.

לאחר ההחלפה המערך יראה כך:

Current Parameters:i=3 ,j=4 ,min=3
בסבב הרביעי i גדל ב1 (כי אנחנו יודעים שכל הערכים לפניו ממוינים), נשווה את הערך שבmin אליו (min=3) כלומר, אנו מחפשים כעת את האיבר הרביעי הכי קטן.
נגדיר את j להיות 4 (כדי למנוע בדיקה על אותו המספר בריצה הראשונה).
לאחר שרצנו על כל המערך ראינו כי האיבר שנמצא בתא מספר 5 הוא המינימלי ולכן נחליף אותו עם תא מספר 3.

לאחר ההחלפה המערך יראה כך:

Current Parameters:i=4 ,j=5 ,min=4
בסבב החמישי i גדל ב1 (כי אנחנו יודעים שכל הערכים לפניו ממוינים), נשווה את הערך שבmin אליו (min=4) כלומר, אנו מחפשים כעת את האיבר החמישי הכי קטן.
נגדיר את j להיות 5 (כדי למנוע בדיקה על אותו המספר בריצה הראשונה).
לאחר שרצנו על כל המערך ראינו כי האיבר שנמצא בתא מספר 4 הוא עצמו המינימלי ולכן לא נבצע החלפה.
כלומר המערך ישאר כך:

Current Parameters: i=5 ,j=6 ,min=5
בסבב השישי (והאחרון) i גדל ב1 (כי אנחנו יודעים שכל הערכים לפניו ממוינים), נשווה את הערך שבmin אליו (min=5).
כלומר, אנו מחפשים כעת את האיבר השישי הכי קטן.
נגדיר את j להיות 6 (כדי למנוע בדיקה על אותו המספר בריצה הראשונה).
כעת, אנו רואים כי j שווה לגודל המערך ולכן אין צורך לרוץ על המערך כי אנחנו יודעים שאין יותר ערכים לא ממוינים.
כלומר המערך שלנו ממוין!

מיון בחירה נראה כך בקוד:

זמן ריצה של מיון בחירה עומד בסדר גודל של O(n²).
ראוי לציין שזה אינו האלגוריתם היחיד שמממש מיון בחירה.

CODE:


#include <stdio.h>
void swap(int *num1, int *num2)
{
  int temp = *num1;
  *num1 = *num2;
  *num2 = temp;
}

void selection_sort(int *array, int n)
{
  int i, j, min;
  for (i = 0; i < n - 1; i++)
  {
    min = i;	
    j=i+1;
    while (j<n)
    {
      if (array[j] < array[min])
      {
        min = j;
      }
      j++;
    }
    if (min!=i)
    {
      Swap(&array[min], &array[i]);
    }
  }
}