- מיון דחיפה

דף ראשי «

מפת האתר «

אודות האתר «

עזרה «

study.eitan.ac.il «

» נושאי לימוד

יום שבת 4 במאי 2024

מיון דחיפה

דף ראשי

פרק 5: אלגורתמי מיון בפסקל

מיון דחיפה

מיון דחיפה

דרך אחרת למיון מערך היא על ידי אלגוריתם של מיון דחיפה.

דוגמא:

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

המיון יעשה על ידי אלגוריתם של מיון דחיפה.

פתרון:

תחילה נאתר את המספר הקטן ביותר במערך ונחליף אותו עם תוכן תא מספר 1. לאחר מכן נחפש מתא מס' 2 ועד סוף המערך, את המספר הקטן ביותר ונחליפו עם תוכן תא 2.

כך נמשיך את התהליך עד תא מספר 9.

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

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

program SORT_ARRAY;

   { תוכנית הכוללת תת תוכנית המבצעת מיון }

const

   FIRST:=1; (* התא הראשון במערך *)

   LAST = 10; (* התא האחרון במערך *)

type

   ARRAY_10_INT = array[FIRST..LAST] of integer;

    ·

    ·   קטע הבא לפני תת תוכנית זו

    ·

procedure PUSH_DOWN_SORT (var A:ARRAY_10_INT);

   { תת תוכנית למיון מערך על ידי מיון דחיפה }

   { A המערך שימוין הוא מערך }

var

   I: integer; (* מונה הלולאה החיצונית *)

   J: integer; (* מונה הלולאה הפנימית *)

   CELL: integer; (* משמר את מספר התא בו נמצא המספר הקטן ביותר *)

   SMALL: integer; (* התא שבו יישמר המספר הקטן ביותר *)

begin

   for I:=FIRST to (LAST-1) do (*לך מהתא הראשון עד לפני האחרון*)

   begin

      CELL := I; (* הנח כי התא הנוכחי מכיל את המספר הקטן ביותר*)

      SMALL := A[I];

      for J:=(I+1) to LAST do (* לך מהתא הבא עד סוף המערך *)

      begin

         if A[J] < SMALL then (* אם תוכן תא זה קטן מזה ששמרת*)

         begin

            SMALL:=A[J]; (* שמור את תוכנו *)

            CELL:= J; (* ושמור את מספר התא הזה *)

         end;

      end;

      A[CELL]:=A[I]; (* לתא בו נמצא הקטן I הצב את תוכן התא *)

      A[I]:=SMALL; (* את הערך הקטן היותר I הצב לתוך התא *)

   end;

end;

    ·

    ·        קטע הבא אחרי תת תוכנית זו

    ·

להורדת הפרוצדורה לחץ כאן

אם היינו רוצים לסדר את המערך מהגדול לקטן, כל שהיה עלינו לעשות הוא להחליף את הסימן

> (קטן) בסימן < (גדול) בהוראת if .

מספר ההשוואות שבוצעו (ההוראה if) הוא 45=1+...+9.

מספר השוואות זה קבוע (אי אפשר לומר מה יקרה במקרה הגרוע ביותר).

לעומת זאת, מספר ההחלפות במקרה הגרוע יהיה 9. זה יקרה כאשר המערך לא ממוין לחלוטין.

אם רק חלק מהתאים לא ממוינים, יבוצעו החלפות רק כמספר התאים הלא ממוינים.לדוגמא, אם התאים 2 עד 9 ממוינים ורק 10 ו-1 אינם ממוינים תתבצע רק החלפה אחת.

דוגמא:

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

פתרון:

החציון של סדרת מספרים הוא המספר החוצה את סדרת המספרים לשניים, כאשר המספרים מסודרים לפי גודלם (כלומר הסדרה ממוינת).

לדוגמא, כאשר בסדרה יש מספר אי זוגי של מספרים, החציון של סדרת המספרים: 10,8,8,8,7,5,4,4,3 הוא 7. (המספר האמצעי)

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

לדוגמא, החציון של סדרת המספרים: 10,8,8,8,5,4,4,3 הוא:

7.5 = 2/(8+5)

ולכן, בתרגיל על מנת לחשב חציון יש למיין תחילה את המערך:

program NAME;

const

   FIRST = 26;

   LAST = 35;

type

   ARRAY_10_INT=array[FIRST..LAST] of integer;

    ·

    ·     קטע הבא לפני תת תוכנית זו

    ·

function MEDIAN (var A:ARRAY_10_INT):real;

   { תת-תוכנית לחישוב החציון בסדרת מספרים }

var

   N:real; (* הערך השלם יצביע על התא בו נמצא החציון *)

begin

   { בצע מיון של המערך }

   PUSH_DOWN_SORT(A);

   {הוגדר כממשי N מצא את אמצע המערך – יתכן ויהיה שבר ולכן }

   N:=(FIRST+LAST)/2;

{עליו(השלם) מצביע N-אם מספר האיברים אי זוגי אזי החציון הוא בתא ש}

   {(השלם) N+1 ו- N זוגי) החציון הוא הממוצע של המקום ה-N אחרת,(אם}

   if (((FIRST +LAST) mod 2 ) = 0) then   (* מערך אי זוגי *)

      MEDIAN:=A[round(N)]

   else

      MEDIAN:=(A[trunc(N)] + A[trunk(N+1)])/2; (* מערך זוגי *)

end;

   ·

   ·    קטע הבא אחרי תת תוכנית זו

   ·