موضوع مقاله: مرتب‌سازی روان | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # مرتب‌سازی روان | مقدمه: این مرتب‌سازی حالتی از مرتب‌سازی درهم است که توسط ادسخر دیکسترا در سال ۱۹۸۱ توسعه یافته‌است. | ## بخش 1: مرتب‌سازی روان | مزیت مرتب‌سازی روان این است که وقتی تعدادی از ورودی‌ها مرتب شده باشد پیچیدگی از شود در حالی که متوسط پیچیدگی مرتب‌سازی روان است بدون توجه به مرتب بودن یا نبودن ورودی‌ها بررسی اجمالی left برای اینکه یک آرایه را مرتب کنیم ابتدا آن را به رشته‌ای از پشته‌ها تقسیم می‌کنیم که هر پشته اندازه ی مساوی یکی از اعداد فیبوناچی دارد. فرایند تقسیم ساده‌است -چپ‌ترین گرهٔ آرایه بزرگترین پشته ممکن را ایجاد می‌کند و بقیهٔ عناصر باقی‌مانده هم به همین شکل تقسیم شوند. هر آرایه‌ای با هر طول می‌تواند به بخش‌هایی با اندازه تقسیم شود توضیح: مثلاً در کوچکترین حالت است هیچ دو پشته‌ای طول یکسان نخواهند داشت. این رشته یک رشته با طول اکیداً نزولی از پشته‌ها است هم چنین یک بیت از آرایه را می‌توانیم برای نگه داشتن که به عنوان اندازه پشته‌ها استفاده می‌شود در نظر بگیریم. توضیح: به آرامی به سمت 2n افزایش می‌یابد پس در نتیجه در هر آرایه‌ای همیشه یک وجود دارد که از نصف اندازه آرایه بزرگتر است.برای آرایه به اندازه ۲ استثنا وجود دارداما این آرایه را می‌توانیم به ۲ آرایه با اندازه ۱ و 0 ( و ) تقسیم کنیم که هر ۲ با عدد ۱ تعریف شوند و برابر ۱ هستند. هیچ دو پشتهی طولی با های متوالی و پیاپی نخواهند داشت به جز دو عدد آخر که ممکن است چنین حالتی داشته باشند. اگر هیچ عنصری در چپ وجود نداشته باشد (حتی یک تک عنصر) بعد از بکار بردن دو و (متوالی) ما می‌توانیم این دو را ترکیب کنیم و عنصری بزرگتر با نام بسازیم و اگر ما این کار را انجام ندهیم (ترکیب) بعد از و هیچ عنصر دیگری وجود نخواهد داشت. | ## بخش 2: مرتب‌سازی روان | هر پشته دارای عنصری بنام اندازه اندازه است که از چپ به راست مثل یک پشته تفاضلی سازمان دهی شده‌است و به ترتیب از چپ به راست دارای عنصرهای و ویک گرهٔ ریشه‌است که ابتدا برای پشته‌ها با طول و استثنا دارد (چون و برابر ۱ هستند). هر پشته این خاصیت پشته را که گرهٔ ریشه همیشه بزرگتر مساوی گره‌های فرزند آن ریشه‌است را نگه می‌دارد و ریشهٔ پشته‌ها تمام این خاصیت را که گرهٔ ریشه در هر پشته بزرگتر مساوی گرهٔ ریشهٔ پشته چپ آن است را نگه دارد. نتیجه این است که راست‌ترین گره در ریشه همیشه از بقیهٔ گره‌ها بزرگتر مساوی خواهد بود و مهمتر از همه اینکه آرایه‌ای که اکنون مرتب شده برای اینکه مجموعهٔ معتبری از پشته‌ها شود نیازی به باز آرایی ندارد. این دنباله بوسیلهٔ اضافه کردن عنصر به راست پشته افزایش می‌یابد (بزرگ می‌شود) و بوسیلهٔ جابجا کردن عناصر (swap) خاصیت دنباله‌ای و خاصیت پشته‌ای حفظ شود. از این نکات می‌فهمیم که راست‌ترین عنصر هر دنباله‌ای از پشته‌ها بزرگترین عنصر آن پشته‌است و بنابراین هر عنصر سر جای اصلی خود قرار دارد عملیات یک لحظه الگوریتم بهینه‌سازی ادسخر دیکسترارا نادیده بگیرید. افزایش رشته بوسیله اضافه کردن عنصر به راست عناصر موجود کاهش رشته بوسیلهٔ حذف کردن راست‌ترین عنصر (ریشهٔ هیپ قبلی) و حفظ و ذخیرهٔ هیپ و موقعیت رشته افزایش رشته بوسیله اضافه کردن عنصر به راست اگر مثلاً آخرین ۲ هیپ به سایزهای و باشد عنصر جدیدی که اضافه کنیم گرهٔ ریشهٔ یک هیپ بزرگتر به سایز شود که این هیپ لازم ندارد که خاصیت هیپ را داشته باشد. اگر مثلاً آخرین دو هیپ متوالی نبودند بعد از راست‌ترین عنصر یک هیپ جدید به سایز ۱ ایجاد می‌شود که در حقیقت این همان هست. | ## بخش 3: مرتب‌سازی روان | بعد از این خصوصیات رشته و هیپ باید ذخیره شود به شکل زیر این کار انجام شود: راست‌ترین هیپ را به عنوان (current)هیپ انتخاب کنیم. بهینه‌سازی : اگر هیپ جدید قصد دارد قسمتی از هیپ بزرگتر شود خودتان را برای ایجاد رشتهٔ خصوصیات زحمت ندهید. این کار فقط وقتی لازم است که یک هیپ در دسترس است و تنها کاری که می‌کند سایز نهایی را می‌دهد. بعد از اینکه این کار انجام شد نگاه کنید چگونه بسیاری از عناصر، چپ هیپ جدید به سایز هستند حال اگر هیپی با مقدار 1+ وجود داشت این هیپ ادغام می‌شود. خصوصیات هیپ را در راست‌ترین هیپ ذخیره نکنید، اگر حالا آن هیپ یکی از هیپ‌های نهایی رشته شود سپس خصوصیات رشته را ذخیره کنید. البته هر موقع که یک هیپ چدید ایجاد می‌شود بعد از اضافه شدن، راست‌ترین هیپ جدید از راست‌ترین هیپ قبل بزرگتر نیست و خصوصیات هیپ نیاز دارند ذخیره شوند. کاهش رشته بوسیله حذف راست‌ترین عنصر اگر راست‌ترین عنصر سایز ۱ دارد دیگر هیچ کاری لازم نیست انجام دهید. | ## جمع‌بندی | اگر راست‌ترین هیپ سایز ۱ نداشت سپس ریشه را حذف کنید سپس ۲ هیپ قبلی (sub-heap)را مثل عضوهای رشته نمایش دهید.