אלגוריתמי מיון בתיאוריה ובפועל

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

מבוא

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

int[] array = {10, 2, 10, 3, 1, 2, 5};
for (int i = 0; i < array.length; i++) {
	System.out.println(array[i]);
}

מה ניתן לומר על קטע קוד זה? יש לנו לולאה בה אנו משנים את האינדקס ( int i) מ-0 לאלמנט האחרון במערך. למעשה, אנחנו פשוט לוקחים כל רכיב במערך ומדפיסים את תוכנו. ככל שיש יותר אלמנטים במערך, כך ייקח לקוד זמן רב יותר לסיום. כלומר, אם nהוא מספר האלמנטים, כאשר n = 10התוכנית ייקח זמן רב פי שניים לרוץ מאשר כאשר n = 5. אם לתוכנית שלנו יש לולאה אחת, זמן הביצוע גדל באופן ליניארי: ככל שיש יותר אלמנטים, זמן הביצוע ארוך יותר. מסתבר שהאלגוריתם שלמעלה עובד בזמן ליניארי (פונקציה לינארית של n). במקרים כאלה, אנו אומרים שהמורכבות של האלגוריתם היא "O(n)". סימון זה נקרא גם "Big O" או "התנהגות אסימפטוטית". אבל אתה יכול פשוט לזכור את "מורכבות האלגוריתם".

אלגוריתם המיון הפשוט ביותר (מיון בועות)

נניח שיש לנו מערך ואנחנו יכולים לחזור עליו. גדול. עכשיו בואו ננסה למיין אותו בסדר עולה. מה זה אומר? זה אומר שבהינתן שני אלמנטים (לדוגמה, a = 6, b = 5), עלינו לסדר מחדש aואם גדול מ- (אם ). מה זה אומר כשאנחנו משתמשים באינדקס כדי לעבוד עם אוסף (כפי שקורה עם מערך)? זה אומר שאם האלמנט עם האינדקס a גדול מהאלמנט עם האינדקס ( ), אז יש להחליף את האלמנטים. ישנן דרכים שונות לשנות מקום. אבל נשתמש בטכניקה פשוטה, מובנת וקלה לזכור: baba > bbarray[a] > array[b]

private void swap(int[] array, int ind1, int ind2) {
    int tmp = array[ind1];
    array[ind1] = array[ind2];
    array[ind2] = tmp;
}

כעת נוכל לכתוב את הדברים הבאים:

int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int i = 1; i < array.length; i++) {
	if (array[i] < array[i - 1]) {
		swap(array, i, i-1);
	}
}
System.out.println(Arrays.toString(array));

כפי שאתה יכול לראות, האלמנטים באמת הוחלפו. התחלנו עם אינדקס 1, כי אם למערך יש רק אלמנט אחד, הביטוי array[i] < array[i-1]אינו חוקי עבור index 0. פעולה זו גם מגינה עלינו ממקרים שבהם למערך אין אלמנטים או רק אלמנט אחד, וזה גורם לקוד להיראות טוב יותר. אבל המערך שהתקבל עדיין לא ממוין, כי מעבר אחד לא מספיק כדי לבצע את המיון. נצטרך להוסיף עוד לולאה שבה נבצע מעברים שוב ושוב עד שנקבל מערך ממוין:

int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
boolean needIteration = true;
while (needIteration) {
	needIteration = false;
	for (int i = 1; i < array.length; i++) {
		if (array[i] < array[i - 1]) {
			swap(array, i, i-1);
			needIteration = true;
		}
	}
}
System.out.println(Arrays.toString(array));

אז סיימנו את אלגוריתם המיון הראשון שלנו. נחזור על הלולאה החיצונית ( while) עד שנחליט שאין צורך בעוד איטרציות. כברירת מחדל, לפני כל איטרציה חדשה, אנו מניחים שהמערך שלנו ממוין ואין לנו צורך בלולאה יותר. בהתאם לכך, אנו עוברים ברצף בין האלמנטים ובודקים את ההנחה הזו. אבל אם האלמנטים לא מסודרים, אז אנחנו מחליפים אלמנטים ומבינים שכעת אין לנו ערובה שהאלמנטים בסדר הנכון. זה אומר שאנחנו צריכים לבצע איטרציה נוספת. לדוגמה, נניח שיש לנו [3, 5, 2]. 5הוא יותר מ- 3הכל טוב. אבל 2הוא פחות מ 5. עם זאת, [3, 2, 5]דורש מעבר נוסף, שכן 3 > 2ויש להחליף אותם. מכיוון שאנו משתמשים בלולאה בתוך לולאה, המורכבות של האלגוריתם שלנו עולה. בהינתן nאלמנטים, זה הופך n * n, כלומר, O(n^2). זה נקרא מורכבות ריבועית. באופן כללי, אנחנו לא יכולים לדעת בדיוק כמה איטרציות יהיה צורך. ביטוי המורכבות של אלגוריתם מראה כיצד המורכבות גדלה במקרה הגרוע. כלומר, הוא מציין כמה זמן הביצוע יגדל ככל שמספר האלמנטים nישתנה. מיון בועות הוא אחד מאלגוריתמי המיון הפשוטים והבלתי יעילים ביותר. זה נקרא לפעמים גם "מין טיפש". חומר בנושא זה:

• "HackerRank: אלגוריתמים - מיון בועה "

מיון בחירה

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

int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int left = 0; left < array.length; left++) {
	int minInd = left;
	for (int i = left; i < array.length; i++) {
		if (array[i] < array[minInd]) {
			minInd = i;
		}
	}
	swap(array, left, minInd);
}
System.out.println(Arrays.toString(array));

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

• "CS50: מיון בחירה"

מיון הכנסה

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

int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int left = 0; left < array.length; left++) {
	// Get an element
	int value = array[left];
	// Iterate through the elements that are in front of this element
	int i = left - 1;
	for (; i >= 0; i--) {
		// If the current element is smaller, then move the larger element to the right.
		if (value < array[i]) {
			array[i + 1] = array[i];
		} else {
			// If the current element is larger, we stop
			break;
		}
	}
	// Insert the current value in the empty space
	array[i + 1] = value;
}
System.out.println(Arrays.toString(array));

מיון הסעות

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

int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int i = 1; i < array.length; i++) {
	if (array[i] < array[i - 1]) {
		swap(array, i, i - 1);
		for (int z = i - 1; (z - 1) >= 0; z--) {
			if (array[z] < array[z - 1]) {
				swap(array, z, z - 1);
			} else {
				break;
			}
		}
	}
}
System.out.println(Arrays.toString(array));

חומר בנושא זה:

• החלטת AQA 1 2.02a מציגה את מיון המעבורת מאת ג'ק בראון

מיון מעטפת

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

int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
// Calculate the gap between the checked elements
int gap = array.length / 2;
// As long as there is a gap between the elements
while (gap >= 1) {
    for (int right = 0; right < array.length; right++) {
        // Shift the right index until we find one for which
        // there is the necessary gap between it and the element before it
       for (int c = right - gap; c >= 0; c -= gap) {
           if (array[c] > array[c + gap]) {
               swap(array, c, c + gap);
           }
        }
    }
    // Recalculate the gap
    gap = gap / 2;
}
System.out.println(Arrays.toString(array));

חומר בנושא זה:

• AQA Decision 1 2.03a Shell Sort - דוגמה עם 8 מספרים

מיזוג מיון

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

public static void mergeSort(int[] source, int left, int right) {
        // Select the delimiter, i.e. split the input array in half
        int delimiter = left + ((right - left) / 2) + 1;
        // Recursively execute this function on the two halves (if we can split the input array)
        if (delimiter > 0 && right > (left + 1)) {
            mergeSort(source, left, delimiter - 1);
            mergeSort(source, delimiter, right);
        }
}

כעת, בואו נוסיף את הפעולה העיקרית ליישום שלנו. הנה שיטת העל שלנו:

public static void mergeSort(int[] source, int left, int right) {
        // Select the delimiter, i.e. split the input array in half
        int delimiter = left + ((right - left) / 2) + 1;
        // Recursively execute this function on the two halves (if we can split the input array)
        if (delimiter > 0 && right > (left + 1)) {
            mergeSort(source, left, delimiter - 1);
            mergeSort(source, delimiter, right);
        }
        // Create a temporary array with the required size
        int[] buffer = new int[right - left + 1];
        // Starting from the specified left index, go through each element.
        int cursor = left;
        for (int i = 0; i < buffer.length; i++) {
            // We use delimeter to point to the element on the right half
            // If delimeter> right, then the right half has no elements that haven't been added
            if (delimiter > right || source[cursor] > source[delimiter]) {
                buffer[i] = source[cursor];
                cursor++;
            } else {
                buffer[i] = source[delimiter];
                delimiter++;
            }
        }
        System.arraycopy(buffer, 0, source, left, buffer.length);
}

אנחנו יכולים להפעיל את הדוגמה שלנו על ידי התקשרות mergeSort(array, 0, array.length-1). כפי שאתה יכול לראות, התהליך מסתכם בקבלת מערך קלט יחד עם אינדיקציות של ההתחלה והסוף של הקטע שיש למיין. כאשר המיון מתחיל, אלו הם ההתחלה והסוף של המערך. לאחר מכן אנו מחשבים את המפריד, שהוא המדד שבו נחלק את המערך. אם ניתן לחלק את המערך ל-2 חלקים, אז אנו קוראים לשיטת המיון באופן רקורסיבי עבור שני חצאי המערך. אנחנו מכינים מאגר עזר שבו נכניס את הקטע הממוין. לאחר מכן, הגדירו את האינדקס בתחילת הקטע למיון והתחילו לעבור דרך כל אלמנט של המאגר הריק, ולמלא אותו באלמנטים הקטנים ביותר. אם האלמנט שאליו מצביע האינדקס קטן מהאלמנט שעליו מצביע המפריד, נכניס את האלמנט למאגר ונעביר את האינדקס. אחרת, נמקם את האלמנט שעליו מצביע המפריד לתוך המאגר ומעבירים את המפריד. ברגע שהמפריד עובר את גבולות הקטע הממוין או שאנו ממלאים את כל המערך, הטווח שצוין נחשב לממוין. חומר בנושא זה:

• CS50: מיון מיזוג
• הוראות רעיון - מיון מיזוג

ספירת מיון ומיון רדיקס

אלגוריתם מיון מעניין נוסף הוא ספירת מיון. המורכבות האלגוריתמית כאן היא O(n+k), היכן nהוא מספר האלמנטים והוא kהערך המרבי של אלמנט. לאלגוריתם הזה יש חיסרון אחד: עלינו לדעת את ערכי המינימום והמקסימום במערך. הנה דוגמה למיון הספירה:

public static int[] countingSort(int[] theArray, int maxValue) {
        // An array of "counters", ranging from 0 to the maximum value
        int numCounts[] = new int[maxValue + 1];
        // We increase the counter in the corresponding cell (index = value)
        for (int num : theArray) {
            numCounts[num]++;
        }
        // Create an array to hold the sorted result
        int[] sortedArray = new int[theArray.length];
        int currentSortedIndex = 0;
        // Run through the array of "counters"
        for (int n = 0; n < numCounts.length; n++) {
            int count = numCounts[n];
            // Run through the number of values
            for (int k = 0; k < count; k++) {
                sortedArray[currentSortedIndex] = n;
                currentSortedIndex++;
            }
        }
        return sortedArray;
    }

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

• סרטון על מיון ספירה
• אלגוריתם מיון ספירה

מיון מהיר

ובכן, הגיע הזמן לקינוח - מיון מהיר, אחד מאלגוריתמי המיון המפורסמים ביותר. יש לו מורכבות לוגריתמית: O(n log n). אלגוריתם המיון הזה פותח על ידי טוני הואר. מעניין לציין שהוא המציא אותו בעודו חי בברית המועצות, שם למד תרגום מכונה באוניברסיטת מוסקבה ופיתח ספר ביטויים רוסית-אנגלית. יתרה מכך, Java משתמשת בגרסה מורכבת יותר של אלגוריתם זה ב Arrays.sort. מה לגבי Collections.sort? למה שלא תסתכל איך הדברים ממוינים "מתחת למכסה המנוע"? הנה הקוד:

public static void quickSort(int[] source, int leftBorder, int rightBorder) {
        int leftMarker = leftBorder;
        int rightMarker = rightBorder;
        int pivot = source[(leftMarker + rightMarker) / 2];
        do {
            // Move the left marker from left to right as long as the element is less than pivot
            while (source[leftMarker] < pivot) {
                leftMarker++;
            }
            // Move the right marker as long as the element is greater than pivot
            while (source[rightMarker] > pivot) {
                rightMarker--;
            }
            // Check whether we need to swap the elements pointed to by the markers
            if (leftMarker <= rightMarker) {
                // The left marker will be less than the right one only if we need to do a swap
                if (leftMarker < rightMarker) {
                    int tmp = source[leftMarker];
                    source[leftMarker] = source[rightMarker];
                    source[rightMarker] = tmp;
                }
                // Shift the markers to get new borders
                leftMarker++;
                rightMarker--;
            }
        } while (leftMarker <= rightMarker);

        // Execute recursively on the parts
        if (leftMarker < rightBorder) {
            quickSort(source, leftMarker, rightBorder);
        }
        if (leftBorder < rightMarker) {
            quickSort(source, leftBorder, rightMarker);
        }
}

כל זה דברים מאוד מפחידים, אז בואו נחפור בזה. עבור מערך קלט ( int[]מקור), אנו יוצרים שני סמנים: שמאל ( L) וימין ( R). במהלך קריאת השיטה הראשונה, הם תואמים את ההתחלה והסוף של המערך. לאחר מכן אנו מזהים את אלמנט הציר, ששמו ההולם הוא pivot. לאחר מכן, המשימה שלנו היא להעביר ערכים קטנים יותר מאשר pivotמשמאל ל- pivotוגדולים יותר - ימינה. לשם כך, ראשית מזיזים את Lהסמן עד שנמצא ערך גדול מ- pivot. אם לא נמצא ערך קטן יותר, אז L הופך שווה ל pivot. לאחר מכן אנו מזיזים את Rהסמן עד שנמצא ערך קטן מ- pivot. אם לא נמצא ערך גדול יותר, אז Rהופך להיות שווה ל pivot. לאחר מכן, אם Lהסמן נמצא לפני Rהסמן או עולה בקנה אחד איתו, אז ננסה להחליף את האלמנטים אם האלמנט Lקטן מהאלמנט R. לאחר מכן נעבור Lימינה ב-1, ונעבור Rשמאלה ב-1. כאשר Lהסמן זז מעבר Rלסמן, זה אומר שההחלפה הושלמה: ערכים קטנים יותר נמצאים משמאל ל- pivot, ערכים גדולים יותר נמצאים מימין ל- pivot. לאחר מכן, אנו קוראים לאותה שיטת מיון באופן רקורסיבי על מערכי המשנה - מתחילת הקטע שיש למיין לסמן הימני, ומהסמן השמאלי ועד סוף הקטע שיש למיין. למה מההתחלה לסמן הימני? כי בסוף איטרציה, מסתבר שהסמן הימני זז מספיק כדי להפוך לגבול החלק השמאלי. האלגוריתם הזה מורכב יותר ממיון פשוט, ולכן עדיף לשרטט אותו. קח דף נייר לבן וכתוב: 4 2 6 7 3. לאחר מכן כתוב pivotבאמצע, כלומר מתחת למספר 6. הקף אותו בעיגול. מתחת לגיל 4, כתוב Lומתחת לגיל 3, כתוב R. 4 פחות מ-6, 2 פחות מ-6. בסופו של דבר אנחנו עוברים Lלעמדה pivot, כי Lאנחנו לא יכולים לעבור pivot, לפי התנאי. כתבו שוב 4 2 6 7 3. הקיפו את 6 ( pivot) והכניסו Lמתחתיו. כעת הזיזו את Rהסמן. 3 הוא פחות מ-6, אז שימו את Rהסמן על 3. מכיוון ש-3 הוא פחות מ-6 ( pivot), אנו מבצעים swap. כתוב את התוצאה: 4 2 3 7 6. עיגול 6, כי זה עדיין ה- pivot. הסמן Lנמצא על 3. Rהסמן נמצא על 6. זכור שאנו מזיזים את הסמנים עד Lשעובר מעבר R. עברו Lלמספר הבא. כאן אני רוצה לחקור שתי אפשרויות: 1) המקרה שבו המספר הלפני אחרון הוא 7 ו-2) המקרה שבו הוא 1, לא 7. אם המספר הלפני אחרון הוא 1: הזיזו את Lהסמן ל-1, כי אנחנו יכולים לזוז Lכל עוד Lהסמן מצביע על מספר קטן מ- pivot. אבל אנחנו לא יכולים לזוז Rמ-6, כי אנחנו יכולים להזיז R רק אם Rהסמן מצביע על מספר שגדול מ- pivot. אנחנו לא מבצעים swap, כי 1 הוא פחות מ-6. כתוב את המצב הנוכחי: 4 2 3 1 6. עיגול 6 ( pivot). Lעובר pivotומפסיק לנוע. Rלא זז. אנחנו לא מבצעים החלפה. הסט Lובתפקיד Rאחד. כתוב את Rהסמן מתחת ל-1. Lהסמן הוא מחוץ לתחום. כי Lהוא מחוץ לתחום, אנחנו לא עושים כלום. אבל, אנחנו כותבים שוב 4 2 3 1, כי זה הצד השמאלי שלנו, שהוא פחות מ- pivot(6). בחר את החדש pivotוהתחל הכל מחדש :) אם המספר הלפני אחרון הוא 7: הזז את Lהסמן ל-7. אנחנו לא יכולים להזיז את הסמן הימני, כי הוא כבר מצביע על הציר. 7 גדול מ- pivot, אז אנו מבצעים א swap. כתוב את התוצאה: 4 2 3 6 7. עיגול 6, כי זה ה- pivot. הסמן Lמוסט כעת ל-7, והסמן Rמוסט ל-3. זה לא הגיוני למיין את החלק עד Lהסוף, כי יש רק אלמנט אחד. עם זאת, אנו שולחים את החלק מ-4 לסמן Rלמיון. אנחנו בוחרים a pivotומתחילים הכל מחדש :) במבט ראשון אולי נראה שאם תוסיפו הרבה ערכים השווים ל- pivotאז תשברו את האלגוריתם. אבל זה לא המקרה. אתה יכול לחשוב על שילובים מסובכים ועל הנייר לשכנע את עצמך שהכל נכון ולהתפלא שפעולות כל כך פשוטות מיישמות מנגנון מיון כל כך אמין. החיסרון היחיד הוא שאלגוריתם המיון הזה אינו יציב. מכיוון שהחלפה עשויה לשנות את הסדר היחסי של אלמנטים זהים אם נתקל באחד מהם לפני pivotשהרכיב השני יוחלף לחלק שלפני pivot.

בשורה התחתונה

למעלה, הסתכלנו על סט "ג'נטלמן" של אלגוריתמי מיון המיושמים בג'אווה. אלגוריתמים הם בדרך כלל שימושיים, הן מנקודת מבט יישומית והן מבחינת למידה כיצד לחשוב. חלקם פשוטים יותר, חלקם מסובכים יותר. אנשים חכמים הגנו על עבודת הגמר שלהם עבור חלקם. עבור אחרים, הם כתבו ספרים עבים במיוחד. אני מקווה שהחומרים המשלימים יעזרו לך ללמוד עוד יותר, שכן מאמר זה הוא רק סקירה כללית שכבר התבררה כבעלת משקל. ומטרתו לספק הקדמה קטנה. אתה יכול גם למצוא מבוא לאלגוריתמים אם אתה קורא "אלגוריתמים של גרוקינג ". אני גם אוהב את הפלייליסט של ג'ק בראון: AQA Decision 1 1.01 Tracing an Algorithm . בשביל הכיף, אתה יכול לראות הדמיות אלגוריתמים ב- sorting.at ו- visualgo.net .