אפר׳ 8

מיון איברים- עזרה

1 תגובות

היי,

איך ממשים מיון בועות ב-Java? והאם הוא המיון הכי יעיל שיש היום במערכים?

הדר

 

אפר׳ 14

היי הדר,

בקשר לאיך מממשים את מיון הבועות (ידוע גם כ-Bubble Sort):

במיון בועות, בכל סבב i של הלולאה החיצונית אנחנו שמים במקומו (כלומר, אם גודל המערך הוא N, בתום הסבב איבר המדובר יהיה במקום הN - i במערך) את האיבר ה-i הכי גדול במערך. עושים זאת ע"י כך שמריצים עוד לולאה (לולאה פנימית) מ-0 (המקום הראשון במערך) ועד N - i - 1. בכל סבב של הלולאה הפנימית האנחנו משווים בין 2 איברים - a[j] ו-a[j + 1] (כאשר j הוא האינדקס של ה-for הפנימי). אם הם כבר ממויינים (כלומר האיבר ה-j קטן מהאיבר שאחרי), ממשיכים הלאה, לסבב הבא של הלולאה הפנימית. אם לא, מחליפים אותם.

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

(כשאני אומרת "רצים" אני מתכוונת שאנחנו מקדמים את האיבר ביחד עם ה-j שלנו לאורך המערך ע"י החלפת הערך שלו ושל ההבא אחריו).

 

 

אני מצרפת קישור לאתר אינטרנטי (באנגלית) שמצאתי ע"י הקלדת הצירוף "Bubble Sort Java" בגוגל (יש שם עוד אפשרויות, מוזמנת לנסות לחפש בעצמך אם יתברר שהקישור לא טוב, אבל ממה שראיתי במבט ראשון האתר מסביר טוב). יש שם את הקוד למיון בועות בעוד שפות, תבחרי בג'אווה (ברירת המחדל היא C).

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

 

בקשר לשאלה השניה, מיון בועות הוא *לא* המיון הכי יעיל מבחינת זמנים:

מיון בועות רץ (במקרה הכי גרוע) N^2 פעמים (N אורך המערך), ומיון מיזוג (Merge Sort) רץ במקרה הכי גרוע N*log(N) פעמים (אבל שימי לב שסיבוכיות המקום של מיון המיזוג היא N, בניגוד לסיבוכיות מקום 1 במיונים האחרים).

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

 

 

 

קישור למיון בועות:

https://www.geeksforgeeks.org/bubble-sort/

 

קישור למיון מיזוג:

https://www.geeksforgeeks.org/merge-sort/

 

 

בהצלחה!

אופיר.

Newest Posts
  • היי, יש לי עבודת בית ואשמח אם תעזרו לי :) והעבודה היא : להביא 2 הבדלים בין מערך לרשימה מקושרת.
  • היי יש לי מבחן במדעי המחשב ואשמח לעזרה בכמה שאלות - 1. מה זאת שפה רגולרית? האם אוטומט סופי דטרמיניסטי נחשב לשפה רגולרית? 2. כאשר שואלים אותי על האיבר האחרון במחסנית- הכוונה לראשון שנכנס? 3. מה זה Node? 4. איך יודעים מה הסיבוכיות/סדר הגודל של פעולה על מחסנית 5. איך אני כותבת פעולה שמקבלת מחסנית עם רצפים של מספרים ומחזירה את אותה מחסנית רק עם מופע אחד לכל מספר תודה מראש על העזרה!
  • היי קוראים לי ענבל, תלמידת כיתה יא במגמת מדעי המחשב ותוכנית הקלאב. לאחרונה התעניינתי בבניית משחק מציאות מדומה אך לצערי מצאתי רק תוכנה אחת חינמית והיא כולה בשפת c ואני לומדת java ו pycharm. אשמח אם מישהי שהתנסתה בנושא בעבר תוכל להמליץ לי על תוכנה

עוצב ונבנה ע״י Kukushka

© 2018 כל הזכויות שמורות לסייברגירלז