מיון מעטפת בג'אווה
1. הקדמה
במדריך זה נתאר את אלגוריתם המיון של Shell ב- Java.
2. סקירת מיון המעטפת
2.1. תיאור
נתאר תחילה את אלגוריתם המיון של Shell כך שנדע מה אנו מנסים ליישם.
מיון מעטפת מבוסס על אלגוריתם מיון ההכנסה, והוא שייך לקבוצת האלגוריתמים היעילים ביותר. בכללי, האלגוריתם מפרק מערך מקורי לקבוצות משנה קטנות יותר ואז כל אחד מאלה ממוין באמצעות מיון הכנסה.
אבל, איך זה הופך את קבוצות המשנה אינו פשוט. הוא לא בוחר באלמנטים שכנים ליצור תת-קבוצה כפי שניתן היה לצפות. במקום זאת, מיון מעטפת משתמש במה שמכונה הַפסָקָה אוֹ פער ליצירת תת-קבוצות. למשל, אם יש לנו את הפער אני, זה אומר שתת-קבוצה אחת תכיל את האלמנטים שהם אני עמדות בנפרד.
ראשית, האלגוריתם ממיין את האלמנטים המרוחקים זה מזה. ואז, הפער הופך קטן יותר ומשווים אלמנטים קרובים יותר. בדרך זו, כמה אלמנטים שאינם נמצאים במיקום הנכון יכולים להיות ממוקמים מהר יותר מאשר אם היינו מייצרים את קבוצות המשנה מהאלמנטים הסמוכים.
2.2. דוגמה
בואו נראה זאת בדוגמה עם הפערים של 3 ו -1 והרשימה הלא ממוינת של 9 אלמנטים:
אם נעקוב אחר התיאור לעיל, באיטרציה הראשונה, יהיו לנו שלוש קבוצות משנה עם 3 אלמנטים (מודגשים באותו צבע):
לאחר מיון כל אחת מקבוצות המשנה באיטרציה הראשונה, הרשימה תיראה כך:
אנו יכולים לציין שלמרות שעדיין אין לנו רשימה ממוינת, האלמנטים קרובים יותר כעת למיקומים הרצויים.
לבסוף, עלינו לבצע מיון אחד נוסף עם תוספת של אחד וזה למעשה סוג הכנסה בסיסי. מספר פעולות ההעברה שעלינו לבצע כדי למיין רשימה קטן כעת מכפי שהיה קורה אם לא היינו מבצעים את החזרה הראשונה:
2.3. בחירת רצפי הפער
כפי שציינו, למיון המעטפת יש דרך ייחודית לבחור רצפי פער. זו משימה קשה ועלינו להיזהר שלא לבחור מעט מדי או יותר מדי פערים. ניתן למצוא פרטים נוספים ברשימת רצפי הפער המוצעים ביותר.
3. יישום
בואו נסתכל כעת על היישום. נשתמש ברצף המקורי של מעטפת במרווחי זמן:
N / 2, N / 4, ..., 1 (מחלקים ברציפות ב -2)היישום עצמו אינו מורכב מדי:
מיון חלל ציבורי (int arrayToSort []) {int n = arrayToSort.length; עבור (int פער = n / 2; פער> 0; פער / = 2) {עבור (int i = פער; i = פער && arrayToSort [j - פער]> מפתח) {arrayToSort [j] = arrayToSort [j - פער ]; j - = פער; } arrayToSort [j] = מקש; }}}תחילה יצרנו רצף פער עם לולאת for ואז עשינו את מיון ההכנסה לכל גודל פער.
כעת אנו יכולים לבדוק בקלות את השיטה שלנו:
@Test הציבור בטל givenUnsortedArray_whenShellSort_thenSortedAsc () {int [] קלט = {41, 15, 82, 5, 65, 19, 32, 43, 8}; ShellSort.sort (קלט); int [] צפוי = {5, 8, 15, 19, 32, 41, 43, 65, 82}; assertArrayEquals ("שני המערכים אינם שווים", צפוי, קלט); }4. מורכבות
בדרך כלל, אלגוריתם המיון של מעטפת יעיל מאוד ברשימות בינוניות. קשה לקבוע את המורכבות מכיוון שהיא תלויה רבות ברצף הפער, אך מורכבות הזמן משתנה בין עַל) ו O (N ^ 2).
מורכבות החלל במקרה הגרוע ביותר היא עַל) עם O (1) מרחב עזר.
5. מסקנה
במדריך זה תיארנו את מיון Shell והמחישנו כיצד אנו יכולים ליישם אותו ב- Java.
כרגיל, את כל הקוד ניתן היה למצוא ב- GitHub.
