[موسیقی] داگ لوید: مرتب سازی بر اساس گزینش است الگوریتم است که، همانطور که شما ممکن است انتظار، انواع مجموعه ای از عناصر. و به یاد الگوریتم مجموعه ای گام به گام است از دستورالعمل برای انجام یک کار. 

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

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

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

در حال حاضر، دوباره، کل آرایه بخش نامرتب است. تمام عناصر قرمز نامرتب هستند. و بنابراین ما از طریق جستجو ما پیدا کردن کوچکترین ارزش است. ما در آغاز شروع، ما به پایان، ما پیدا کردن کوچکترین ارزش است، یک. به طوری که بخشی از یک است. و سپس بخش دوم، مبادله که ارزش با عنصر اول از بخش نامرتب، و یا اولین عنصر قرمز است. 

در این مورد است که می تواند پنج، بنابراین ما مبادله یک و پنج. هنگامی که ما انجام این کار، ما می توانیم بصری دید که ما کرده ایم کوچکترین عنصر ارزش نقل مکان کرد از آرایه، به ابتدا. به طور موثر مرتب سازی آن عنصر است. 

و بنابراین ما می تواند در واقع منظور و دولت است که یکی از طبقه بندی شده اند است. و بنابراین ما بخش طبقه بندی شده اند نشان می دهد آرایه ما، با رنگ آمیزی آن را آبی رنگ است. 

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

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

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

ما که پنج است کوچکترین عنصر. ما آن را مبادله با اولین عنصر از قسمت نامرتب. و در حال حاضر پنج طبقه بندی شده اند است. 

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

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

بهترین حالت چه خبر؟ خوب آن را دقیقا به همان، درست است؟ در واقع ما هنوز هم قدم از طریق هر عنصر از آرایه به منظور تایید آن است که، در واقع، کوچکترین عنصر. 

بنابراین بدترین حالت زمان اجرا، ما مجبور به تکرار یک فرایند n بار، یک بار برای هر یک از n عنصر و در بهترین حالت، ما باید به انجام همان. 

بنابراین به فکر بازگشت به ما جعبه ابزار پیچیدگی محاسباتی، شما چه فکر میکنید بدترین است مورد زمان اجرا برای مرتب سازی انتخابی؟ شما چه فکر میکنید بهترین است مورد زمان اجرا برای مرتب سازی انتخابی؟ 

آیا شما حدس می زنم O بزرگ از n مربع، و بزرگ امگا از n مربع؟ شما می شود، مناسب است. کسانی هستند، در واقع، بدترین حالت و بهترین حالت اجرا بار، برای مرتب سازی انتخابی. 

من داگ لوید هستم. این CS50 است.