>> [موسیقی]
داگ لوید: خوب، پس مرتب سازی حبابی یک الگوریتم است
شما می توانید به مرتب سازی بر اساس مجموعه ای از عناصر استفاده کنید.
اجازه دهید یک نگاه چگونه کار می کند.
>> بنابراین ایده اصلی در پشت مرتب سازی حبابی است.
ما به طور کلی می خواهید به حرکت بالاتر عناصر ارزش به طور کلی به سمت راست،
و کاهش ارزش به طور کلی عناصر به سمت چپ، به عنوان ما انتظار می رود.
ما می خواهیم همه چیز پایین تر به در می شود آغاز، و از چیزهایی بالاتر
در پایان باشد.
>> چگونه این کار را کردیم؟
خوب در کد شبه، می توان گفت، اجازه دهید
مجموعه ای از یک ضد مبادله را به یک مقدار غیر صفر.
خواهیم دید که چرا ما این کار را در یک ثانیه.
و پس از آن ما به شرح زیر تکرار روند تا زمانی که مبارزه مبادله 0 است،
یا تا زمانی که ما هیچ سواپ در همه.
>> شمارشگر مبادله به 0 اگر آن را در حال حاضر 0 است.
سپس در هر نگاه جفت های مجاور از عناصر.
اگر این دو عنصر هستند نه به منظور، آنها مبادله،
و اضافه کردن 1 به مقابله مبادله.
اگر شما در حال فکر کردن در مورد این قبل از شما آن تجسم،
توجه کنید که این پایین حرکت خواهد کرد عناصر ارزش به سمت چپ
و بالاتر عناصر به سمت راست به ارزش، به طور موثر انجام آنچه ما می خواهیم انجام،
است که حرکت آن گروه از عناصر در آن راه.
بیایید تجسم چگونه این ممکن است با استفاده از آرایه ما نگاه
که ما مورد استفاده برای تست این الگوریتم باشد.
ما یک آرایه نامرتب در اینجا دوباره، نشان داده شده با تمام عناصر
قرمز شدن.
و من مجموعه من مبادله ضد به یک مقدار غیر صفر باشد.
من خودسرانه انتخاب منفی 1-- آن را 0.
ما می خواهیم این روند را تا زمانی که مبارزه مبادله 0 است.
این است که چرا من مجموعه ای مبادله من مقابله با برخی از ارزش های غیر صفر،
چون در غیر این صورت مبادله ضد می شود 0.
ما حتی نمی شروع روند الگوریتم.
بنابراین، مراحل are-- شمارشگر مبادله
تا 0، پس از آن در هر مجاور نگاه جفت، و اگر آنها از سفارش هستید،
مبادله آنها، و اضافه کردن 1 به مقابله مبادله.
بنابراین اجازه دهید این روند آغاز خواهد شد.
بنابراین اولین چیزی که ما انجام می دهیم ما دفاعیه مبادله مجموعه را به 0،
و سپس ما شروع به دنبال در هر جفت های مجاور.
>> بنابراین ما برای اولین بار شروع به دنبال در 5 و 2.
ما می بینیم که آنها از می سفارش و بنابراین ما آنها مبادله.
و ما اضافه کردن 1 به مقابله مبادله.
بنابراین در حال حاضر ما مبادله کردن 1 است، و 2 و 5 روشن شده است.
در حال حاضر ما این فرآیند را دوباره تکرار کنید.
>> ما در این جفت ارز در مجاورت بعدی نگاه کنید، 5 و 1-- آنها نیز خارج از دستور هستید،
بنابراین ما آنها را مبادله و اضافه کردن 1 به مقابله مبادله.
سپس ما در 5 و 3 است.
آنها از نظم هستند، بنابراین ما مبادله آنها و ما اضافه کردن 1 به مقابله مبادله.
سپس ما در 5 و 6 است.
آنها به منظور هستیم، بنابراین ما در واقع نه نیاز به مبادله هر چیزی در این زمان.
سپس ما در 6 و 4 نگاه کنید.
آنها همچنین از سفارش هستیم، بنابراین ما مبادله آنها و ما اضافه کردن 1 به مقابله مبادله.
>> در حال حاضر متوجه آنچه اتفاق افتاده.
ما نقل مکان کرد 6 تمام راه را به پایان است.
بنابراین در انتخاب نوع، اگر شما دیده می شود که ویدئو، آنچه ما کردیم این بود
ما به پایان رسید تا در حال حرکت کوچکترین عناصر در ساختمان
آرایه مرتب شده اساسا از چپ به راست، کوچکترین تا بزرگترین.
در مورد مرتب سازی حبابی، اگر ما زیر این الگوریتم خاص،
ما در واقع رفتن به ساختمان می شود آرایه مرتب شده از راست
به سمت چپ، بزرگ به کوچک.
ما به طور موثر حباب 6، بزرگترین ارزش، تمام راه را به پایان است.
>> و بنابراین ما هم اکنون می توانید اعلام که طبقه بندی شده اند،
و در آینده iterations-- رفتن را از طریق آرایه again--
ما لازم نیست به نظر 6 نیست.
ما فقط باید در نظر عناصر نامرتب
هنگامی که ما به دنبال در جفت های مجاور.
بنابراین ما به پایان رسید یکی از عبور از مرتب سازی حبابی.
بنابراین در حال حاضر ما به بازگشت به این سوال، تکرار تا زمانی که در مقابله مبادله 0 است.
خوب ضد مبادله 4، بنابراین ما قصد داریم
برای نگه داشتن تکرار این فرایند است.
>> ما قصد داریم برای تنظیم مجدد شمارنده مبادله تا 0، و در هر جفت های مجاور است.
بنابراین ما با 2 شروع و 1-- آنها خارج از دستور، بنابراین ما آنها را مبادله
و ما اضافه کردن 1 به مقابله مبادله.
2 و 3، آنها را در جهت هستید.
ما لازم نیست به هیچ چیز.
در 3 و 5 می باشد.
ما لازم نیست به انجام هر کاری است.
>> 5 و 4، آنها هستند سفارش، و بنابراین ما
نیاز به آنها مبادله و اضافه کردن 1 به مقابله مبادله.
و در حال حاضر ما نقل مکان کرد 5، بزرگترین عنصر بعدی،
به پایان بخش نامرتب.
بنابراین ما هم اکنون می توانید تماس بگیرید که بخشی از قسمت طبقه بندی شده اند.
>> در حال حاضر شما به دنبال در صفحه نمایش و احتمالا می توانید بگویید،
می تواند به عنوان من، که آرایه است در حال حاضر طبقه بندی شده اند.
اما ما می توانیم ثابت نمی کند که در عین حال.
ما تضمین ندارد که آن را طبقه بندی شده اند.
اما این است که در آن مبادله ضد رفتن به به بازی آمد.
>> بنابراین ما یک پاس به پایان رسانده ام.
مبادله ضد 2 است.
بنابراین ما قصد داریم به تکرار این فرایند دوباره،
تکرار تا زمانی که در مقابله مبادله 0 است.
شمارشگر مبادله به 0.
بنابراین ما آن را بازنشانی کنید.
>> در حال حاضر در هر جفت های مجاور است.
که در سفارش، 1 و 2.
در 2 و 3 هستند.
در 3 و 4 می باشد.
بنابراین در این نقطه، متوجه ما تکمیل کرده اید به دنبال در هر جفت های مجاور،
اما ضد مبادله است که هنوز هم 0.
>> اگر ما مجبور به تغییر هر یک از عناصر، سپس آنها
باید به منظور شود، فضیلت از این روند.
و به این ترتیب بهره وری از انواع، که دانشمندان ما کامپیوتر را دوست دارم،
ما در حال حاضر است می تواند اعلام کل آرایه باید
مرتب، چون ما نمی مجبور به تعویض هر یک از عناصر.
این خیلی خوب است.
>> پس چه بدترین حالت است سناریو با مرتب سازی حبابی؟
در بدترین حالت آرایه است در به طور کامل معکوس،
و بنابراین ما به حباب هر کدام از عناصر بزرگ تمام
راه در سراسر آرایه.
و ما به طور موثر نیز به حباب تمام عناصر کوچک تماس
تمام راه در سراسر آرایه، TOO.
بنابراین هر یک از عناصر نفر به حرکت در سراسر همه از دیگر عناصر N.
به طوری که بدترین حالت است.
در بهترین حالت سناریو هر چند، این است
کمی متفاوت از مرتب سازی انتخابی.
آرایه است در حال حاضر طبقه بندی شده اند زمانی که ما در رفت.
ما لازم نیست را به هر گونه معاوضه در گذر نخست.
بنابراین ما ممکن است برای نگاه در عناصر کمتری، درست است؟
ما لازم نیست به تکرار این پردازش چند بار بیش از.
>> پس چه معنا است؟
پس چه بدترین حالت است برای مرتب سازی حبابی، و چه چیزی
بهترین حالت برای مرتب سازی حبابی؟
آیا شما این را حدس بزنید؟
در بدترین حالت شما مجبور به تکرار در تمام عناصر ازت n بار.
بنابراین بدترین حالت N مربع.
>> اگر آرایه کاملا مرتب شده هر چند، شما تنها
باید هر نگاه از عناصر یک بار.
و اگر شمارنده مبادله است که هنوز هم 0، شما می توانید می گویند این آرایه مرتب شده اند.
و به این ترتیب در بهترین حالت، این است در واقع بهتر از انتخاب
sort-- آن امگا N است.
>> من داگ لوید هستم.
این CS50 است.