כיצד לחשב מיון מערך בסיבוכיות נמוכה ככל הניתן

[Holy Spirit]

מה שגיל אומר: בלולאה שלך כל מעבר k מסדר את האיברים עם שארית k (המעבר ה-"0" את המספרים עם שארית 0 וכו').

ובלולאה/לולאות שלו הוא במעבר אחד מסדר גם את המספרים עם שארית 0 להתחלה וגם את המספרים עם שארית 3 לסוף, ובעוד מעבר אחד אותו דבר עם השאריות 1, 2.

זה אולי משפר קצת את הקבוע, אבל לא בהרבה. זה בכל מקרה O(n)‎.

זה איך שאני רשמתי את הדרך שלי (לא בדוק):

void sortByMod4(int arr[]) {
  int top = 0;
  for (int n = 0; n < 3; n++) {
    for (int i = top; i < arr.length(); i++) {
      if (a[i] % 4 == n) {
        swap(a[top], a[i]);
        top++;
      }
    }
  }
}