streamalism.org

1. סקירה כללית

במדריך זה נחקור את אלגוריתם QuickSort בפירוט, תוך התמקדות ביישום Java שלו.

נדון גם ביתרונות ובחסרונות שלה ואז ננתח את מורכבות הזמן שלה.

2. אלגוריתם QuickSort

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

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

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

לבסוף, כל רשימות המשנה הממוינות מתמזגות ליצירת הפלט הסופי.

2.1. שלבי אלגוריתם

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

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

בואו ניקח דוגמה פשוטה על מנת להבין טוב יותר את האלגוריתם הזה.

Arr [] = {5, 9, 4, 6, 5, 3}

1. נניח שאנחנו בוחרים 5 כציר לפשטות
2. ראשית נכניס את כל האלמנטים פחות מ -5 למיקום הראשון של המערך: {3, 4, 5, 6, 5, 9}
3. לאחר מכן נחזור על זה עבור מערך המשנה השמאלי {3,4}, ונקבל 3 כציר
4. אין אלמנטים פחות מ -3
5. אנו מיישמים סידור מהיר על מערך המשנה בצד ימין של הציר, כלומר {4}
6. מערך משנה זה מורכב מרכיב ממוין אחד בלבד
7. אנו ממשיכים עם החלק הימני של המערך המקורי, {6, 5, 9} עד שנקבל את המערך שהוזמן הסופי

2.2. בחירת הציר האופטימלי

הנקודה המכריעה ב- QuickSort היא לבחור את הציר הטוב ביותר. האלמנט האמצעי הוא, כמובן, הטוב ביותר, מכיוון שהוא יחלק את הרשימה לשתי רשימות משנה שוות.

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

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

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

אנו מקבלים את האינדקס של הציר הממוין ומשתמשים בו לשיחה רקורסיבית חֲלוּקָה() שיטה עם אותם פרמטרים כמו quickSort () שיטה, אך עם מדדים שונים:

חלל ציבורי quickSort (int arr [], int התחל, int סוף) {if (התחל <סוף) {int partitionIndex = מחיצה (arr, התחל, סוף); quickSort (arr, start, partitionIndex-1); quickSort (arr, partitionIndex + 1, סוף); }}

בוא נמשיך עם ה- חֲלוּקָה() שיטה. לשם פשטות, פונקציה זו לוקחת את האלמנט האחרון כציר. לאחר מכן, בדוק כל אלמנט והחלף אותו לפני הציר אם ערכו קטן יותר.

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

מחיצת אינטר פרטית (int arr [], int start, int end) {int pivot = arr [end]; int i = (התחל -1); עבור (int j = start; j <end; j ++) {if (arr [j] <= pivot) {i ++; int swapTemp = arr [i]; arr [i] = arr [j]; arr [j] = swapTemp; }} int swapTemp = arr [i + 1]; arr [i + 1] = arr [סוף]; arr [end] = swapTemp; החזר i + 1; }

4. ניתוח אלגוריתמים

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

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

במקרה הגרוע ביותר, האלגוריתם יבחר רק אלמנט אחד בכל איטרציה, כך O (n) + O (n-1) + ... + O (1), שהוא שווה ל- O (n2).

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

4.2. QuickSort לעומת MergeSort

בואו נדון באילו מקרים עלינו לבחור ב- QuickSort על פני MergeSort.

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

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

במקרה כזה, בדרך כלל עדיף עליות תקורה עבור Quicksort ו- Mergesort.

5. מסקנה

Quicksort הוא אלגוריתם מיון אלגנטי שמאוד שימושי ברוב המקרים.

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

נקודה מעניינת נוספת להזכיר היא של ג'אווה Arrays.sort () השיטה משתמשת ב- Quicksort למיון מערכים של פרימיטיבים. היישום משתמש בשני צירים ומתפקד הרבה יותר טוב מהפתרון הפשוט שלנו, ולכן עבור קוד ייצור בדרך כלל עדיף להשתמש בשיטות ספרייה.

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