שיטות מיון
שיטות שונות למיון מערכים חד-מימדיים
מהו מיון ?
סוגי מיון
מיון בחירה
מיון בועות
מיון בועות (באנגלית: 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 – סימן שבוצעה החלפה והמערך עדיין איננו ממוין, ויש להמשיך בתהליך המיון.
משימה
מיון הכנסה
מיזוג מערכים ממויינים
מטלה
מיון מניה – Counting Sort
הנחה על הקלט: איברי הקלט הם מספרים שלמים בתחום 0-K .
רעיון כללי: לכל איבר x, נספור את כמות האיברים שקטנים/שווים לו וכך נדע איפה הוא צריך להיות במערך הסופי.
כתוב את האלגוריתם שלך במצגת .
מיון דליים
הנחה על הקלט: איברי הקלט הם מספרים שלמים בתחום 0-K .
רעיון כללי: לכל איבר x , נספור כמה פעמים הוא מופיע במערך, ולפי הספירה שהתקבלה נמלא מערך חדש שבו המספרים יהיו ממויינים.
כתוב את האלגוריתם שלך במצגת.