7.3 מיון-מהיר

מבנה נתונים ואלגוריתמים

 

 

 

מיון-מהיר (QuickSort) הוא אלגוריתם מיון יעיל ביותר שהומצא על ידי C.A.R Hoare. אלגוריתם זה כולל שני שלבים:

·        שלב החלוקה

·        שלב המיון

 

כפי שנראה בהמשך, רוב העבודה מבוצעת בשלב החלוקה, שבו מחושב היכן תפוצל וכיצד תתחלק העבודה הנותרת. בשלב החלוקה פשוט מטופלות שתי הבעיות הקטנות יותר שנוצרו בשלב החלוקה.

 

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

 

<TBODY>

quicksort( void *a, int low, int high )

  {

  int pivot;

  /* Termination condition! */

  if ( high > low )

    {

    pivot = partition( a, low, high );

    quicksort( a, low, pivot-1 );

    quicksort( a, pivot+1, high );

    }

  }


Initial Step - First Partition


Sort Left Partition in the same way</TBODY>

 

 

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

 

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

 

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

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

 

 

 

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

 

 

מושגים

 

אלגוריתם מסוג "הפרד ומשול"

אלגוריתם הפותר בעיות (מושל) על ידי חלוקתן לתת-בעיות קטנות יותר שוב ושוב, עד שהבעיות כה קטנות שפתרונן טריוויאלי.

מיון במקום (in place)

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

 

המשך ל: מיון מהיר - חלוקה במקום             חזור ל: תוכן עניינים