Quicksort כשיטה תכנות

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

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

Quicksort נפוץ מאוד, ניתן למצוא אותו בכל מקום. על בסיס שלה השיטה מיושמת TList.Sort, נוכח כל הגרסאות (למעט 1) דלפי, את הפונקציה של זמן הספרייה שלקח לסיים, qsort ב- C ++.

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

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

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

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