מדריך לאלגוריתם מיון במקום עם יישום Java
1. הקדמה
במדריך זה נסביר כיצד פועל אלגוריתם המיון במקום.
2. אלגוריתמים במקום
האלגוריתמים במקום הם כאלה שאינם זקוקים למבנה נתונים עזר כלשהו בכדי להפוך את נתוני הקלט. בעיקרון, המשמעות היא שהאלגוריתם אינו משתמש במרחב נוסף לצורך מניפולציה בקלט. זה כמעט עוקף את הקלט עם הפלט.
עם זאת, במציאות, האלגוריתם עשוי לדרוש מקום נוסף קטן ולא קבוע עבור משתני עזר. המורכבות של מרחב זה היא ברוב המקרים O (יומן n), אם כי לפעמים מותר לכל דבר פחות מליניארי.
3. פסאודוקוד
בואו עכשיו נראה איזה פסאוד-קוד ונשווה את האלגוריתם במקום לזה שאינו במקום.
נניח שאנחנו רוצים להפוך מערך של נ מספרים.
3.1. אלגוריתם במקום
אם נחשוב על הבעיה, נראה שיש לנו מערך קלט ומערך הפוך כפלט. בסופו של דבר איננו זקוקים למערך המקורי שלנו, אלא רק למערך ההפוך.
ואז, מדוע שלא נדרוס את הקלט במקום להעביר את הערכים שלו למערך החדש לחלוטין, מכיוון שהוא עשוי להראות כמו שיטה ברורה ביותר? לעשות את זה, נצטרך רק משתנה נוסף אחד לאחסון זמני של הערכים שאיתם אנו עובדים כעת:
reversInPlace (מערך A [n]) עבור i מ- 0 ל- n / 2 temp = A [i] A [i] = A [n - 1 - i] A [n - 1 - i] = tempראוי לציין כי לא משנה כמה גדול המערך, השטח הנוסף שאנחנו צריכים תמיד יהיה O (1) במקרה הזה.
האיור מראה שאנחנו צריכים פחות צעדים מאשר במקרה הקודם:
3.2. אלגוריתם מחוץ למקום
מצד שני, אנו יכולים לעשות זאת בצורה די פשוטה, ברורה יותר. אנו יכולים ליצור מערך חדש באותו גודל, להעתיק את הערכים מהמקור בסדר המתאים ואז למחוק את המערך המקורי:
reverseOutOfPlace (מערך A [n]) צור מערך חדש B [n] עבור i מ- 0 ל- n - 1 B [i] = A [i] מחק A החזר Bלמרות שזה יעשה את מה שרצינו שהוא יעשה, זה לא יעיל מספיק. יש לנו עַל) נדרש מקום נוסףמכיוון שיש לנו שני מערכים להתמודד איתם. חוץ מזה, יצירת והסרה של מערך חדש היא בדרך כלל פעולה איטית.
בואו נראה את האיור של התהליך:
4. יישום ג'אווה
בואו נראה כעת כיצד נוכל ליישם ב- Java את מה שלמדנו בחלק הקודם.
ראשית, אנו מיישמים אלגוריתם במקום:
intic public int [] reverseInPlace (int A []) {int n = A.length; עבור (int i = 0; i <n / 2; i ++) {int temp = A [i]; A [i] = A [n - 1 - i]; A [n - 1 - i] = temp; } להחזיר A; }אנו יכולים לבדוק בקלות שזה עובד כמצופה:
@Test הציבור בטל givenArray_whenInPlaceSort_thenReversed () {int [] קלט = {1, 2, 3, 4, 5, 6, 7}; int [] צפוי = {7, 6, 5, 4, 3, 2, 1}; assertArrayEquals ("שני המערכים אינם שווים", צפוי, InOutSort.reverseInPlace (קלט)); }שנית, בואו נבדוק את יישום האלגוריתם שלא במקום:
intic public int [] reverseOutOfPlace (int A []) {int n = A.length; int [] B = int int [n]; עבור (int i = 0; i <n; i ++) {B [n - i - 1] = A [i]; } להחזיר ב '; }המבחן די פשוט:
@ מבט פומבי בטל givenArray_whenOutOfPlaceSort_thenReversed () {int [] קלט = {1, 2, 3, 4, 5, 6, 7}; int [] צפוי = {7, 6, 5, 4, 3, 2, 1}; assertArrayEquals ("שני המערכים אינם שווים", צפוי, InOutSort.reverseOutOfPlace (קלט)); }5. דוגמאות
ישנם אלגוריתמי מיון רבים המשתמשים בגישה במקום. חלקם הם מיון הכנסה, מיון בועות, מיון ערימה, מיון קווקס, ומיון פגזים ותוכלו ללמוד עליהם יותר ולבדוק את יישומי Java שלהם.
כמו כן, עלינו להזכיר מיון מסרק ומספר גדול. לכל אלה מורכבות שטח O (יומן n).
זה יכול להיות שימושי ללמוד עוד על תיאוריית ה- Big-O Notation, כמו גם לבדוק כמה דוגמאות מעשיות של Java על מורכבות האלגוריתם.
6. מסקנה
במאמר זה, תיארנו את האלגוריתמים במקום שנקרא, המחישנו כיצד הם עובדים באמצעות פסאודוקוד וכמה דוגמאות, רשימנו כמה אלגוריתמים שעובדים על עיקרון זה, ולבסוף יישמנו את הדוגמאות הבסיסיות בג'אווה.
כרגיל, את כל הקוד ניתן היה למצוא ב- GitHub.
