שיטות מיון

שיטות שונות למיון מערכים חד-מימדיים

מהו מיון ?

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

סוגי מיון

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

מיון בחירה

מיון בחירה (selection sort בלעז) הוא אלגוריתם מיון השוואתי פשוט אך לא יעיל.

מיון בועות

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


בתחילת הסרטון תצפה באנימציה המדגימה מיון בועות .


צפה במצגת המתארת את תהליך המיון.


מיון בועות (מערך A )

טענת כניסה : הפעולה מקבלת מערך עם נתונים

טענת יציאה : הפעולה ממיינת את אברי המערך בסר עולה

1) עבור i מ 0 עד size-2 (כולל) בצע :

1.1) עבור j מ 0 עד size-2-i (כולל) בצע:

1.1.1) אם A[j] גדול מ A[j+1] אזי

1.1.1.1) [temp = A[j

A[j] = A[j+1] (1.1.1.2

1.1.1.3) A[j+1] = temp

במעבר הראשון עוברים על מערך בגודל size ומביאים את האיבר הגדול ביותר למקום האחרון במערך, במקום ה - size-1 .

במעבר השני עוברים על מערך בגודל size-1 ומביאים למקום ה size-2 את האיבר השני בגודלו.

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

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

הלולאה הפנימית "מגלגלת" את האיבר הגדול ביותר למקומו בסוף המערך.


איזה מיון נראה לך יעיל יותר : מיון בחירה או מיון בועות ?

מיון בועות משופר

שיפור האלגוריתם :

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

כיצד נדע שהמערך כבר ממוין ? – אם באחד המעברים לא בוצעו החלפות כלל, סימן שהמערך ממוין.

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

משימה

פתח את המצגת ופעל לפי ההוראות.

מיון הכנסה

קרא את תיאור האלגוריתם .


כתוב את קוד הדמה בשפת java ובדוק ע"י הרצה .

מיזוג מערכים ממויינים

צפה בקובץ המתאר את האלגוריתם ( עמודים 82-84 )


פתור אחד מהתרגילים 13 , 14 , 15 המופיעים בעמוד 85 .

מטלה

ממש אחד מבין האלגוריתמים שלפניך :



מיון מניה – Counting Sort


הנחה על הקלט: איברי הקלט הם מספרים שלמים בתחום 0-K .


רעיון כללי: לכל איבר x, נספור את כמות האיברים שקטנים/שווים לו וכך נדע איפה הוא צריך להיות במערך הסופי.


כתוב את האלגוריתם שלך במצגת .


מיון דליים


הנחה על הקלט: איברי הקלט הם מספרים שלמים בתחום 0-K .


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


כתוב את האלגוריתם שלך במצגת.