דף 1 מתוך 1

מבחן 2009 מועד א' - שאלה 2 א'

נשלח: 20:07 25/06/2010
על ידי danny
בהסבר לפתרון שמציעים מסבירים כי יש לכל היותר 100 החלפות - כמספר האיברים שממוקמים לא נכון במקומם
אך מכיוון שאנחנו מבצעים Insertion Sort, אנחנו בין כה וכה עוברים עבור כל איבר i על כל שכניו מצד שמאל (שהרי זו דרך הפעולה של Insertion Sort), בכדי לזהות אם צריכה להתבצע החלפה.

אז השאלה שלי היא בעצם - אם ההליכה במערך היא ב-Insertion Sort, אז מדוע מתחשבים רק בהחלפות עצמם? (ההליכה יוצאת O(n^2) מן הסתם)

Re: מבחן 2009 מועד א' - שאלה 2 א'

נשלח: 20:17 25/06/2010
על ידי YoniDor
התשובה שנתונה שם לא מנוסחת כמו שצריך , היא כתובה בצורה קצת מבולבלת.

הכוונה היא כזו :
האיברים הממוינים לא יתחלפו בינם לבין עצמם ( כי הם כבר ממוינים ) , אלא רק עם איברים מתוך ה100 שלא ממוינים.
מה שאומר , שפוטנציאלית , כל איבר מה-100 יכול להתחלף מקסימום n פעמים (נניח שהתחלף עם כולם בשלב כלשהו).
המקרה הגרוע הוא כאשר כל איבר מה-100 התחלף עם n איברים , אז הגענו ל 100*n שזה (O(n.