>> MARK GROZEN-SMITH: היי, אני מארק Grozen-סמית, וזה Quicksort.
בדיוק כמו סוג הכנסה ואת הבועה למיין, Quicksort הוא אלגוריתם ל
מיון רשימה או מערך של דברים.
לשם פשטות, נניח שאלו דברים הם רק מספרים שלמים, אבל
יודע שQuicksort עובד עבור יותר מסתם מספרים.
התחלה מהירה היא קצת יותר מסובך מהכנסה או בועה, אבל זה
גם הרבה יותר יעיל ברוב המקרים.
חכה שני.
האם הוא רק אומר "ביותר מקרים ", לא" כל "?
מעניין, לא.
לא כל המקרים הם אותו הדבר.
אל תדאגו לגבי פרט זה אם אתה לא ראיתי את סימון O גדול עדיין, אבל
Quicksort הוא O (n בריבוע) אלגוריתם במקרה הגרוע, בדיוק כמו
כניסה או מיון בועות.
עם זאת, בדרך כלל מעשים הרבה יותר כמו אלגוריתם מ 'אנלוגי ישן.
למה?
אנחנו נחזור לכך בהמשך.
אבל לעת עתה, בואו פשוט ללמוד איך Quicksort עובד.
>> אז בואו ללכת דרך Quicksorting זה מערך של מספרים שלמים מקטן ביותר
לגדול ביותר.
כאן יש לנו את המספרים השלמים 6, 5, 1, 3, 8, 4, 7, 9, ו -2.
ראשית, עלינו לבחור את האלמנט הסופי של מערך זה - במקרה זה, שני -
וקורא לזה "ציר". בשלב הבא, אנחנו להתחיל להסתכל על שני דברים -
אחד, המדד הנמוך ביותר, שאני מתייחס כללהישאר בצד הימין של
הקיר, ו, שתיים, השמאלי ביותר אלמנט, שאני אתקשר "נוכחית
אלמנט. "מה שאנחנו הולכים לעשות הוא נראה את כל האלמנטים האחרים, אחרים
מהציר, ולשים את כל האלמנטים קטן יותר מהציר כדי
משמאל לקיר וכל אלה גדול מהציר כדי
זכותו של הקיר.
ואז, סוף סוף, אנחנו אקפיץ הציר ממש על הקיר שלשים אותו בין
כל המספרים קטנים יותר ממה שהוא וכל המספרים גדולים יותר.
>> אז בואו לעשות את זה.
להרים את 2, לשים את הקיר ב מתחיל, ולקרוא 6 "הנוכחי
אלמנט. "אז אנחנו רוצים להסתכל על האלמנט הנוכחי שלנו, 6.
ומכיוון שזה גדול יותר מאשר 2, אנחנו משאירים אותו שם כדי
זכותו של הקיר.
לאחר מכן, אנחנו עוברים להסתכל על 5 כמו שלנו אלמנט הנוכחי ותראה שזה
הוא, שוב, גדול יותר מהציר, ולכן אנחנו להשאיר אותו במקומו בצד הימין
הצד השני של החומה.
אנחנו ממשיכים הלאה.
האלמנט הנוכחי שלנו הוא החברה 1, ו-- הו.
זה שונה עכשיו.
האלמנט הנוכחי הוא החברה קטן יותר הציר, ולכן אנו רוצים לשים את זה
מהשמאל לקיר.
כדי לעשות זאת, בואו פשוט לעבור אלמנט הנוכחי עם המדד הנמוך ביותר
יושב רק בצד הימין של הקיר.
עכשיו, אנחנו עוברים את המדד אחת לקיר כך 1 הוא בצד השמאל
הצד השני של החומה עכשיו.
>> חכה.
אני פשוט מתערבב אלמנטים על צד ימני של הקיר, לא עשה לי?
אל תדאג.
זה בסדר.
הדבר היחיד שאכפת לנו לעת עתה הוא שכל האלמנטים האלה כדי
זכותו של הקיר גדולה יותר מהציר.
אין צו בפועל הנחה הוא עדיין.
>> עכשיו, בחזרה למיון.
אז אנחנו ממשיכים להסתכל על שאר האלמנטים.
ובמקרה זה, אנו רואים שיש אין אלמנטים אחרים פחות מ
ציר, ולכן אנחנו משאירים את כולם על בצד הימני של הקיר.
לבסוף, אנו מגיעים לאלמנט הנוכחי ותראה שזה הציר.
עכשיו, זה אומר שיש לנו שני סעיפים של המערך, הישות הראשונה
קטן על הציר ועל צד השמאל של הקיר, והבן השני
גדול מהציר כדי צד ימני של הקיר.
אנחנו רוצים לשים את אלמנט הציר בין שתיים, ואז נדע
שהציר הוא בזכות מקום ממוין סופי.
אז אנחנו לעבור האלמנט הראשון על צד ימני של הקיר עם הציר,
ואנחנו יודעים של הציר בעמדתה הנכונה.
>> לאחר מכן, אנו חוזרים על תהליך זה עבור subarrays שמאל וימין של הציר.
מאז subarray האחרון הוא רק אחד עוד אלמנט, אנחנו יודעים שזה כבר
ממוין כי איך אפשר להיות מחוץ להורות אם אתה רק אלמנט אחד?
לצד ימין של subarray, אנחנו רואה שהציר הוא 5, והקיר
הוא פשוט עזב את 6.
והאלמנט הנוכחי גם מתחיל כ6.
אז 6 הוא יותר מ -5.
אנחנו משאירים אותו במקומו על צד ימני של הקיר.
עכשיו, נע על, 3 הוא פחות מ 5.
אז אנחנו עוברים את זה עם האלמנט הראשון רק זכותו של הקיר.
עכשיו, אני עברתי את הקיר אחת למעלה.
עכשיו, על מנת להזיז את 8.
8 הוא יותר מ 5, ולכן אנחנו משאירים אותו.
4 הוא פחות מ 5, אז אנחנו עוברים את זה.
ועוד.
>> בכל פעם שאנו חוזרים על התהליך על צדדים ימני ושמאליים של המערך. אנחנו
לבחור ציר ולעשות השוואות וליצור רמה אחרת של שמאל ו
subarrays הנכון.
קריאה רקורסיבית זה תימשך עד אנחנו מגיעים לסוף, כאשר יש לנו
חילק את המערך הכולל לתוך רק subarrays באורך 1.
משם, אנחנו יודעים שהמערך ממוין כי כל אלמנט יש, ב
שלב מסוים, היה ציר.
במילים אחרות, עבור כל רכיב, כל המספרים בצד השמאל הם פחותים
ערכים ואת כל המספרים ל נכון יש ערכים גדולים יותר.
>> שיטה זו עובדת טוב מאוד אם ערך של הציר שנבחר הוא
בערך באמצע טווח הערכים של הרשימה.
משמעות הדבר, לאחר שאנו מתקדמים אלמנטים מסביב, שם על כמה שיותר
אלמנטים בצד השמאל של הציר כפי שיש לימין.
וטבע הפרד ומשול של אלגוריתם Quicksort מכן נלקח
את מלוא יתרונות של.
זה יוצר זמן ריצה של O (n log n,) n כי אנחנו צריכים לעשות n מינוס 1
השוואות בכל דור ויומן n כי יש לנו לחלק את הרשימה
להיכנס פעמים n.
עם זאת, במקרים הגרועים ביותר, זה אלגוריתם בעצם יכול להיות O (n
בריבוע.) נניח בכל דור ודור, הציר פשוט קורה כל כך להיות
הקטן ביותר או הגדול ביותר של מספרים שאנחנו מיון.
משמעות דבר פירוק הרשימה n פעמים וקבלת n מינוס 1
השוואות בכל פעם אחת.
לפיכך, o של n בריבוע.
>> איך אנחנו יכולים לשפר את השיטה?
דרך אחת טובה כדי לשפר את השיטה היא כדי לצמצם את ההסתברות כי
הריצה היא אי פעם באמת o של n בריבוע.
זכור מקרה תרחיש זה הגרוע ביותר, הגרוע ביותר רק יכול לקרות כאשר
הציר שנבחר הוא תמיד הגבוה ביותר או הערך הנמוך ביותר במערך.
כדי להבטיח זאת היא פחות סבירה שיקרה, אנחנו יכולים למצוא את הציר על ידי
בחירת אלמנטים ומספר לוקח את הערך החציוני.
>> השם שלי הוא מארק Grozen-סמית, וזה CS50.
>> לשם פשטות, נניח שאלו דברים הם רק מספרים שלמים, אבל
יודע שQuicksert -
Quicksert?
סליחה.
>> כאן יש לנו את המספרים השלמים 6, 5, 1, 3, 8, 4, 9.
>> 1 SPEAKER: באמת?
>> SPEAKER 2: אל תעצור שם.
>> 1 SPEAKER: באמת?