סקירה ובדיקה של שיטות מיון. חלק א'

לפני כמה ימים, בהערות ב-VKontakte, היה לי ויכוח עם אחד מהתלמידים האחרים של הפרויקט. מהות המחלוקת הייתה "מי ינצח" - שיטה sort()ממחלקה java.util.Arraysאו מימושים שנכתבו בעצמם של אלגוריתמים פשוטים: בועה , הכנסה , בחירה , מעטפת (אלגוריתם מעטפת). עבור חלקם, התשובה לשאלה זו עשויה להיות ברורה, אך מאחר שהמחלוקת התעוררה, למרות שלכל צד היו "מקורות מכובדים" לטובת נקודת המבט שלו, הוחלט לערוך מחקר, למתוח את העניין האפור ב. התהליך, יישום אלגוריתמים שונים. TL;DR: java.util.Arrays.sort() היא ללא תנאי המובילה במערכים של 100,000 אלמנטים או יותר; עם גודל קטן יותר, שיטת Shell יכולה לפעמים להתחרות בה. שאר האלגוריתמים הנחשבים ריקים לחלוטין ויכולים להיות שימושיים רק בתנאים אקזוטיים מסוימים. עכשיו בואו נסתכל כיצד ממוינים מערכים במכשירי הסיליקון שלנו.

מיון בחירה. מיון לפי בחירה

נתחיל בשיטה הפשוטה והברורה ביותר. המהות של זה מודגמת לנו בצורה מושלמת על ידי רוברט סדג'וויק בהרצאת הווידאו שלו על קורסרה (אצטט משם את האנימציה שדחסתי בצורה גרועה לגיף): View Running through the array from the first element, at every step we חפש את האלמנט המינימלי בצד ימין, איתו אנו מחליפים את הנוכחי. כתוצאה מכך, אנו שומרים את הגרסה הסופית של המערך שלנו בצורה ממוינת. הנה הקוד שמיישם את האלגוריתם הזה ב-Java:

public void sort(int[] array) {
        int n = array.length;
        for (int i = 0; i < n; i ++) {
            int minIndex = min(array, i, n - 1);
            swap(array, i, minIndex);
        }
    }

public static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
public static int min(int[] array, int begin, int end) {
        int minVal = array[begin];
        int minIndex = begin;
        for (int i = begin + 1; i <= end; i++) {
            if (array[i] < minVal) {
                minVal = array[i];
                minIndex = i;
            }
        }
        return minIndex;
    }

ניתוח האלגוריתם מראה שיש צורך לסרוק את שאר המערך בכל מעבר, כלומר, נצטרך בדיוק N + (N-1) + (N-2) + ... + 1 = N^ 2/2 השוואות. לפיכך, המורכבות של האלגוריתם היא O(N^2). מה זה אומר? המשמעות היא שעל ידי הגדלת מספר האלמנטים במערך (N) פי 2, נגדיל את זמן הריצה של האלגוריתם לא ב-2, אלא ב-2^2 = פי 4. על ידי הגדלת N פי 10, נגדיל את זמן הפעולה פי 100, וכן הלאה. במחשב הנייד שלי 2012 עם מעבד Core i3 המריץ אובונטו 14.4, קיבלתי את זמן הפעולה הבא:

מיון הכנסה. מיון הכנסה

כאן הרעיון מעט שונה. שוב, בואו נפנה לאנימציה של דוקטור סדג'וויק: View What is ahead אפילו לא נצפה על ידינו עדיין, וכל מה שאנחנו משאירים מאחור תמיד נשאר מסודר. הנקודה היא שאנחנו "מחזירים" כל אלמנט חדש של המערך המקורי להתחלה עד שהוא "נשען" על אלמנט קטן יותר. לפיכך, שוב יש לנו N מעברים (עבור כל רכיב של המערך המקורי), אבל בכל מעבר, ברוב המקרים, אנחנו לא מסתכלים על כל השאר, אלא רק על חלק. כלומר, נקבל אפשרות 1 + (N-1) + (N-2) + … + N = N^2/2 רק אם נצטרך להחזיר כל אלמנט הבא להתחלה, כלומר במקרה של הקלט ממוין מערך "בהפוך" (חוסר מזל, חסר מזל). במקרה של מערך שכבר ממוין (הנה מזל) יהיה חינמי מוחלט - בכל מעבר יש השוואה אחת בלבד ומשאיר את האלמנט במקומו, כלומר האלגוריתם יעבוד בזמן פרופורציונלי ל-N. המורכבות של האלגוריתם ייקבע לפי המקרה התיאורטי הגרוע ביותר, כלומר O( N^2). בממוצע, זמן הפעולה יהיה פרופורציונלי ל-N^2/4, כלומר מהיר פי שניים מהאלגוריתם הקודם. ביישום שלי, בגלל השימוש הלא אופטימלי בתמורה, זמן הריצה היה ארוך יותר מזה של Selection. אני מתכוון לתקן ולעדכן את הפוסט בקרוב. להלן הקוד והתוצאה של פעולתו על אותה מכונה:

public void sort(int[] array) {
        int length = array.length;
        for (int i = 1; i < length; i++) {
            for (int j = i; j >= 1; j--) {
                if (array[j] < array[j - 1])
                    swap(array, j, j - 1);
                else
                    break;
            }
        }
    }

מיון מעטפת. מיון מעטפת

בחור חכם, דונלד של, הבחין כבר ב-1959 שהמקרים היקרים ביותר באלגוריתם להכנסות הם כאשר האלמנט חוזר רחוק מאוד לתחילת המערך: במעבר כלשהו אנו מחזירים את האלמנט להתחלה בכמה מיקומים , ובמעבר אחר כמעט דרך כל המערך להתחלה הוא רחוק וארוך. האם ניתן לעשות זאת בבת אחת, לדלג על מספר אלמנטים? והוא מצא דרך כזו. זה מורכב מביצוע מיון חלקי מיוחד ברצף, הנקרא בדרך כלל d-sort או, לפי Sedgwick, h-sort (אני חושד ש-h פירושו הופ). 3-sort, למשל, ישווה את האלמנט המדובר לא עם הקודם, אלא ידלג על שניים וישווה לאחד 3 עמדות אחורה. אם ישתנה, הוא ישווה אותו שוב עם האלמנט 3 מיקומים אחורה וכן הלאה. השורה התחתונה היא שהמערך שיתקבל יהיה "ממוין 3", כלומר, המיקום השגוי של האלמנטים יהיה פחות מ-3 מיקומים. העבודה עם אלגוריתם ההכנסה הזה תהיה קלה ונעימה. אגב, "1-sort" הוא לא יותר מסתם אלגוריתם הכנסה =) על ידי החלת h-sort ברצף על המערך עם ערכי h יורדים, נוכל למיין מערך גדול מהר יותר. כך זה נראה: צפה האתגר כאן הוא כיצד לבחור את הרצף הנכון של מיונים חלקיים. בסופו של דבר, ביצועי האלגוריתם תלויים בכך. הנפוץ ביותר הוא הרצף שהציע דונלד קנות: h = h*3 + 1, כלומר 1, 4, 13, 40, ... וכן הלאה עד 1/3 מגודל המערך. רצף זה מספק ביצועים נאותים והוא גם קל ליישום. ניתוח האלגוריתם דורש טונות של שפה והוא מעבר ליכולתי. רוחב הניתוח נקבע גם על ידי הווריאציות הרבות של רצפי h. מבחינה אמפירית, אנו יכולים לומר שמהירות האלגוריתם טובה מאוד - ראו בעצמכם: מיליון אלמנטים בפחות משנייה! והנה קוד Java עם רצף Knut.

public void sort(int[] array) {
        int h = 1;
        while (h*3 < array.length)
            h = h * 3 + 1;

        while(h >= 1) {
            hSort(array, h);
            h = h/3;
        }
    }

    private void hSort(int[] array, int h) {
        int length = array.length;
        for (int i = h; i < length; i++) {
            for (int j = i; j >= h; j = j - h) {
                if (array[j] < array[j - h])
                    swap(array, j, j - h);
                else
                    break;
            }
        }
    }

מיון בועות. שיטת בועה

זו קלאסיקה! כמעט כל מתכנת מתחיל מיישם את האלגוריתם הזה. זה כל כך קלאסי שלד"ר סדג'וויק אפילו לא הייתה אנימציה לזה, אז הייתי צריך לעשות את העבודה בעצמי. צפה כאן, בכל מעבר, אנו חוצים את המערך מתחילתו ועד סופו, מחליפים אלמנטים שכנים שאינם תקינים. כתוצאה מכך, האלמנטים הגדולים ביותר "צפים" (ומכאן השם) לסוף המערך. אנחנו מתחילים כל מעבר חדש באופטימיות בתקווה שהמערך כבר ממוין ( sorted = true). בסוף הקטע, אם אנו רואים שטעינו, מתחילים קטע חדש. הקושי כאן הוא ששוב, אנו חוצים (כמעט) את כל המערך בכל מעבר. ההשוואה מתרחשת בכל שלב, החלפה מתרחשת כמעט בכל שלב, מה שהופך את האלגוריתם הזה לאחד האיטיים ביותר (אם ניקח בחשבון מיושמים באופן רציונלי, ולא "מיין רועד" ואחרים כאלה). מעניין שבאופן פורמלי המורכבות כאן תהיה שווה גם ל-O(N^2), אבל המקדם גבוה בהרבה מזה של הוספות ובחירות. קוד אלגוריתם:

public void sort(int[] array) {
        boolean isSorted;
        int nMinusOne = array.length - 1;
        for(int i = 0; i < nMinusOne; i++) {
            isSorted = true;
            for (int j = 0; j < nMinusOne - i; j++) {
                if (array[j] > array[j + 1]) {
                    swap(array, j, j + 1);
                    isSorted = false;
                }
            }
            if (isSorted)
                return;
        }
    }

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

תקציר החלק הראשון

כתוצאה מכך, אני מציע להסתכל בטבלה הכללית עבור אלגוריתמים אלה. אתה יכול גם להשוות עם התוצאות עבור השיטה המובנית java.util.Arrays.sort(). זה נראה כמו סוג של קסם - מה יכול להיות מהיר יותר מ-Shell? אכתוב על כך בחלק הבא. שם נסתכל על אלגוריתמי מיון מהיר בשימוש נרחב, כמו גם מיון מיזוג, נלמד על ההבדל בשיטות מיון מערכים מפרימיטיבים וסוגי התייחסות, וגם נכיר ממשק חשוב מאוד בעניין זה Comparable;) למטה תוכלו ללמוד גרף בנוי בקנה מידה לוגריתמי באמצעות טבלאות נתונים. ככל שהקו שטוח יותר, כך האלגוריתם טוב יותר =) למי שרוצה להוריד את כל הפרויקט ולהריץ בדיקות בעצמו, שמור על הקישור: Java נתראה בחלק הבא! =)