MARK GROZEN-SMITH: سلام، من مارک هستم Grozen اسمیت، و این مرتب سازی سریع می باشد. درست مانند مرتب سازی بر درج و حباب مرتب کردن، مرتب سازی سریع یک الگوریتم برای است مرتب سازی یک لیست یا آرایه ای از همه چیز. برای سادگی، اجازه دهید فرض کنیم که کسانی که همه چیز فقط اعداد صحیح، اما می دانیم که مرتب سازی سریع برای کار بیش از اعداد. کلید شروع سریع است کمی پیچیده تر است از درج و یا حباب است، اما همچنین بسیار کارآمد تر در اکثر موارد. صبر کن یک لحظه. آیا او فقط می گویند "ترین موارد، "نه" همه "؟ جالب توجه است، هیچ. همه موارد یکسان است. آیا در مورد این جزئیات نگران نباشید اگر شما را دیده اند، نه نماد O بزرگ است، اما مرتب سازی سریع O (n مربع) الگوریتم است در بدترین حالت، درست مثل درج و یا مرتب سازی حبابی. با این حال، به طور معمول عمل می کند خیلی بیشتر مثل یک آنالوگ متر الگوریتم های قدیمی. چرا؟ ما به آن بعد دریافت کنید. اما در حال حاضر، اجازه دهید فقط یادگیری چگونه کار می کند مرتب سازی سریع. 

بنابراین اجازه دهید از طریق 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. از آنجا، ما می دانیم که آرایه طبقه بندی شده اند زیرا هر عنصر، در برخی از نقطه، یک محور. به عبارت دیگر، برای هر عنصر، همه اعداد به سمت چپ و کمتر ارزش ها و تمام اعداد به حق دارند ارزش بیشتر است. 

این روش به خوبی کار می کند در صورتی که ارزش محوری انتخاب شده است تقریبا در وسط طیف وسیعی از مقادیر لیست. به این معنی که بعد از حرکت ما عناصر اطراف، وجود دارد در مورد به عنوان بسیاری از عناصر در سمت چپ محور به سمت راست وجود دارد. و ماهیت تقسیم و تسخیر از الگوریتم مرتب سازی سریع است و سپس گرفته استفاده کامل از. این یک زمان اجرا از O (n log n استفاده،) N به خاطر ما باید انجام دهیم N منهای 1 مقایسه در هر نسل و ورود به سیستم N چرا که ما به تقسیم فهرست ورود برپایه نفر. با این حال، در بدترین موارد، این الگوریتم در واقع می تواند O (n است مربع.) فرض کنید در هر نسل، محور خیلی اتفاق می افتد می شود کوچکترین و بزرگترین تعداد ما در حال مرتب سازی. این به معنی شکستن در فهرست n بار و ساخت N منهای 1 مقایسه هر بار تنها. بنابراین، O از N مربع. 

چگونه می توان بهبود روش؟ یک راه خوب برای بهبود روش برای کاهش احتمال این که زمان اجرا است که تا کنون در واقع O از N مربع. به یاد داشته باشید این بدترین، بدترین سناریو مورد فقط می تواند رخ دهد هنگامی که محور انتخاب شده است همیشه بالاترین و یا کمترین مقدار در آرایه. برای اطمینان از این است به احتمال زیاد کمتر اتفاق می افتد، ما می توانیم محوری توسط پیدا انتخاب عناصر متعدد و مصرف مقدار متوسط. 

نام من علامت Grozen اسمیت است، و این CS50 است. 

برای سادگی، اجازه دهید فرض کنیم که کسانی که همه چیز فقط اعداد صحیح، اما می دانیم که Quicksert - Quicksert؟ متأسفم. 

در اینجا ما باید اعداد صحیح 6، 5، 1، 3، 8، 4، 9. 

SPEAKER: 1: واقعا؟ 

SPEAKER 2: آیا جا ختم نشد. 

SPEAKER 1: واقعا؟