כתוב בשאלה שהפיבוט הוא החציון. לפי המשמעות המתמטית, חציון זה המספר שחצי מהאיברים גדולים ממנו וחצי קטנים ממנו.
או לפי ההגדרה של ויקיפדיה- "החציון שווה לערך המופיע במקום האמצעי לאחר סידור הנתונים".
http://he.wikipedia.org/wiki/%D7%97%D7%A6%D7%99%D7%95%D7%9F
אבל לפי השיטה הזאת צריך קודם למיין את המערך בשביל לדעת מה הפיבוט…
למה הכוונה?
ההגדרות זהות. נניח נלך לפי ההגדרה הראשונה. תחשבי איפה החציון ישב אם תמייני את כל האיברים.
בנוסף, ניתן להגדיר לפי מיון האיברים. זה לא אומר שכדי למצוא את החציון חייבים למיין.
לגבי השאלה - שימי לב שאת רק צריכה לבצע את המיון לפי ה-
pivot
שהגדרנו להיות החציון, את לא צריכה להראות איך מצאת את החציון
(קל למצוא חציון במערך של 15 איברים בעזרת הראש בלבד)
באופן כללי -
אלגוריתם ה-
Quicksort
במימוש הדטרמיניסטי היעיל שלו יבחר את ה-
pivot
להיות החציון, בדיוק כמו בשאלה.
כמובן שהוא לא יכול למיין בשביל המשימה הזאת,
וזו הסיבה שלמדנו את אלגוריתם החמישיות,
שמוצא חציון בזמן לינארי.
אני יכולה למצוא את החציון "בראש"
פשוט אם חושבים על אלגוריתם שממיין בצורה כזאת, היה נראה קצת לא הגיוני לחפש ככה את החציון
אבל בסדר, רק רציתי לוודא שזאת הייתה הכוונה
כשמדברים על מספר איברים- האם זה עם חזרות או בלי? כלומר, אם יש שתי 10- לספור אותם פעמיים או פעם אחת? במקרה שלנו בשני המקרים מקבלים תשובות שונות…
רגע, הכוונה היא שהחציון שווה ל-P או ל-r כמו שראינו בשיעור? כלומר האם החציון הוא זה שאני בודק האם המספר גדול ממנו או קטן ממנו, ולפי זה מקדם את i ו-j (שזה r מהשיעור)? כי בשיעור ה-p הוא פשוט האיבר הראשון שממנו מתחילים את המיון.