יש מספר די גדול של אלגוריתמי מיון, רבים מהם מאוד ספציפיים ופותחו כדי לפתור מגוון מצומצם של בעיות ולעבוד עם סוגי נתונים ספציפיים. אבל מבין כל המגוון הזה, האלגוריתם הפשוט ביותר הוא מיון בועות, שניתן ליישם בכל שפת תכנות. למרות הפשטות שלו, הוא עומד בבסיס אלגוריתמים רבים למדי. יתרון נוסף וחשוב לא פחות הוא הפשטות שלו, ולכן, ניתן לזכור אותו וליישם אותו מיד, מבלי שתהיה לפניכם ספרות נוספת.
בניגוד לתוכנת מחשב, המיון לא יקשה עליכם, כי אתם מסוגלים לראות את כל התמונה ומיד להבין איזה גיבור צריך להעביר לאן כדי שהמיון לפי גובה יסתיים בהצלחה. בטח כבר ניחשתם שכדי למיין את מבנה הנתונים הזה בסדר עולה, פשוט החליפו את המקומות של האלק ואיירון מן:
טיפש משהו ואינו רואה את כל מבנה הנתונים כמכלול. תוכנית הבקרה שלה יכולה להשוות רק שני ערכים בו זמנית. כדי לפתור בעיה זו, היא תצטרך למקם שני מספרים בזיכרון ולבצע עליהם פעולת השוואה, ולאחר מכן לעבור לזוג מספרים אחר, וכך הלאה עד שכל הנתונים נותחו. לכן, כל אלגוריתם מיון יכול להיות מפושט מאוד בצורה של שלושה שלבים:
לאחר שתעבור על כל הרשימה במעבר אחד עם אלגוריתם כזה, המיון לא יסתיים לחלוטין. אבל מצד שני, האלמנט הגדול ביותר ברשימה יועבר למיקום הימני הקיצוני. זה תמיד יקרה, כי ברגע שתמצא את האלמנט הגדול ביותר, אתה כל הזמן תחליף מקומות עד שתזיז אותו עד הסוף. כלומר, ברגע שהתוכנית "תמצא" את האלק במערך, היא תעביר אותו הלאה לסוף הרשימה:
זו הסיבה שהאלגוריתם הזה נקרא מיון בועות, מכיוון שכתוצאה מהפעולה שלו, האלמנט הגדול ביותר ברשימה יהיה בחלק העליון של המערך, וכל האלמנטים הקטנים יותר יוזזו מיקום אחד שמאלה:
כדי להשלים את המיון, תצטרכו לחזור לתחילת המערך ולחזור שוב על חמשת השלבים שתוארו למעלה, שוב לעבור משמאל לימין, להשוות ולהזיז אלמנטים לפי הצורך. אבל הפעם אתה צריך לעצור את האלגוריתם אלמנט אחד לפני סוף המערך, כי אנחנו כבר יודעים שהאלמנט הגדול ביותר (Hulk) נמצא לחלוטין במיקום הימני ביותר:
אז לתוכנית חייבת להיות שתי לולאות. לבהירות רבה יותר, לפני שנעבור לסקור את קוד התוכנית, אתה יכול להשתמש בקישור הזה כדי לראות הדמיה של אופן פעולת מיון הבועות: הדמיה של אופן פעולת מיון הבועות
IntelliJ IDE המועדף עליך. זה ינותח להלן:
מהירות האלגוריתם מושפעת לא רק ממספר המעברים, אלא גם ממספר התמורות שצריך לבצע. עבור נתונים אקראיים, מספר התמורות הוא ממוצע (N^2) / 4, שזה בערך חצי ממספר המעברים. עם זאת, במקרה הגרוע, מספר התמורות יכול להיות גם N^2 / 2 - זה המקרה אם הנתונים ממוינים בתחילה בסדר הפוך. למרות העובדה שמדובר באלגוריתם מיון איטי למדי, די חשוב לדעת ולהבין כיצד הוא עובד, וכאמור, הוא מהווה בסיס לאלגוריתם מורכבים יותר. Jgd!
מבוא
כל האינטרנט המודרני מורכב ממספר עצום של סוגים שונים של מבני נתונים שנאספים במסדי נתונים. הם מאחסנים כל מיני מידע, החל מנתונים אישיים של משתמשים ועד הליבה הסמנטית של מערכות אוטומטיות אינטליגנטיות במיוחד. מיותר לציין שמיון הנתונים ממלא תפקיד חשוב ביותר בכמות העצומה הזו של מידע מובנה. מיון יכול להיות שלב חובה לפני חיפוש מידע כלשהו במסד הנתונים, ולידע באלגוריתמי מיון יש תפקיד חשוב מאוד בתכנות.מיון דרך עיני מכונה ועיניים אנושיות
בואו נדמיין שצריך למיין 5 עמודות בגבהים שונים בסדר עולה. עמודות אלו יכולות להיות כל סוג של מידע (מחירי מניות, רוחב פס של ערוצי תקשורת וכו'); אתה יכול להציג כמה מהגרסאות שלך למשימה זו כדי להבהיר אותה יותר. ובכן, כדוגמה, נמיין את הנוקמים לפי גובה:בוצע!
וזה ישלים את המיון בהצלחה. עם זאת, המחשב, בניגוד אליך,- השוו שני אלמנטים;
- החלף או העתק אחד מהם;
- עבור לאלמנט הבא;
אלגוריתם מיון בועות
מיון הבועות נחשב לפשוט ביותר, אבל לפני שנתאר את האלגוריתם הזה, בואו נדמיין איך הייתם ממיינים את הנוקמים לפי גובה אם הייתם יכולים, כמו מכונה, להשוות רק שני גיבורים זה עם זה בפרק זמן אחד. סביר להניח שתעשה (האופטימלי ביותר) בדרך הבאה:- אתה עובר לאלמנט אפס של המערך שלנו (האלמנה השחורה);
- השווה את אלמנט האפס (האלמנה השחורה) עם הראשון (האלק);
- אם האלמנט במיקום אפס גבוה יותר, אתה מחליף אותם;
- אחרת, אם האלמנט במיקום אפס קטן יותר, אתה משאיר אותם במקומם;
- עבור למיקום ימינה וחזור על ההשוואה (השווה את האלק עם הקפטן)
יישום מיון בועות ב-Java
כדי להדגים כיצד מיון עובד ב-Java, הנה קוד התוכנית:- יוצר מערך של 5 אלמנטים;
- מעלה לתוכו את עליית הנוקמים;
- מציג את תוכן המערך;
- מיישם מיון בועות;
- מציג מחדש את המערך הממוין.
class ArrayBubble{
private long[] a; // array reference
private int elems; //number of elements in the array
public ArrayBubble(int max){ //class constructor
a = new long[max]; //create an array with size max
elems = 0; //when created, the array contains 0 elements
}
public void into(long value){ // method for inserting an element into an array
a[elems] = value; //insert value into array a
elems++; //array size increases
}
public void printer(){ // method for outputting an array to the console
for (int i = 0; i < elems; i++){ //for each element in the array
System.out.print(a[i] + " "); // output to console
System.out.println(""); //a new line
}
System.out.println("----End array output----");
}
private void toSwap(int first, int second){ //method swaps a pair of array numbers
long dummy = a[first]; // put the first element into a temporary variable
a[first] = a[second]; // put the second element in place of the first
a[second] = dummy; //instead of the second element, write the first from temporary memory
}
public void bubbleSorter(){ //МЕТОД ПУЗЫРЬКОВОЙ СОРТИРОВКИ
for (int out = elems - 1; out >= 1; out--){ //Outer loop
for (int in = 0; in < out; in++){ //Inner loop
if(a[in] > a[in + 1]) //If the order of the elements is wrong
toSwap(in, in + 1); // call the swapping method
}
}
}
}
public class Main {
public static void main(String[] args) {
ArrayBubble array = new ArrayBubble(5); //Create array array with 5 elements
array.into(163); //fill the array
array.into(300);
array.into(184);
array.into(191);
array.into(174);
array.printer(); //display elements before sorting
array.bubbleSorter(); //ИСПОЛЬЗУЕМ ПУЗЫРЬКОВУЮ СОРТИРОВКУ
array.printer(); // print the sorted list again
}
}
למרות ההערות המפורטות בקוד, אנו מספקים תיאור של חלק מהשיטות המוצגות בתוכנית. שיטות המפתח שמבצעות את העבודה העיקרית בתוכנית נכתבות במחלקה ArrayBubble. המחלקה מכילה בנאי ומספר שיטות:
into
- שיטת הכנסת אלמנטים למערך;printer
- מציג את תוכן המערך שורה אחר שורה;-
toSwap
- מסדר מחדש אלמנטים במידת הצורך. לשם כך, נעשה שימוש במשתנה זמניdummy
, שבו נכתב ערך המספר הראשון, ובמקום המספר הראשון נכתב הערך מהמספר השני. התוכן מהמשתנה הזמני נכתב למספר השני. זוהי טכניקה סטנדרטית להחלפת שני אלמנטים;ולבסוף השיטה העיקרית:
-
bubbleSorter
- שעושה את העבודה העיקרית וממיין את הנתונים המאוחסנים במערך, נציג אותם שוב בנפרד:public void bubbleSorter(){ //МЕТОД ПУЗЫРЬКОВОЙ СОРТИРОВКИ for (int out = elems - 1; out >= 1; out--){ //Outer loop for (int in = 0; in < out; in++){ //Inner loop if(a[in] > a[in + 1]) //If the order of the elements is wrong toSwap(in, in + 1); // call the swapping method } } }
out
ופנימי in
. המונה החיצוניout
מתחיל לספור ערכים מסוף המערך ויורד בהדרגה באחד עם כל מעבר חדש. out
עם כל מעבר חדש, המשתנה מוזז עוד יותר שמאלה כדי לא להשפיע על הערכים שכבר ממוינים בצד ימין של המערך. המונה הפנימיin
מתחיל לספור ערכים מתחילת המערך ועולה בהדרגה באחד בכל מעבר חדש. העלייה in
מתרחשת עד שהיא מגיעה out
(האלמנט המנותח האחרון במעבר הנוכחי). הלולאה הפנימית in
משווה בין שני תאים סמוכים in
ו- in+1
. אם in
מאוחסן מספר גדול יותר מ- in+1
, אז השיטה נקראת toSwap
, אשר מחליפה את המקומות של שני המספרים הללו.
GO TO FULL VERSION