איך בונים אלגוריתם מיון?

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

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

קטע תוכנית לדוגמה:

For A:= 1 to Size - 1 do
For B:= A + 1 to Size do
If Table[B] < Table [A] then
Begin
Temp := Table[A];
Table[A] := Table [B];
Table[B] := Temp
End;

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

קטע תוכנית לדוגמה:

A:= 1;
Switch := True;
While (A < Size) and (Switch = True) do
Begin
Switch := False;
For B := 1 to Size - A do
If Table [B+1] < Table[B] then
Begin
Temp:= Table[B];
Table[B] := Table[B+1];
Table[B+1] := Temp;
Switch := True;
End;
A := A + 1;
End;

מיון על ידי שיבוץ (Insertion Sort) במיון זה מניחים שהערכים שכבר משובצים בטבלה הינם ממוינים. את הערך החדש צריך להוסיף לטבלה במקום המתאים לו לפי סדר המיון. אם הוכנסו כבר K ערכים לטבלה, אפשר להכניס לטבלה את האיבר החדש שמספרו הסידורי הוא 1 + K. הפעולות הדרושות הן מציאת המקום J בטבלה כך ש:X < A[J] וגם X > A[J-1]. מזיזים את האיברים ממקום J ואילך למקום הבא בטבלה ומכניסים את X למקום J. אם X אינו קטן מאיבר כלשהו בתחום 1 עד K, הערך של J יגיע לערך 1 + K, כלומר יש להכניס את האיבר בסוף הטבלה, ואם הערך של X קטן מכל הערכיים, יש להכניסו בראש הטבלה.

מה קשור?

מהן פקודות דוס?  איך מחפשים באינטרנט?  איך בונים אלגוריתם חיפוש?

 

 הוסף הערה חדשה    שנה את ההגדרות בנוגע להערות