[موسیقی] 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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