DIR Return Create A Forum - Home
---------------------------------------------------------
Class H22
HTML https://classh22.createaforum.com
---------------------------------------------------------
*****************************************************
DIR Return to: exercises
*****************************************************
#Post#: 7--------------------------------------------------
27.2 עבודת
כיתה,
המיון של
משה
DIR By: Noam
Date: March 1, 2014, 3:25 am
---------------------------------------------------------
[right]בניגוד
למה שנאמר
בכיתה, לא
ניתן היה
לשפר את
האלגוריתם
של משה ע"י
הוספת
משתנה
שזוכר
ביצוע
החלפה. אני
אפרט
בפסודו-קוד:[color=white]
י[/color]
[glow=red,2,300]עבור על
המערך[/glow]
יייי[glow=red,2,300]כל
עוד יש
צורך
בחילוף-
עבור על
המערך[/glow]
יייייייי[glow=red,2,300]החלף
בין התאים[/glow]
יייייייי[glow=red,2,300]שנה
את המונה[/glow]
נכון, למי
שזוכר משה
כתב את זה
בצורת
שיקוע
הנמוכים
במקום
העלאת
הגבוהים,
אבל זה לא
רלוונטי.
אף על פי
שבחישוב
סיבוכיות
פורמלי
הקוד של
משה זהה
לקוד אותו
כתבנו,
לאלגוריתם
של משה
צפוי זמן
ריצה קצר
יותר
דה-פקטו.
מבחינת
המצב הגרוע
ביותר (בו
המערך
ממויין
לכוון
ההפוך)
והטוב
ביותר (בו
הערך
ממוין),
הקוד של
משה והקוד
שלנו זהים.
י
השינוי
המהותי הוא
במצב בו
ישנה כמות
החלפות
גדולה מ- 0
וקטנה
מהמקסימום
הנדרש. י
אני אתן
דוגמא
פשוטה: י
הקלט הוא
מערך
ממויין,
ובו יש
צורך
בהחלפה
בודדת בין
שני
איברים. י
הקוד שלנו
יעבור על
המערך פעם
אחת, יחליף,
ויזכור
שנעשתה
החלפה.
לאחר מכן,
נאתחל את
המשתנה
שזוכר את
ההחלפות,
ונעבור שוב
על המערך.
כעת,
המשתנה
שזוכר
החלפות
יגרום לנו
לסיים
(היות ולא
בוצעה
החלפה
בריצה
השנייה). ז"א,
בפועל יש
לנו שתי
ריצות על
המערך
(פחות איבר
למי שזוכר
שלא צריך
לרוץ על
הממויינים).
י
הקוד של
משה ירוץ
על המערך,
יגיע
לאיברים
ההפוכים.
ייכנס
ללולאה,
יחליף את
האיברים
וייצא
ממנה- כי
כעת
האיברים
במקומם
הנכון. אז-
ימשיך לרוץ
על המערך
(הלולאה
המכילה),
ויסיים את
הריצה.
בפועל
קיבלנו
ריצה אחת
על המערך
וריצה של
איבר אחד
(בלולאה
הפנימית). י
ההבדל
בדוגמא בין
הקודים הוא
מספר צעדים
השווה
למספר
האיברים
פחות 2, כאשר
הקוד של
משה יצטרך
ללכת פחות
צעדים. י
[/right]
#Post#: 8--------------------------------------------------
Re: 27.2 עבודת
כיתה,
המיון של
משה
DIR By: SpiderGoat
Date: March 1, 2014, 4:22 am
---------------------------------------------------------
[right]מעניין...
לא זכרתי
שהתכנית
שלו שלו
ידעה
להפסיק
בזמן אם
ההמשך
ממוין.
אבל בלי
קשר משה
יצא מגניב
עם הקוד
שלו.
למדתי ממנו
דבר או
שניים.
מה שכן,
אני כתבתי
לולאה בתוך
לולאה,
ובלי תנאי
יציאה
מוקדם,
אז ההערה
של המרצה,
בין אם
נכונה ובין
אם לא, עזרה
לי המון
בתרגיל
הנוכחי.
עד עכשיו
כתבתי
"עובד". אני
צריך לחשוב
מעכשיו על
"עובד
ויעיל".
ויפה לך
שאתה זוכר
מספיק כדי
לשחזר
ולקמפל!
[/right]
*****************************************************
Page 1 of 1