תרגיל 8, שאלה 1

תרגיל 8, שאלה 1

Israela 04 Jan 2011 21:11

כתוב בשאלה שהפיבוט הוא החציון. לפי המשמעות המתמטית, חציון זה המספר שחצי מהאיברים גדולים ממנו וחצי קטנים ממנו.
או לפי ההגדרה של ויקיפדיה- "החציון שווה לערך המופיע במקום האמצעי לאחר סידור הנתונים".
http://he.wikipedia.org/wiki/%D7%97%D7%A6%D7%99%D7%95%D7%9F
אבל לפי השיטה הזאת צריך קודם למיין את המערך בשביל לדעת מה הפיבוט…
למה הכוונה?

Re: תרגיל 8, שאלה 1

yaronore 04 Jan 2011 21:36

ההגדרות זהות. נניח נלך לפי ההגדרה הראשונה. תחשבי איפה החציון ישב אם תמייני את כל האיברים.

בנוסף, ניתן להגדיר לפי מיון האיברים. זה לא אומר שכדי למצוא את החציון חייבים למיין.

Re: תרגיל 8, שאלה 1

Yahav 04 Jan 2011 22:12

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

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

Re: תרגיל 8, שאלה 1

Israela 04 Jan 2011 22:20

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

Re: תרגיל 8, שאלה 1

Yahav 04 Jan 2011 22:28

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

Re: תרגיל 8, שאלה 1

idocohe2 04 Jan 2011 22:22

כשמדברים על מספר איברים- האם זה עם חזרות או בלי? כלומר, אם יש שתי 10- לספור אותם פעמיים או פעם אחת? במקרה שלנו בשני המקרים מקבלים תשובות שונות…

Re: תרגיל 8, שאלה 1

Yahav 04 Jan 2011 22:29

עם חזרות.
הסיבה היא שאנחנו רוצים לחלק את המערך לשני חלקים מאוזנים בגודל.

Re: תרגיל 8, שאלה 1

idocohe2 04 Jan 2011 23:14

רגע, הכוונה היא שהחציון שווה ל-P או ל-r כמו שראינו בשיעור? כלומר האם החציון הוא זה שאני בודק האם המספר גדול ממנו או קטן ממנו, ולפי זה מקדם את i ו-j (שזה r מהשיעור)? כי בשיעור ה-p הוא פשוט האיבר הראשון שממנו מתחילים את המיון.

Last edited on 05 Jan 2011 08:40 by Yahav Show more

Re: תרגיל 8, שאלה 1

Yahav 05 Jan 2011 08:44

החציון יבחר להיות ה-pivot, כלומר אותו איבר שאתה מחליף עם האיבר האחרון ואז מחלק את המערך לגדולים ממנו ולקטנים ממנו.