streamalism.org

1. הקדמה

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

2. תורת מיון הדלי

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

בואו נסתכל במהירות על ה- הצעדים הנדרשים לביצוע מיון דלי:

1. הגדר מערך של הדליים הריקים שלנו בתחילה
2. הפץ את האלמנטים שלנו לדליים המתאימים שלהם
3. ממיין כל דלי
4. לשרשר את הדליים הממוינים יחד כדי ליצור מחדש את הרשימה המלאה

3. יישום ג'אווה

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

3.1. הגדרת דלי

ראשית, אנחנו צריך לקבוע אלגוריתם hashing להחליט אילו מהאלמנטים שלנו יושמו באיזה דלי:

hash int פרטי (int i, int max, int numberOfBuckets) {return (int) ((double) i / max * (numberOfBuckets - 1)); }

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

int int finalOfBuckets = (int) Math.sqrt (initialList.size ()); רשימה דליים = ArrayList חדש (numberOfBuckets); עבור (int i = 0; i <numberOfBuckets; i ++) {buckets.add (ArrayList חדש ()); }

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

private int findMax (קלט רשימה) {int m = Integer.MIN_VALUE; עבור (int i: קלט) {m = Math.max (i, m); } להחזיר מ '; }

3.2. הפצת האלמנטים

כעת, לאחר שהגדרנו את הדליים שלנו, נוכל לעשות זאת הפץ כל אלמנט ברשימת הקלט שלנו לדלי הרלוונטי שלו באמצעות ה- בְּלִיל שיטה:

int max = findMax (initialList); עבור (int i: initialList) {buckets.get (hash (i, max, numberOfBuckets)). הוסף (i); } 

3.3. מיון הדליים האישיים

עם הדליים שלנו מוגדרים ומלאים במספרים שלמים, בואו נשתמש ב- משווה למיין אותם:

משווה השוואה = Comparator.naturalOrder (); עבור (רשימה דלי: דליים) {bucket.sort (משווה); }

3.4. שרשור הדליים שלנו

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

List sortedArray = חדש LinkedList (); עבור (רשימת דלי: דליים) {sortedArray.addAll (דלי); } להחזיר sortedArray;

4. בדיקת הקוד שלנו

עם השלמת היישום, בוא נכתוב מבחן יחידה מהיר כדי לוודא שהוא עובד כצפוי:

סדרן BucketSorter = IntegerBucketSorter חדש); רשימה לא ממוינת = Arrays.asList (80,50,60,30,20,10,70,0,40,500,600,602,200,15); רשימה צפויה = Arrays.asList (0,10,15,20,30,40,50,60,70,80,200,500,600,602); List sorted = sorter.sort (לא ממוין); assertEquals (צפוי, ממוין);

5. מורכבות זמן

לאחר מכן, בואו נסתכל במהירות על מורכבות הזמן בביצוע מיון דלי.

5.1. במקרה הגרוע ביותר

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

5.2. תרחיש מקרים ממוצע

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

6. מסקנה

במאמר זה ראינו כיצד ליישם מיון דלי ב- Java. בדקנו גם את מורכבות הזמן של אלגוריתם מיון הדלי.

כמו תמיד, הקוד המוצג במאמר זה זמין ב- GitHub.