מיון מערך - int

Complexity - סיבוכיות

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

מיון

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

סידור ערכים במערך

בעת חיפוש בתוך מערך \ רשימה ע"מ ליעל את העבודה ולחסוך משאבים של המחשב והתוכנה מחלקת את הרשימה ל2 ומבצעת בדיקה מול ערך שמאמצע במידה והערך שמחפשים גדול ממנו החיפוש יתבצע בצד אחד של המערך אחרת בצד השני

במערך של string  הבדיקה היא לפי הABC במידה והמילה שמחפשים גדולה מהערך האמצעי התשובה שמתקבלת היא 1 והחיפוש יהיה בצד הגדול אחרת התשובה היא 1- והחיפוש בצד הקטן

לכן צריך לסדר את המערך בסדר עולה 

החלפת ערכים במערך

דוג' להחלפה פשוטה שבה יצרנו מערך עם 5 מספרים ומבקשים מהמשתמש לבחור איזה מספר להחליף עם איזה

פונקציה ראשונה מציגה למשתמש את המערך והשנייה עושה את ההחלפה באמצעות משתנה עזר – מכניסים את הערך של המשתנה הראשון למשתנה עזר > מעדכנים את הראשון בערך של השני > מעדכנים את השני בערך של הראשון שנמצא במשתנה עזר ואז שוב קוראים לפונקציה הראשונה שתציג את המערך עם הסדר החדש

static void Main(string[] args)

        {

            int[] data = new int[5] {0 , 1, 2, 3, 4};

            int m = 0, n = 0;

            {

                show(data);

                Console.WriteLine("enter first");

                m = Convert.ToInt32 (Console.ReadLine());

                Console.WriteLine("enter second");

                n = Convert.ToInt32(Console.ReadLine());

                swap(data, m, n);

                show(data);

            }

        }

        public static void  show (int[] data)

        {

            for (int i = 0; i < data.Length; i++)

            {

                Console.WriteLine(data[i] + ",");

            }

            Console.WriteLine();

        }

        public static void swap(int[] data , int m , int n)

        {

            int temporary;

            temporary = data[m];

            data[m] = data[n];

            data[n] = temporary;

        }

Bubble Sort

סידור המערך בסדר עולה  - המיון קיבל את שמו מהדרך בה מבעבעים אלמנטים במערך: האלמנטים הכבדים בכיוון אחד, והקלים בכיוון ההפוך

int[] data = new int[5] {9 , 1, 4, 8, 3};

            int i, j;

            int N = data.Length;

            for (j = N - 1; j > 0; j--)

            {

                for (i = 0; i < j; i++)

                {

                    if (data[i] > data[i + 1])

                        swap(data, i, i + 1);

                }

             }

1. הגדרנו מערך עם חמישה מספרים
2. משתנה N מוגדר לערך של האורך של המערך = 5
3. לולאה ראשונה רצה 4 פעמים -  J = לN מינוס 1 (על המספר האחרון במערך לא צריך לרוץ ולבדוק אם יש גדול ממנו אחריו כי הוא האחרון)
4. לולאה פנימית שרצה 4 (מ-ס ועד J) פעמים ובודקת האם המספר במערך גדול מהמספר שלידו במידה וכן מתבצעת קריאה לפונקציה שמחליפה בניהם  (אותה הפונקציה מהדוג' הקודמת)

סדר המספרים במערך בתחילת ההרצה  -  9, 1, 4, 8, 3

בסיבוב הראשון של הלולאה החיצונית – הלולאה הפנימית רצה בדקה את מיקום אחד מול 2 והחליפה בניהם בסיבוב השני בדקה את מיקום 2 מול 3 והחליפה בניהם כך שבסיום הסיבוב הראשון הסדר של המערך היה  1, 4, 8, 3, 9

בסיבוב השני – מיקום ראשון ושני לא הוחלפו כי אחד לא גדול מ4 וכן השני עם השלישי אבל 8 התחלף עם 3 1, 4, 3, 8, 9

בסיום הסיבוב השלישי   - 1, 3, 4, 8, 9 

סיבוב רביעי כבר רץ ללא שינויים

Selection Sortמיון בחירה

• נמצא את האיבר בעל הערך הנמוך ביותר במערך.
• נחליף אותו עם האיבר הראשון במערך.
• ונמשיך באותה שיטה על שאר המערך (ללא האיבר הראשון).

 היתרון שבכל הרצה מבצעים פחות פעולות אך בכ"א במונחי זמן רציה המיון נחשב כלא יעיל

            int[] data = new int[5] {9 , 1, 4, 8, 3};

            for (int i = 0; i < data.Length; i++)

            {

                int min = i;

                for (int  j= i+1 ; j < data.Length; j++)

                {

                    if(data[j] < data[min])

                    {

                        min = j;

                    }

                }

                if (data[i] > min)

                {

                    swap( data , i, min );

                }

            }

פונקציות רקורסיביות

פונקציה שקוראת לעצמה לדוג' פונקציה לחישוב חזקה -  2 בחזקת 4    התרגיל הנדרש הוא

16  = 2•2•2•2

לביצוע החישוב נעשה פונקציה שמכפילה מספר בעצמו וקוראת לעצמה לחישוב חוזר 

לא לשכוח! לתת לפונקציה תנאי יציאה אחרת היא תחזור על עצמה שוב ושוב

static void Main(string[] args)

        {

            int b , a , result;

            Console.WriteLine("enter number base");

            b = Convert.ToInt32(Console.ReadLine());

            Console.WriteLine("enter number exponent");

            a = Convert.ToInt32(Console.ReadLine());

            result = Exponentiation(b , a);

            Console.WriteLine(result);

{

     public static int Exponentiation(int m , int n)

            {  if (n > 1)

            {

                return m * Exponentiation(m, n - 1);

            }

           return m;

        }