מיון בועות
דוגמא:
כתוב תת-תוכנית למיון מערך המכיל מספרים כלשהם בסדר עולה.
פתרון:
נניח שנתונים שלושת המשתנים הבאים: A,B,C
את הגדול בין A ל-B נשים ב-B (נחליף את התאים אם יש צורך)
את הגדול בין B ל-C נציב ב-C (שוב, נחליף את התאים אם יש צורך)
כעת הגדול ביותר נמצא ב-C ונשאר לבצע שוב את הפעולה הראשונה (כלומר השוואה בין A ל-B והצבת הגדול מבין השניים ב-B ).
קיבלנו סדרה של שלושה מספרים ממוינים.
מיון מסוג זה נקרא מיון בועות (Bubble sort) כיוון שהמספר מבעבע למקומו שלב אחרי שלב (מקום אחרי מקום).
את האלגוריתם הזה נרחיב ונבצע אותו על המערך (נשחק עם המצביעים על התאים במערך):
program SORT_ARRAY; { תוכנית הכוללת תת תוכנית המבצעת מיון בועות} const FIRST = 1; (* התא הראשון במערך *) LAST = 10; (* התא האחרון במערך *) type ARRAY_10_INT = array[FIRST..LAST] of integer; · · קטע הבא לפני תת תוכנית זו · procedure BUBBLE_SORT (var A:ARRAY_10_INT); { תת תוכנית למיון מערך על ידי מיון בועות } { A המערך שימוין הוא מערך } var I:integer; (* מצביע על התא שעד אליו יבוצעו ההשוואות בכל מעבר *) J:integer; (* I עד , J+1 ו- J ההשוואות מבוצעות בין התא *) TEMP:integer; (* תא עזר לביצוע ההחלפה *) begin for I:= (LAST-1) downto FIRST do (* לך עד התא לפני האחרון*) begin for J:=FIRST to I do (* I לך עד *) begin if A[J]>A[J+1] then (* J+1 גדול מהתא J אם התא ה-*) begin (* החלף את ערכי התאים *) TEMP:=A[J]; A[J]:=A[J+1]; A[J+1]:=TEMP; end; end; end; end; · · קטע הבא אחרי תת תוכנית זו ·
|
להורדת הפרוצדורה של מיון בועות לחץ כאן
אם התאים 2 עד 9 ממוינים ורק 1 ו-10 לא ממוינים, כלומר, מוחלפים ביניהם, יתבצעו 17 החלפות.
במקרה הגרוע ביותר, כשהמערך ממוין הפוך מהדרוש, יתבצעו
9+8+…+2+1=45 החלפות.