מיון: בועה, בחירה והכנסה
עמוד זה דורש דפדפן עדכני (תומך ב-SharedArrayBuffer). אנא עדכן את Chrome, Edge, Firefox או Safari לגרסה העדכנית ביותר.
סידור מערך
- מיון מסדר מחדש את המערך כך שהפריטים יהיו מהקטן לגדול.
- אנו ממינים בתוך המערך: אנו מזיזים פריטים בתוך אותו מערך, ללא ערך חזרה.
- שלושי שיטות קלאסיות לעשות זאת: בלבילה, הכנסה, ובחירה.
החלפת שני אלמנטים
- לכל מיון יש להחליף שני פריטים. שמור אחד זמנית, ואז כתוב עליו מחדש.
int t = a[i]; a[i] = a[j]; a[j] = t;מחליף את המקומותiוj.- לשכוח את הזמני מאבד אחת הערכים — תמיד שמור אותו.
מיון בועות
- עבר על המערך והשווה כל זוג של שכנים:
a[j]וa[j + 1]. - אם הם בסדר הלא נכון, החלף אותם. הערך הגדול ביותר "מצטופף" לקצה.
- חזור על מעברים עד שכל המערך יהיה מסודר.
מיון הכנסה
- התעלם מהחלק השמאלי של המערך כמי שסודר כבר, והגדל אותו פריט אחד בכל פעם.
- קח את הפריט הבא כקובץ, הזז פריטים מסודרים גדולים יותר ימינה, ואז השחל את הקובץ לתוך הרווח.
- כך אנשים רבים מסדרים קלפים בידם.
English
#include <stdio.h>
int main(void) {
int a[] = {3, 1, 2};
// one bubble pass: compare neighbours and swap if out of order
for (int j = 0; j < 2; j++) {
if (a[j] > a[j + 1]) {
int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
}
}
printf("%d %d %d\n", a[0], a[1], a[2]); // 1 2 3
return 0;
}
טעויות נפוצות
- מיון בועות, בחירה והכנסה הם כולם O(n²).
- עקוב אחר מערך קטן ביד כדי לבדוק את הסיוורט שלך.
כעת תנסו בעצמכם
- סדר עולה (הקטן תחילה), במקום, ללא ערך החזרה.
- הבדיקה מנסה מספר מערכים, כולל שליליים ומערכת שכבר מסודרת.
- אל תכתוב
main— הבוקר מספק אותו already.
חקור
צפה בביצוע מיון
בועה / בחירה / הכנסה כולם מבצעי השוואה והחלפה לסדר.
רמת קושי 4/5 · 280 מטבעות + בונוס קטן בהשלמה הראשונה היום
השלם void swap(int a[], int i, int j) כך שתחליף את הפריטים באינדקסים i ו-j, במקום (ללא החזרה). אל תכתב פונקציה main.
לחץ על הרץ כדי לראות את התוצא כאן.
רמת קושי 4/5 · 280 מטבעות + בונוס קטן בהשלמה הראשונה היום
השלם void bubble_sort(int a[], int n) כך שתמין את המערך לעלייה, במקום, באמצעות מיון בועות. אל תכתב פונקציה main.
לחץ על הרץ כדי לראות את התוצא כאן.
רמת קושי 4/5 · 280 מטבעות + בונוס קטן בהשלמה הראשונה היום
שלים את void insertion_sort(int a[], int n) כך שתסדר את המערך בסדר עולה, במקום, באמצעות מיון הכנסה (take each item as a key and shift bigger items right). אל תכתוב main.
לחץ על הרץ כדי לראות את התוצא כאן.