ויקיספר

מבוא לתכנות ולמדעי המחשב בשפת C/רקורסיה (מיון מהיר): הבדלים בין גרסאות בדף

עיון אינטראקטיבי בהיסטוריה
→ העריכה הקודמת
תוכן שנמחק תוכן שנוסף
חזותיקוד ויקי
 
שורה 2:
 
== מיון מהיר ==
כבר השתכנענו בעבר שמיון הוא משימה חשובה. ראינו שכאשר הנתונים ממוינים, אפשר למצוא את הנתון שמחפשים הרבה יותר בקלות. למדנו גם אלגוריתם למיון אבל הוא היה די נאיבי ולא יעיל. היעילות שלו היתה <mmath>O(n^2)</mmath>.
 
בשיעור זה נלמד אלגוריתם יעיל בהרבה שנקרא מיון מהיר, או quicksort בלעז. בממוצע, הסיבוכיות של האלגוריתם הזה היא <mmath>O(n \cdot log (n))</mmath> אבל במקרה הכי גרוע (והנדיר) היא עדיין <mmath>O(n^2)</mmath>.
 
עד היום דיברנו על סיבוכיות התלויה רק בגודל הקלט. כאן, כאשר תיארנו את הסיבוכיות של quicksort, דיברנו על סיבוכיות ממוצעת וסיבוכיות במקרה הגרוע. העניין הוא שיעילות האלגוריתם שנלמד עכשיו, תלויה מאוד בסדר הנתונים שהתקבלו בקלט. לדוגמה, דווקא אם הקלט יהיה ממויין מלכתחילה, האלגוריתם יעבוד קשה מאוד והיעילות שלו תהיה דומה לזו של המיון הנאיבי שלמדנו. במקרה היותר טיפוסי, של קלט מעורבל, האלגורתם יהיה יעיל בהרבה.
אוחזר מתוך "https://he.wikibooks.org/wiki/מבוא_לתכנות_ולמדעי_המחשב_בשפת_C/רקורסיה_(מיון_מהיר)"