Sorting: selection and insertion sort
סידור מערך
- חיפוש ליניארי הוא O(n); בינארי הוא O(log n).
- בבחן AP CSA עליכם לכתוב ולעקוב אחר שני סוגי מיונים: מיון בחירה ומיון הכנסה.
- עליך גם לעקוב (אבל לא לכתוב) סוג נוסף: מייג' סורט. אנו בוחנים כאן את שלושתם.
מיון בחירה: הרעיון
- הליכה באורך המערך משמאל לימין.
- בכל מיקום
i, מצאו את הערך הקטן ביותר בחלק שעדיין אינו מסודר (מ-iועד הסוף). - החליפו את הערך הקטן ביותר למיקום
i. עכשיו0..iמסודר. - חזרו על הפעולה עד שהמערך כולו מסודר.
public class Sorter {
public static void selectionSort(int[] a) {
for (int i = 0; i < a.length - 1; i++) {
int min = i; // index of smallest so far
for (int j = i + 1; j < a.length; j++) {
if (a[j] < a[min]) {
min = j; // found a smaller value
}
}
int temp = a[min]; // swap a[i] and a[min]
a[min] = a[i];
a[i] = temp;
}
}
}
מיון בחירה: מעקב
- נסדר את
{5, 2, 4, 1, 3}. החלק שמאלית ל-|כבר מסודר. - בכל סיבוב נבחר הערך הקטן ביותר מהשאר והוחלף לקצה.
start: [5, 2, 4, 1, 3]
i=0 smallest=1 → swap a[0],a[3]: [1 | 2, 4, 5, 3]
i=1 smallest is already 2 → no move: [1, 2 | 4, 5, 3]
i=2 smallest=3 → swap a[2],a[4]: [1, 2, 3 | 5, 4]
i=3 smallest=4 → swap a[3],a[4]: [1, 2, 3, 4 | 5]
done: [1, 2, 3, 4, 5]
מיון הכנסה: הרעיון
- דמיינו אחיזה בכרטיסי משחק והוספת כרטיס אחד כל פעם למקום הנכון.
- התחילו מאינדקס
1. קראו לערך זה את המפתח. - הזיזו ערכים גדולים יותר בצד שמאל בשיבה אחת ימינה, עד שמפתח נכנס למקומו.
- השחילו את המפתח לתוך הפתח. עכשיו הכל משמאל מסודר.
public class Sorter {
public static void insertionSort(int[] a) {
for (int i = 1; i < a.length; i++) {
int key = a[i]; // the value to place
int j = i - 1;
while (j >= 0 && a[j] > key) { // shift bigger values right
a[j + 1] = a[j];
j = j - 1;
}
a[j + 1] = key; // drop key into the gap
}
}
}
מיון הכנסה: מעקב
- סדר מחדש את
{5, 2, 4, 1, 3}. החלק שמאולף ל-|נשאר מסודר בזמן ההתקדמות. - ה-
keyהוא הערך שאנו מכניסים בכל סיבוב.
start: [5, 2, 4, 1, 3]
i=1 key=2 → shift 5 right, place 2: [2, 5 | 4, 1, 3]
i=2 key=4 → shift 5 right, place 4: [2, 4, 5 | 1, 3]
i=3 key=1 → shift 5,4,2 right, place 1: [1, 2, 4, 5 | 3]
i=4 key=3 → shift 5,4 right, place 3: [1, 2, 3, 4, 5]
done: [1, 2, 3, 4, 5]
מייג' סורט: רק מעקב
- מייג' סורט משתמש ברקורסיה (שיעור 15). אינכם כותבים אותו במבחן, אך עליכם לעקוב אחריו.
- פצלו את המערך לחצי ושוב ושוב, עד שכל חלק מכיל ערך אחד.
- מיזוג זוגות של חלקים יחד, תמיד בשמירה על הסדר.
מיזוג סוורט: מעקב
- ערך אחד כבר "מוערך". מיזוג שני חלקים מוערכים נותן חלק מוערך גדול יותר.
split: [5, 2, 4, 1]
[5, 2] [4, 1]
[5] [2] [4] [1]
merge: [2, 5] [1, 4]
merge: [1, 2, 4, 5]
- מיון בחירה ומיון הכנסה הם איטיים על מערכים גדולים (כ- n² צעדים).
- מיון מיזוג מהיר יותר על מערכים גדולים (כ- n·log n צעדים). מכאן החשיבות שלו.
טעויות נפוצות
- בחירת והכנסה סוורט הם שניהם O(n²).
- עקוב אחר מערך קטן ביד כדי לבדוק את הסיוורט שלך.
כעת תנסו בעצמכם
- כל משימה נותנת לך שלד שיטה עם TODO. סוורט את המערך במקום (שנה
aעצמו). - Harness נסתר סוורט מספר מערכים ובודק את התוצאה.
- השתמשו ב-Check answer כדי לקמפיל את הקוד שלך עם הבדיקות הסופקות ולצפות בתוצאות. שמרו את ממשקי המחלקה והשיטה המוצגים בתחילת העבודה.
Selection / insertion sort
Sorting compares and swaps until the list is ordered.
רמת קושי 4/5 · 280 מטבעות + בונוס קטן בהשלמה הראשונה היום
Complete selectionSort(int[] a) so it sorts the array in place from small to large, using selection sort. The checker tests several arrays.
לחץ על הרץ כדי לראות את התוצא כאן.
רמת קושי 4/5 · 280 מטבעות + בונוס קטן בהשלמה הראשונה היום
Complete insertionSort(int[] a) so it sorts the array in place from small to large, using insertion sort. The checker tests several arrays.
לחץ על הרץ כדי לראות את התוצא כאן.
רמת קושי 4/5 · 280 מטבעות + בונוס קטן בהשלמה הראשונה היום
Complete isSorted(int[] a) returning true if the array is in order from small to large (each item is <= the next), else false. An empty or one-item array counts as sorted.
לחץ על הרץ כדי לראות את התוצא כאן.