מיון טכניקות בתכנות: מיון "בועה"

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

מאיפה לו שם כל כך יוצא דופן?

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

תיאור של האלגוריתם

מיון בועות מתבצע כדלקמן:

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

אלגוריתם אפילו קצר יותר של תכנית יכול להיות כפי שנכתב:

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

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

היישום הפשוט מתבצע כדלקמן:

הליך Sortirovka_Puzirkom;

החל

מחזור עבור j מ nachalnii_index כדי konechii_index;

מחזור עבור i מ nachalnii_index כדי konechii_index-1;

אם massiv [i]> massiv [i + 1] (האלמנט הראשון יותר משנייה), אז:

(להתחלף ערכים);

סוף

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

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

הליך Sortirovka_Puzirkom;

החל

sortirovka = true;

מחזור עד sortirovka = true;

sortirovka = false;

מחזור עבור i מ nachalnii_index כדי konechii_index-1;

אם massiv [i]> massiv [i + 1] (האלמנט הראשון יותר משנייה), אז:

(להתחלף אלמנטים);

sortirovka = true; (זיהה כי החילופי נעשה).

End.

מגבלות

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

זמן עופרת מחושב ממספר מספר ריבועים במערך - התוצאה הסופית של זה היא מידתית.

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

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

כבוד

מיון בועות הוא מאוד קל להבין. תוכניות הלימוד של אוניברסיטות טכניות בחקר יסודות סידור המערך שלה לעבור מלכתחילה. השיטה קלה ליישום הוא שפת התכנות דלוף (L (דלפי), ואת C / C ++ (C / C פלוס פלוס), ערכיו הפשוטים להפליא של אלגוריתם מיקום בסדר הנכונה ובבית פסקל (Pascal). סוג הבועה הוא אידיאלי למתחילים.

בשל החסרונות של האלגוריתם אינו משמש למטרות משלימות.

עיקרון מיון חזותי

ההשקפה הראשונית של מערך 8 22 4 74 44 37 1 7

שלב 1 8 22 4 74 44 37 1 7

8 22 4 74 44 1 37 7

8 22 4 74 1 44 37 7

8 22 4 1 74 44 37 7

8 22 1 4 74 44 37 7

8 1 22 4 74 44 37 7

1 8 22 4 74 44 37 7

שלב 2 1 8 22 4 74 44 7 37

1 8 22 4 74 7 44 37

1 8 22 4 7 74 44 37

1 8 22 4 7 74 44 37

1 8 4 22 7 74 44 37

1 4 8 22 7 74 44 37

שלב 3 1 4 8 22 7 74 37 44

1 4 8 22 7 37 74 44

1 4 8 22 7 37 74 44

1 4 8 7 22 37 74 44

1 4 7 8 22 37 74 44

שלב 4 1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

שלב 5 1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

שלב 6 1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

שלב 7 1 4 7 8 22 37 44 74

בועה למשל סוג ב פסקל

לדוגמה:

kol_mas const = 10;

var massiv: מערך [1..kol_mas] של מספר שלם;

א, ב, יא: שלם;

מתחיל

writeln ( 'קלט', kol_mas, 'אלמנטים של מערך');

עבור: = 1 ל kol_mas לעשות readln (massiv [א ]);

עבור: = 1 ל kol_mas-1 לעשות להתחיל

עבור b: = a + 1 כדי kol_mas מתחילים

אם massiv [א]> massiv [ B] אז מתחיל

k: = massiv [א]; massiv [א]: = massiv [ ב]; massiv [ב]: = k;

בסופו;

בסופו;

בסופו;

writeln ( 'לאחר המיון');

עבור: = 1 ל kol_mas לעשות writeln (massiv [א ]);

הסוף.

בועה לדוגמא, מיון בשפת C (C)

לדוגמה:

#include

#include

העיקרי int (int argc, char * argv [])

{

int massiv [8] = {36, 697, 73, 82, 68, 12, 183, 88}, i, ff;

עבור (;;) {

ff = 0;

עבור (i = 7; i> 0; i -) {

אם (massiv [i] [אני- 1]) {

swap (massiv [i], massiv [אני- 1]);

ff ++;

}

}

אם (ff == 0) לשבור;

}

getch (); // עיכוב תצוגה

להחזיר 0;

}.