مرتب‌سازی هرمی: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
جز ربات: مرتب‌سازی رده‌ها؛ زیباسازی |
بدون خلاصۀ ویرایش |
||
خط ۵۵:
روال HEAPSORT زمان (O(n lgn را صرف می‌کند چون فراخوانی BUILD-HEAPزمان (O(n و هر یک از n-1 فراخوانی MAX-HEAPIFY زمان
(O(lgn را صرف می‌کند.
== بررسی فضای مصرفی مرتب‌سازی هرمی ==
در روش بحث شده برای مرتب کردن n عنصر، دو آرایه n عنصری نیاز است. یکی از این آرایه‌ها عناصر را به فرم درخت heap به عنوان ورودی الگوریتم، و دیگری عناصر مرتب شده را به عنوان خروجی الگوریتم شامل می‌شوند. در چنین حالتی این الگوریتم یک روش مرتب‌سازی درجا نیست. با اندکی تغییر در روش پیاده‌سازی الگوریتم می‌توان عملکرد دو آرایه را در یک آرایه ادغام کرده، و میزان حافظه مصرفی را کاهش داد.
درخت min-heap مثال فوق را در نظر بگیرید. با حذف عدد یک به عنوان گره ریشه درخت و اعمال تغییرات لازم به نتیجه زیر می‌رسیم:
خط عمودی پررنگ، انتهای اطلاعات درخت در آرایه را نشان می‌دهد. خانه شماره 6 حاوی اطلاعات سوخته و بلا استفاده است. پس می‌توانیم عنصر حذف شده را در آن قرار دهیم:
توجه داشته باشید که در حال حاضر درخت از پنج عنصر تشکیل شده است و عنصر ششم آرایه از عناصر درخت نیست. به همین ترتیب با حذف مجدد گره ریشه با مقدار 4 آرایه زیر حاصل می‌شود:
و با درج عنصر حذف شده در محل بلا استفاده:
به همین ترتیب با تکرار الگوریتم نتیجه نهایی حاصل می‌شود:
روش مرتب‌سازی انتخابی (Selection Sort) یکی از روش‌های اولیه مرتب‌سازی بر اساس مقایسه عناصر است. این الگوریتم طی چند مرحله عناصر لیست را به صورت صعودی یا نزولی مرتب می‌کند. به این ترتیب که در هر مرحله با بررسی عناصر نامرتب، بزرگترین (یا کوچکترین) عنصر را پیدا کرده، و به انتهای لیست منتقل می‌کند.
لیست اعداد زیر را در نظر بگیرید، که باید به صورت صعودی (کوچک به بزرگ) مرتب شود:
2 8 4 1 7
در مرحله اول، کل لیست از ابتدا تا انتها بررسی شده، و بزرگترین عنصر با عنصر انتهای لیست نامرتب جابجا می‌شود:
1) 2 8 4 1 7 -> 2 7 4 1 8
در مرحله دوم، پیمایش از ابتدای لیست تا عنصر چهارم صورت گرفته، و بزرگترین عنصر با عنصر انتهای آن جابجا می‌شود:
2) 2 7 4 1 8 -> 2 1 4 7 8
علت این که چرا عنصر پنجم بررسی نمی‌شود کاملا مشخص است. این عنصر در مرحله قبل به عنوان بزرگترین عنصر به انتهای لیست منتقل شده است، و به طور حتم نیاز به جابجایی ندارد.
در مرحله سوم، عناصر اول تا سوم بررسی شده و بزرگترین عنصر به انتهای آن منتقل می‌شود:
3) 2 1 4 7 8 -> 2 1 4 7 8
و در مرحله آخر دو عنصر باقیمانده مقایسه می‌شوند:
4) 2 1 4 7 8 -> 1 2 4 7 8
و به این ترتیب لیست مرتب می‌شود.
== منابع ==
| |||