שלום

נתנו לנו משימה ליצור מיון הכנסה בינארי ב c++

לאחר חיפוש מצאתי את הקוד הבא בקישור הבא:

using namespace std;

int BinarySearch (int a[], int low, int high, int key);
void BinaryInsertionSort (int a[], int n);

int main ()
{
int n=10;
int a[]={2,3,5,2,7,9,4,6,1,6};
for (int i=0; i<n; i++) {
cout<<a[i]<<" ";}
cout<<endl<<endl;
BinaryInsertionSort (a,n);
for (int i=0; i<n; i++) {
cout<<a[i]<<" ";}

return 0;
}

int BinarySearch (int a[], int low, int high, int key)
{
int mid;

if (low == high)
return low;

mid = low + ((high - low) / 2);

if (key > a[mid])
return BinarySearch (a, mid + 1, high, key);
else if (key < a[mid])
return BinarySearch (a, low, mid, key);

return mid;
}


void BinaryInsertionSort (int a[], int n)
{
int ins, i, j;
int tmp;

for (i = 1; i < n; i++) {
ins = BinarySearch (a, 0, i, a[i]);
if (ins < i) {
tmp = a[i];
for (j = i - 1; j >= ins; j--)
a[j + 1] = a[j];
a[ins] = tmp;
}
}

#include <iostream>

}

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

אשמח בכל זאת אם מישהו יוכל להסביר לי יותר בפשטות כיצד הקוד עובד כי הסתבכתי קצת עם כל הרקורסיות

תודה

קודם תסתכל על search. היא לא תלויה ב-insert.

מה היא עושה? הפונקציה מחפשת את האיבר במערך a שערכו key.

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

כלומר כל פעם search מוצאת חצי מהקטע הנוכחי שבו key חייב להיות, ואז באופן רקורסיבי מחפשת את key באותו חצי.

עכשיו אתה יכול להבין יותר מה Insertionsort עושה.

הערה קטנה: עטוף את הקוד שלך בטג קוד (כפתור # ליד הכפתור של הציטוט) כדי שייראה נורמלי.

אבל המערך בעצם לא ממויין. איך התוכנית מצליחה גם למיין בינארית וגם למיין בסדר עולה את המערך?

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

step 1:
BinaryInsertionSort ( {2,3,5,2,7,9,4,6,1,6} , 10)
FOR LOOP STEP i=1
ins = BinarySearch ( a={2,3,5,2,7,9,4,6,1,6}, 0, 1, a[0]=2); --> returns 0 (!!!!)
LOOP over J does nothing
FOR LOOP STEP i=2
ins = BinarySearch ( a={2,3,5,2,7,9,4,6,1,6}, 0, 1, a[1]=3); --> returns 0 (!!!!)
loop over J does nothing

...
STEP 4
ins = BinarySearch ( a={2,3,5,2,7,9,4,6,1,6}, 0, 1, a[4]=5); --> returns 1
loop over j (pushes 2 at place 1
STEP 5 (notice that for the first time array a has changed)
ins = BinarySearch ( a={2,2,3,5,7,9,4,6,1,6}, 0, 1, a[5]=7); --> returns 0
...
..

רק ככה קל לראות איך זה עובד: וברישום יותר טכני:

2,3,5,2,7,9,4,6,1,6
^

2,3,5,2,7,9,4,6,1,6
 ^

2,3,5,2,7,9,4,6,1,6
  ^

2,3,5,2,7,9,4,6,1,6
   ^

2,2,3,5,7,9,4,6,1,6
    ^

2,3,5,2,7,9,4,6,1,6
    ^

אבל המערך בעצם לא ממויין. איך התוכנית מצליחה גם למיין בינארית וגם למיין בסדר עולה את המערך?

אכן אתה צודק. מה שהתוכנית עושה זה מניחה שהמערך ממוין עד i, ואז מכניסה את האיבר ה-i+1 למערך הממוין.

עבור i ==0: פשוט מכניסה את איבר 0 למקום 0.

עבור i == 1: היא מכניסה את a[1] למערך בגודל 1 שמכיל את a[0]. עכשיו יש מערך בגודל 2 שהוא ממוין.

עבור i==2: היא מכניסה את a[2] למערך ממוין בגודל 2 שנבנה באיטרציה הקודמת וכן הלאה.