مرتب سازی هرمی تکرار شونده – به زبان ساده

در این مطلب، به «مرتب سازی هرمی تکرار شونده» (Iterative HeapSort) پرداخته‌ایم که در واقع همان الگوریتم مرتب سازی هرمی است که به روش تکرار شونده (Iterative) پیاده‌سازی شده است. همچنین، پیاده‌سازی الگوریتم مرتب سازی هرمی تکرار شونده در زبان‌های برنامه‌نویسی «سی‌پلاس‌پلاس» (++C)، «جاوا» (Java) و «پایتون» (Python) پیاده‌سازی شده است. «مرتب‌سازی هرمی» (HeapSort) گونه‌ای از الگوریتم‌های مبتنی بر مقایسه است که طی آن، ابتدا درخت بیشینه ساخته می‌شود و سپس عنصر ریشه با آخرین عنصر (به تعداد اندازه) جایگزین می‌شود و مشخصات هرم را هر بار نگهداری می‌کند تا در نهایت آن را مرتب کند. مثال زیر برای درک بهتر این مفهوم بیان شده است.

Input :  10 20 15 17 9 21
Output : 9 10 15 17 20 21 

Input:  12 11 13 5 6 7 15 5 19
Output: 5 5 6 7 11 12 13 15 19

در مثال اول، ابتدا باید هرم بیشینه ساخته شود. بنابراین، کار با عدد ۲۰ به عنوان فرزند آغاز می‌شود و والدین آن بررسی می‌شوند. در اینجا، ۱۰ کوچک‌تر است. بنابراین این دو با یکدیگر جا به جا می‌شوند. داریم: $$20\; 10\; 15\; 17\; 9\; 21$$. اکنون، فرزند ۱۷ بزرگ‌تر از والد خودش یعنی ۱۰ است. بنابراین، هر دو با هم جا به جا می‌شوند و ترتیب آن‌ها $$20\; 17\; 15\; 10\; 9\; 21$$ خواهد بود. اکنون، فرزند ۲۱ بزرگ‌تر از والد خود یعنی ۱۵ است. بنابراین، هر دو با یکدیگر جایگزین می‌شوند.

داریم: $$20\; 17\; 21\; 10\; 9\; 15$$. اکنون، ۲۱ بزرگ‌تر از والد خودش ۲۰ است. بنابراین: $$21\; 17\; 20\; 10\; 9\; 15$$. این «هرم بیشینه» (Max Heap) است. اکنون باید مرتب‌سازی اعمال شود. در اینجا باید اولین عنصر با آخرین عنصر جا به جا شود و در عین حال، خصوصیات هرم بیشینه نیز حفظ شود. بنابراین، بعد از اولین جا به جایی $$15\; 17\; 20\; 10\; 9\; 21$$ را داریم که این مورد، نقض خصوصیات هرم بیشینه است؛ بنابراین، باید آن را حفظ کرد. در نهایت، ترتیب به صورت زیر خواهد بود.

20 17 15 10 9 21
17 10 15 9 20 21
15 10 9 17 20 21
10 9 15 17 20 21
9 10 15 17 20 21

در اینجا، قسمت زیر خط‌دار، در واقع همان قسمت مرتب شده است.

مرتب سازی هرمی تکرار شونده در ++C

مرتب سازی هرمی تکرار شونده در جاوا

مرتب سازی هرمی تکرار شونده در پایتون ۳

خروجی قطعه کدهای بالا، به صورت زیر است.

Given array: 10 20 15 17 9 21 

Sorted array: 9 10 15 17 20 21

در اینجا، هر دو تابع buildMaxHeap و heapSort از درجه O(nlogn)‎ هستند.

فیلم مجموعه آموزش داده کاوی و یادگیری ماشین – مقدماتی تا پیشرفته در فرادرس

کلیک کنید

بنابراین، پیچیدگی زمانی کلی برابر با (O(nlogn است.

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

• مجموعه آموزش‌های ساختمان داده و طراحی الگوریتم
• آموزش ساختمان داده‌ها با C و ++C (همراه با حل نمونه سوالات کنکور ارشد)
• مجموعه آموزش‌‌های برنامه‌‌‌نویسی
• مرتب‌سازی پشته با الگوریتم بازگشتی — به زبان ساده
• مرتب‌سازی درجی (Insertion Sort) — به زبان ساده
• مرتب‌سازی حبابی و پیاده سازی آن — از صفر تا صد

^^