[Powered by Google Translate] تامی: بیایید نگاهی به مرتب کردن بر اساس انتخاب، یک الگوریتم
برای گرفتن یک لیست از اعداد و مرتب سازی آنها.
الگوریتم، به یاد داشته باشید، این است که به سادگی یک گام به گام
روش برای انجام یک کار است.
ایده اصلی در پشت مرتب کردن بر اساس انتخاب است به تقسیم
فهرست ما را به دو بخش -
بخش طبقه بندی شده اند و بخش نامرتب است.
در هر مرحله از الگوریتم، تعدادی از حرکت
بخش نامرتب به بخش طبقه بندی شده اند تا در نهایت
فهرست تمام طبقه بندی شده اند.
بنابراین در اینجا یک لیست از شش عدد -
23، 42، 4، 16، 8، و 15.
در حال حاضر لیست کل در نظر گرفته شده است نامرتب است.
حتی اگر یک عدد مثل 16 در حال حاضر ممکن است در صحیح خود باشد
محل سکونت:، الگوریتم ما هیچ راهی برای دانستن این که تا زمانی که
فهرست تمام طبقه بندی شده اند.
بنابراین ما در هر شماره به نامرتب در نظر بگیرند تا زمانی که مرتب سازی بر اساس
آن خودمان است.
ما می دانیم که ما می خواهیم این فهرست را به صعودی باشد.
بنابراین ما می خواهید برای ساخت قسمت طبقه بندی شده اند از لیست ما
از چپ به راست، کوچکترین به بزرگترین.
برای انجام این کار، ما نیاز به پیدا کردن عنصر نامرتب حداقل
و آن را در پایان از بخش طبقه بندی شده اند.
از آنجا که این لیست طبقه بندی شده اند، تنها راه برای انجام این کار این است که به
نگاهی به هر یک از عناصر در بخش نامرتب، به خاطر سپردن
عنصری که کمترین و مقایسه
هر عنصر به آن.
بنابراین ما برای اولین بار می خواهید از 23 نگاه کنید.
این عنصر برای اولین بار دیده ایم است، بنابراین ما به یاد داشته باشید
آن را به عنوان حداقل.
بعد ما را در 42 نگاه کنید.
42 بزرگتر از 23 است، به طوری که 23 هنوز هم حداقل است.
بعد از 4 است که کمتر از 23 است، بنابراین خواهیم 4 به یاد داشته باشید
به عنوان حداقل های جدید است.
بعد 16] که بزرگتر از 4 است، SO 4
هنوز هم حداقل است.
است 8 بزرگتر از 4 و 15 بزرگتر از 4 است، SO 4 باید
کوچکترین عنصر نامرتب.
بنابراین حتی اگر به عنوان انسان، ما بلافاصله می تواند که 4 است
حداقل عنصر، الگوریتم ما باید به دنبال در
هر عنصر نامرتب، حتی پس از ما پیدا کرده ام 4 -
عنصر حداقل.
بنابراین در حال حاضر که ما یافتیم این عنصر حداقل، 4، ما می خواهید
به آن حرکت را به بخش از فهرست طبقه بندی شده اند.
از آنجایی که این اولین گام، این بدان معنی است که ما می خواهیم برای قرار دادن 4 در
آغاز از لیست.
در حال حاضر 23 در ابتدای فهرست، به طوری
اجازه مبادله در 4 و 23.
بنابراین در حال حاضر لیست ما به نظر می رسد مثل این.
ما می دانیم که 4 باید در محل نهایی خود باشد، به دلیل آن است که
هر دو کوچکترین عنصر و عنصر در ابتدا
فهرست.
بنابراین این بدان معنی است که ما هرگز نیاز به آن حرکت دوباره.
بنابراین تکرار این فرایند عنصری دیگر برای اضافه کردن به
بخش از فهرست طبقه بندی شده اند.
ما می دانیم که ما نیازی به در 4 نگاه کنید، چرا که آن
در حال حاضر طبقه بندی شده اند.
بنابراین ما می توانیم از 42 شروع می شود، که ما آن را به عنوان به یاد داشته باشید
عنصر حداقل.
بنابراین بعد ما در 23 است که کمتر از 42 نگاه خواهیم کرد، بنابراین ما
به یاد داشته باشید 23 حداقل جدید.
بعد ما می بینیم از 16 است که کمتر از 23 است، به طوری
16 حداقل است.
در حال حاضر ما در 8 است که کمتر از 16 نگاه کنید، به طوری که
8 حداقل است.
و در نهایت 8 کمتر از 15 است، بنابراین ما می دانیم که 8 حداقل
عنصر نامرتب.
بنابراین این بدان معناست که ما باید 8 تا طبقه بندی شده اند اضافه
بخشی از فهرست.
در حال حاضر 4 تنها عنصر طبقه بندی شده اند، به طوری که ما می خواهیم به جای
بعدی 8 به 4.
از سال 42 این عنصر را برای اولین بار در بخش نامرتب است
فهرست، ما می خواهید به مبادله 42 و 8.
بنابراین در حال حاضر لیست ما به نظر می رسد مثل این.
4 و 8 نشان دهنده بخش از فهرست طبقه بندی شده اند، و
باقی مانده اعداد نامرتب
بخشی از فهرست.
بنابراین ادامه با یکی دیگر از تکرار کنیم.
ما با 23 شروع به این زمان، از آنجایی که ما لازم نیست که به دنبال در
از 4 و 8 دیگر از آنجا که
در حال حاضر مرتب شده است.
16 کمتر از 23 است، بنابراین ما به یاد داشته باشید
16 به عنوان حداقل های جدید شده است.
16 کمتر از 42 است، اما 15 این است که کمتر از 16، تا 15 باید
عنصر حداقل نامرتب.
بنابراین در حال حاضر ما می خواهیم به مبادله 15 و 23 تا
ما این لیست را به من بدهید.
بخش طبقه بندی شده اند از فهرست متشکل از 4، 8 و 15، و
این عناصر هنوز نامرتب است.
اما این فقط اتفاق می افتد که عنصر بعدی نامرتب، 16،
در حال حاضر طبقه بندی شده اند.
با این حال، هیچ راهی وجود دارد برای الگوریتم ما به دانستن که 16
در حال حاضر در محل صحیح خود است، بنابراین ما هنوز هم نیاز به
دقیقا همین روند را تکرار.
پس ما می بینیم که 16 این است که کمتر از 42 و 16 این است که کمتر از 23 است، بنابراین
16 سال باید به حداقل عنصر است.
این غیر ممکن است این عنصر را با خود به مبادله، بنابراین ما می توانیم
به سادگی آن را در این مکان را ترک کنند.
بنابراین ما نیاز به عبور یکی دیگر از الگوریتم ما.
42 بزرگتر از 23 است، به طوری که 23 باید
حداقل عنصر نامرتب.
پس از 23 و 42 مبادله، ما تا پایان با نهایی ما
طبقه بندی شده اند - فهرست
4، 8، 15، 16، 23، 42.
ما می دانیم که 42 باید در محل صحیح از آن
تنها عنصر باقی مانده است، و این که مرتب سازی بر اساس انتخاب.
بیایید در حال حاضر الگوریتم ما با برخی از رسمی
شبه.
در خط اول، ما می توانید ببینید که ما نیاز به استفاده از بیش از
هر عنصر از لیست.
به جز آخرین عنصر، از عنصر 1
لیست در حال حاضر طبقه بندی شده اند.
در خط دو، از نظر ما اولین عنصر نامرتب
بخشی از این فهرست به حداقل، به عنوان ما با ما
به عنوان مثال، بنابراین ما باید چیزی برای مقایسه.
خط سوم شروع می شود حلقه دوم است که در آن ما تکرار بیش از
هر یک از عناصر نامرتب است.
ما می دانیم که بعد از من تکرار، بخش طبقه بندی شده اند
از لیست ما باید در آن از عناصر هر مرحله
انواع یک عنصر است.
بنابراین اولین عنصر نامرتب باید در موقعیت به علاوه 1 باشد.
در خط چهارم، مقایسه کنیم عنصر فعلی را به حداقل برساند
عنصر است که ما تا کنون دیده ایم.
اگر عنصر کوچکتر است از حداقل
عنصر، پس از آن ما به یاد داشته باشید در حال حاضر به عنوان عنصر جدید
حداقل در خط 5.
در نهایت، در خطوط شش و هفت، ما مبادله حداقل
عنصر با عنصر اول نامرتب، در نتیجه
اضافه کردن آن را به بخش از فهرست طبقه بندی شده اند.
هنگامی که یک الگوریتم، برای پرسیدن یک سوال مهم
خودمان را به عنوان برنامه نویسان این است که چه مدت طول کشید؟
ما ابتدا به این سوال که چگونه آن را برای این
الگوریتم در بدترین حالت اجرا؟
به یاد ما نمایندگی این در حال اجرا
زمان با نماد O بزرگ.
به منظور تعیین حداقل عنصر نامرتب،
اساسا تا به حال به هر عنصر در لیست مقایسه
هر عنصر دیگر در لیست.
به طور مستقیم، این برای تلفن های موبایل مانند O عملیات N مربع است.
نگاهی شبه ما، ما نیز یک حلقه تو در تو در داخل
یکی دیگر از حلقه، که در واقع برای تلفن های موبایل مانند O
عملیات N مربع است.
با این حال، به یاد داشته باشید که ما نیاز به بیش از
فهرست کل زمانی که تعیین حداقل عنصر نامرتب؟
هنگامی که ما می دانستیم که از 4 طبقه بندی شده اند، برای مثال، ما نمی
نیاز به دوباره به آن نگاه کنید.
بنابراین آیا این کاهش زمان در حال اجرا است؟
برای ما طول 6، ما نیاز به 5
مقایسه برای اولین عنصر، چهار مقایسه برای
عنصر دوم، و به همین ترتیب.
این بدان معنی است که تعداد کل مراحل است که مجموع
اعداد صحیح از 1 تا طول لیست منهای 1.
ما می توانیم این کار را با یک جمع را نمایندگی کند.
ما نمی خواهد به summations اینجا.
اما معلوم می شود که این جمع برای بار N برابر است با
N منهای 1 بیش از 2.
یا به طور برابر، توان دو نفر بیش از 2 منهای N بیش از 2.
هنگامی که صحبت کردن در مورد زمان اجرا مجانبی، این اصطلاح مربع N
رفتن به تسلط در این مدت ازت.
بنابراین مرتب کردن بر اساس انتخاب O از N مربع است.
به یاد بیاورید که در مثال ما، مرتب کردن بر اساس انتخاب هنوز نیاز به
بررسی کنید که آیا تعداد که در حال حاضر طبقه بندی شده اند
نیاز به منتقل می شوند.
به طوری که بدان معنی است که اگر ما مرتب کردن بر اساس انتخاب در حال حاضر فرار
طبقه بندی شده اند فهرست، آن را به همان تعداد از مراحل آن را به عنوان نیاز
خواهد بود زمانی که در حال اجرا بیش از یک فهرست نامرتب به طور کامل.
بنابراین مرتب کردن بر اساس انتخاب بهترین عملکرد مورد مربع N،
که ما آن را با امگا N مربع را نمایندگی کند.
و آن را برای مرتب کردن بر اساس انتخاب می باشد.
تنها یکی از الگوریتم های بسیاری از ما می توانیم
استفاده از یک لیست مرتب کردن بر اساس.
نام تامی است، و این cs50.