מיון רדיקס בג'אווה
1. הקדמה
במדריך זה נלמד על Radix Sort, ננתח את ביצועיו ונבחן את יישומו.
כאן אנו מתמקדים בשימוש ב- Radix Sort למיון מספרים שלמים, אך זה לא מוגבל למספרים בלבד. אנו יכולים להשתמש בו כדי למיין סוגים אחרים כגון חוּט, גַם.
על מנת לשמור על הפשטות, נתמקד במערכת העשרונית בה המספרים באים לידי ביטוי בבסיס (רדיקס) 10.
2. סקירת אלגוריתם
מיון רדיקס הוא אלגוריתם מיון הממיין מספרים על סמך מיקומי הספרות שלהם. בעיקרון, הוא משתמש בערך המקום של הספרות במספר. בניגוד לרוב אלגוריתמי המיון האחרים, כגון מיזוג מיון, מיון הכנסה, מיון בועות, הוא אינו משווה את המספרים.
מיון Radix משתמש באלגוריתם מיון יציב כתת-דרך למיון הספרות. השתמשנו בווריאציה של מיון ספירה כתת-תחום כאן המשתמשת ברדיקס למיון הספרות בכל עמדה. ספירת מיון היא אלגוריתם מיון יציב והוא עובד היטב בפועל.
מיון רדיקס פועל על ידי מיון ספרות מהספרה הכי פחות משמעותית (LSD) לספרה המשמעותית ביותר (MSD). אנו יכולים גם ליישם מיון Radix כדי לעבד ספרות מ- MSD.
3. דוגמה מהירה
בואו נראה איך זה עובד עם דוגמא. בואו ניקח בחשבון את המערך הבא:
איטרציה 1:
אנו ממיין את המערך הזה על ידי עיבוד ספרות מ- LSD ועבר לכיוון MSD.
אז נתחיל עם הספרות במקום אחד:
לאחר האיטרציה הראשונה, המערך נראה כעת כמו:
שים לב שהמספרים סודרו לפי הספרות במקום אחד.
איטרציה 2:
נעבור לספרות במקום עשרות:
כעת המערך נראה כך:
אנו רואים שהמספר 7 תפס את המיקום הראשון במערך מכיוון שאין בו ספרה במקום העשרות. יכולנו לחשוב על זה כעל בעל 0 במקום העשרות.
איטרציה 3:
נעבור לספרות בעמדה מאות:
לאחר איטרציה זו, המערך נראה כך:
והאלגוריתם נעצר כאן, עם כל האלמנטים ממוינים.
4. יישום
בואו נסתכל עכשיו על היישום.
void sort (int [] numbers) {int maximumNumber = findMaximumNumberIn (numbers); int numberOfDigits = calcnumberOfDigitsIn (maximumNumber); int placeValue = 1; while (numberOfDigits--> 0) {applyCountingSortOn (numbers, placeValue); placeValue * = 10; }}האלגוריתם עובד על ידי מציאת המספר המקסימלי במערך ואז חישוב אורכו. שלב זה עוזר לנו להבטיח כי אנו מבצעים את תת-השגרה לכל ערך מקום.
לדוגמה, במערך, [7, 37, 68, 123, 134, 221, 387, 468, 769]המספר המרבי הוא 769 ואורכו 3.
לכן, אנו חוזרים ומיישמים את תת-הדרך שלוש פעמים על הספרות בכל עמדה:
void applyCountingSortOn (int [] numbers, int placeValue) {int range = 10 // system decimal, numbers from 0-9 // ... // חשב את תדירות הספרות עבור (int i = 0; i <length; i ++ ) {int digit = (numbers [i] / placeValue) טווח%; תדר [ספרה] ++; } עבור (int i = 1; i = 0; i--) {int digit = (numbers [i] / placeValue) טווח%; sortedValues [תדר [ספרה] - 1] = מספרים [i]; תדר [ספרה] -; } System.arraycopy (תוצאה, 0, מספרים, 0, אורך); } בתת-הפעולה השתמשנו ברדיקס (טווח) לספור את המופע של כל ספרה ולהגדיל את תדירותה. לכן, לכל סל בטווח שבין 0 ל -9 יהיה ערך כלשהו בהתבסס על תדירות הספרות. לאחר מכן אנו משתמשים בתדר כדי למקם כל אלמנט במערך. זה גם עוזר לנו למזער את השטח הנדרש למיון המערך.
עכשיו בואו לבדוק את השיטה שלנו:
@Test הציבור בטל givenUnsortedArray_whenRadixSort_thenArraySorted () {int [] numbers = {387, 468, 134, 123, 68, 221, 769, 37, 7}; RadixSort.sort (מספרים); int [] numbersSorted = {7, 37, 68, 123, 134, 221, 387, 468, 769}; assertArrayEquals (numbersSorted, numbers); }5. מיון רדיקס לעומת מיון ספירה
בתת-הדרך, אורכו של תדירות המערך הוא 10 (0-9). במקרה של ספירת מיון, איננו משתמשים ב- טווח. אורך ה- תדירות המערך יהיה המספר המקסימלי במערך + 1. לכן אנו לא מחלקים אותם לפחים ואילו Radix Sort משתמש במיכלי הפחים.
ספירת מיון יעילה למדי כאשר אורך המערך אינו קטן בהרבה מהערך המקסימלי במערך ואילו Radix Sort מאפשר ערכים גדולים יותר במערך.
6. מורכבות
הביצועים של Radix Sort תלויים באלגוריתם המיון היציב שנבחר למיון הספרות.
כאן השתמשנו במיון Radix כדי למיין מערך של נ מספרים בבסיס ב. במקרה שלנו הבסיס הוא 10. החלנו את מיון הספירה ד זמנים שבהם ד מייצג את מספר הספרות. אז מורכבות הזמן של Radix Sort הופכת להיות O (d * (n + b)).
מורכבות החלל היא O (n + b) מכיוון שהשתמשנו כאן בגרסה של ספירת מיון כתת-דרך.
7. מסקנה
במאמר זה תיארנו את אלגוריתם המיון של Radix והדגמנו כיצד ליישם אותו.
כרגיל, יישומי הקוד זמינים ב- Github.
