מיון אלגוריתמים כפי שהם

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

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

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

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

הבה נבחן את הגרסה הראשונה של האלגוריתם של מיון מערך לפי שיטת בועה. האלגוריתם המילולי למיון מערך הכולל את המזה מזהה ומורכב מרכיבים N נראה כך:

1. שים במקום האלמנט הראשון (mas [1]) האלמנט הגדול של המערך. לשם כך, נוכל להשוות את זה הופך את כל האלמנטים הנותרים (mas [2], mas [3] ... mas [N]). אם אתה מוצא כי כל האלמנטים האחרים עולה mas [1], הוא נדרש להחליף אותם (באמצעות buf משתנה נוסף).

2. לאחר החזרת המרכיב [1] לאמור, חזור על הפסקה 1 עבור האלמנט mas [2].

3. פעולות אלה יש לחזור על כל האלמנטים למעט האחרון.

יישום אלגוריתם מיון הבועה בפסקל:

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

הנה יישום אלגוריתם מיון זה עבור שפת התכנות של פסקל:

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