מיון הכנסה ב- Java
1. סקירה כללית
במדריך זה נדון אלגוריתם מיון ההוספה והסתכל על יישום Java שלו.
מיון הכניסה הוא אלגוריתם יעיל להזמנת מספר קטן של פריטים. שיטה זו מבוססת על האופן שבו שחקני הקלפים ממיינים יד של קלפי משחק.
אנחנו מתחילים ביד שמאל ריקה והקלפים מונחים על השולחן. לאחר מכן אנו מוציאים כרטיס אחד בכל פעם מהשולחן ומכניסים אותו למצב הנכון ביד שמאל. כדי למצוא את המיקום הנכון לכרטיס חדש, אנו משווים אותו עם קבוצת הקלפים הממוינת כבר ביד, מימין לשמאל.
נתחיל בהבנת שלבי האלגוריתם בצורה פסאודוקוד.
2. פסאודוקוד
אנו נציג את הפסאודוקוד שלנו למיון הכנסה כנוהל שנקרא מיון הכנסה, לוקח כפרמטר מערך A [1 .. n] של n פריטים למיון. האלגוריתם ממיין את מערך הקלט במקום (על ידי סידור מחדש של הפריטים במערך A).
לאחר סיום ההליך, מערך הקלט A מכיל תמורה של רצף הקלט אך בסדר ממוין:
INSERTION-SORT (A) עבור i = 2 עד A. מקש אורך = A [i] j = i - 1 בעוד j> 0 ו- A [j]> מקש A [j + 1] = A [j] j = j - 1 A [j + 1] = מקשבואו נעבור בקצרה על האלגוריתם שלמעלה.
המדד אני מציין את המיקום של הפריט הנוכחי במערך לעיבוד.
אנו מתחילים מהפריט השני שכן בהגדרה מערך עם פריט אחד נחשב למיון. הפריט באינדקס אני נקרא a מַפְתֵחַ. ברגע שיש את מַפְתֵחַ, החלק השני של האלגוריתם עוסק במציאת האינדקס הנכון שלו. אם ה מַפְתֵחַ קטן מערך הפריט באינדקס יואז המפתח מעביר מיקום אחד שמאלה. התהליך נמשך עד למקרה בו נגיע לאלמנט הקטן מהמפתח.
חשוב לציין כי לפני שמתחילים איטרציה למציאת המיקום הנכון של ה- מַפְתֵחַ באינדקס אני, המערך A [1 .. j - 1] כבר מְמוּיָן.
3. יישום הכרחי
במקרה הכרח, אנו נכתוב פונקציה שנקראת insertionSortImperative, לוקח פרמטר מערך של מספרים שלמים. הפונקציה מתחילה לחזור על המערך מהפריט השני.
בכל זמן נתון במהלך החזרה, יכולנו לחשוב על מערך זה כמחולק באופן הגיוני לשני חלקים; הצד השמאלי הוא הצד הממוין והצד הימני המכיל את הפריטים שעדיין לא ממוינים.
הערה חשובה כאן היא שאחרי שנמצא את המיקום הנכון בו נכניס את הפריט החדש, אנו מעבירים (ולא מחליפים) את הפריטים ימינה לפנות מקום עבורה.
הכנסת חלל סטטי ציבוריSortImperative (int [] קלט) {for (int i = 1; i = 0 && קלט [j]> מקש) {קלט [j + 1] = קלט [j]; j = j - 1; } קלט [j + 1] = מקש; }} לאחר מכן, בואו ניצור מבחן לשיטה לעיל:
@Test הציבור בטל givenUnsortedArray_whenInsertionSortImperative_thenSortedAsc () {int [] קלט = {6, 2, 3, 4, 5, 1}; InsertionSort.insertionSortImperative (קלט); int [] צפוי = {1, 2, 3, 4, 5, 6}; assertArrayEquals ("שני המערכים אינם שווים", צפוי, קלט); }הבדיקה שלעיל מוכיחה שהאלגוריתם ממיין נכון בסדר עולה במערך הקלט .
4. יישום רקורסיבי
הפונקציה למקרה הרקורסיבי נקראת insertionSortRאקורסיבי ומקבל כקלט מערך שלם (זהה למקרה הכרחי).
ההבדל כאן מהמקרה הציווי (למרות העובדה שהוא רקורסיבי) הוא שזה קורא לפונקציה עמוסה עם ארגומנט שני השווה למספר הפריטים למיון.
כשאנחנו רוצים למיין את המערך השלם, נעביר מספר פריטים שווים לאורכם:
החדרת חלל סטטי ציבוריSortRecursive (קלט int []) {insertionSortRecursive (קלט, input.length); }המקרה הרקורסיבי קצת יותר מאתגר. המקרה הבסיסי מתרחש כאשר אנו מנסים למיין מערך עם פריט אחד. במקרה זה, אנחנו לא עושים כלום.
כל השיחות הרקורסיביות הבאות ממיינות חלק שהוגדר מראש במערך הקלט - החל מהפריט השני עד שנגיע לסוף המערך:
הכנסת חלל סטטי פרטיתSortRecursive (קלט int [], int i) {if (i <= 1) {return; } insertionSortRecursive (קלט, i - 1); מקש int = קלט [i - 1]; int j = i - 2; ואילו (j> = 0 && קלט [j]> מקש) {קלט [j + 1] = קלט [j]; j = j - 1; } קלט [j + 1] = מקש; }וכך נראה ערימת השיחות עבור מערך קלט של 6 פריטים:
insertionSortRecursive (קלט, 6) insertionSortRecursive (קלט, 5) והכנס את הפריט השישי למערך הממוין insertionSortRecursive (קלט, 4) והכנס את הפריט החמישי לתוך הכניסה למערך הממויןortRecursive (קלט, 3) והכנס את הפריט הרביעי למיין הכנס מערךSortRecursive (קלט, 2) והכנס את הפריט השלישי למערך הממוין insertionSortRecursive (קלט, 1) והכנס את הפריט השני למערך הממויןבואו נראה גם את המבחן לכך:
@Test הציבור בטל givenUnsortedArray_whenInsertionSortRecursively_thenSortedAsc () {int [] קלט = {6, 4, 5, 2, 3, 1}; InsertionSort.insertionSortRecursive (קלט); int [] צפוי = {1, 2, 3, 4, 5, 6}; assertArrayEquals ("שני המערכים אינם שווים", צפוי, קלט); }הבדיקה שלעיל מוכיחה שהאלגוריתם ממיין נכון בסדר עולה במערך הקלט .
5. מורכבות זמן ומרחב
הזמן שלקח מיון הכנסה ההליך להפעיל הוא O (n ^ 2). עבור כל פריט חדש, אנו חוזרים מימין לשמאל על החלק הממוין כבר במערך כדי למצוא את מיקומו הנכון. ואז אנו מכניסים אותו על ידי הסטת הפריטים מיקום אחד ימינה.
האלגוריתם ממיין במקום אז שלו מורכבות החלל היא O (1) ליישום הכרחית ו עַל) ליישום רקורסיבי.
6. מסקנה
במדריך זה ראינו כיצד ליישם מיון הכנסה.
אלגוריתם זה שימושי למיון מספר קטן של פריטים. זה הופך ליעיל בעת מיון רצפי קלט עם יותר מ -100 פריטים.
יש לזכור שלמרות המורכבות הריבועית שלו הוא ממיין במקום ללא צורך במרחב עזר כפי שקורה מיזוג מיון.
ניתן היה למצוא את הקוד כולו ב- GitHub.
