[Powered by Google Translate] [مرتب سازی بر اساس درج] [تامی MacWilliam] [دانشگاه هاروارد] [این CS50.TV] بیایید نگاهی به چیدمان بر اساس درج، یک الگوریتم برای گرفتن یک لیست از اعداد و مرتب سازی آنها. الگوریتم، به یاد داشته باشید، این است که به سادگی یک روش گام به گام توسط به گام برای انجام یک کار است. ایده اساسی در پشت مرتب سازی بر درج، این است که به لیست ما را به دو بخش تقسیم بخش طبقه بندی شده اند و بخش نامرتب است. 

در هر مرحله از الگوریتم، شماره منتقل شده است از قسمت نامرتب به قسمت طبقه بندی شده اند تا در نهایت لیست تمام طبقه بندی شده اند. در اینجا لیست شش عدد نامرتب - 23، 42، 4، 16، 8، و 15 می باشد. از آنجا که این شماره ها صعودی نشده است، آنها نامرتب است. از آنجا که ما را شروع کرده اند مرتب سازی هنوز، ما در نظر گرفتن هر شش عنصر بخش نامرتب ما. 

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

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

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

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

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

بسیار خوب. در حال حاضر، ما چهار طبقه بندی شده اند و عناصر دو عنصر نامرتب است. بنابراین، اجازه دهید 8 به بخش طبقه بندی شده اند. هشت کمتر از 42 است. هشت کمتر از 23 است. و 8 کمتر از 16 است. اما 8 است بیشتر از 4 است. بنابراین، ما می خواهم برای قرار دادن 8 بین 4 و 16. و در حال حاضر ما فقط باید یک عنصر سمت چپ مرتب - از 15. پانزده کمتر از 42 است، پانزده کمتر از 23 است. و 15 کمتر از 16 است. اما 15 بیشتر از 8 می باشد. 

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

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

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

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

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

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

این بدان معنی است که مرتب سازی بر درج بهترین عملکرد مورد N، که ما آن را با Ω (n) را نمایندگی کند. و آن را برای مرتب کردن بر اساس قرار دادن، فقط یکی از الگوریتم های بسیاری از ما می توانیم با استفاده از یک لیست مرتب سازی بر اساس. نام تامی است، و این CS50. [CS50.TV] آه، شما نه تنها می تواند به توقف است که یک بار آن شروع می شود. آه، ما این کار را انجام دادیم - بوم >>!