שלום ,

לפי מה שלמדתי quick sort היא שיטת מיון היעילה ביותר במקרה הכללי. כמו כן יש את ה insertion sort שממיין בצורה מהירה מאוד מערכים כמעט ממויינים.

אני צריך לשלב את ה insertion sort בתוך quick sort החל מנקודה מסוימת, הקבצים שאני צריך למיין כוללים אלפי מילים.

אני אשמח אם מישהו יוכל לתת לי כיוון חשיבה או הסבר שיעזור לי להבין באיזה מקום הinsertion sort מייעל את האלגוריתם.

תודה

נ.ב הקוד בC++

void quick_insertion(string* A,int i, int j)
{
  if (j - i > 1)
  {
    if (j - i < 10 )/// בחירת הנקודה בה המערך ממוין מספיק
    {
      insertion(A,j);
    }
    else
    {
      int p = partition(A[0],A,i,j);
      quick_insertion(A,i,p);
      quick_insertion(A,p,j);
    }
  }
}

הרעיון ביעול quick sort בעזרת insertion sort הוא הורדת ה Overhead כאשר המערך מספיק קטן

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

לך למיין עם insertion sort תתחיל מ 10 אחוז ותרד,תעשה השוואה על כמה סוגים של רשימות שאתה צריך למיין

ותיקח את הערך שיתן לך יתרון מבחינת מהירות

כמו כן קראתי מזמן שקביעת ה Pivot בצורה רנדומלית יכולה לתת שיפור מסויים

קביעת ה-pivot בצורה אקראית אמורה להקטין את סיבוכיות ה-worst case של האלגוריתם. בקוד הנוכחי, לדוגמה, אם המערך הנתון הוא כבר ממוין לחלוטין, אז הסיבוכיות שלו תהיה (O(n^2 ולא (O(nlogn, ובחירה נכונה של pivot מונעת מצב כזה. הדרך הכי טובה היא שה-pivot יהיה החציון של המערך, וגם את זה ניתן למצוא באמצעות אלגוריתם מתאים.