مرتب سازی پشته با الگوریتم بازگشتی – به زبان ساده

در این مطلب، روش مرتب سازی پشته با الگوریتم بازگشتی مورد بررسی قرار گرفته و سپس، قطعه کدهای مربوط به آن در زبان‌های برنامه‌نویسی گوناگون شامل C، «جاوا» (Java) و «سی‌شارپ» (#C) ارائه شده است. فرض می‌شود که یک پشته (Stack) به عنوان ورودی داده شده و هدف مرتب کردن آن با استفاده از روش بازگشتی است. فرض می شود در صورت سوال نیز گفته شده که امکان استفاده از هر ساختار حلقه‌ای، مانند for ،while و دیگر موارد وجود ندارد. تنها می‌توان از توابع «نوع داده انتزاعی» (Abstract Data Type | ADT)، شامل مواردی که در ادامه آمده است، روی پشته استفاده کرد.

is_empty(S) : Tests whether stack is empty or not.
push(S) : Adds new element to the stack.
pop(S) : Removes top element from the stack.
top(S) : Returns value of the top element. Note that this
function does not remove element from the stack.

مثال:

Input:  -3  <--- Top
        14 
        18 
        -5 
        30 

Output: 30  <--- Top
        18 
        14 
        -3 
        -5

این مساله، نوعی از مسائل معکوس کردن پشته است. ایده اصلی برای حل این مساله، آن است که همه مقادیر تا هنگامی که پشته خالی شود، در «پشته فراخوانی تابع» (Function Call Stack) نگه داشته شوند. هنگامی که پشته خالی شد، همه عناصر نگه داشته شده باید یکی یکی به صورت مرتب شده قرار بگیرند. در اینجا، مرتب بودن حائز اهمیت است.

مرتب سازی پشته با الگوریتم بازگشتی

می‌توان از الگوریتم زیر برای مرتب‌سازی عناصر پشته استفاده کرد.

الگوریتم زیر برای قرار دادن عناصر به صورت مرتب شده است.

نمایش بصری:

در ادامه، مرتب‌سازی پشته با استفاده از داده‌های مثال ارائه شده در بالا، انجام خواهد شد. ابتدا، باید همه عناصر را از پشته حذف و عناصر حذف شده را در متغیر temp ذخیره کرد. پس از حذف کردن همه عناصر، فریم پشته تابع به صورت زیر خواهد بود:

temp = -3 --> stack frame #1
temp = 14 --> stack frame #2
temp = 18 --> stack frame #3
temp = -5 --> stack frame #4
temp = 30 --> stack frame #5

اکنون، پشته خالی است و تابع «()insert_in_sorted_order» فراخوانی می‌شود و ۳۰ را در پایین پشته (از فریم پشته 5#) درج می‌کند. اکنون، پشته به صورت زیر است.

30 <-- top of the stack

اکنون، عنصر بعدی یعنی ۵- (از فریم پشته 4#) انتخاب می‌شود. از آنجا که ۳۰ > ۵- است، ۵- در پایین پشته درج می‌شود. اکنون، پشته به صورت زیر خواهد بود:

30 <-- top of the stack
-5

در ادامه، ۱۸ (از فریم پشته 3#) انتخاب می‌شود. به دلیل آنکه ۳۰ > ۱۸ است، ۱۸ قبل از ۳۰ قرار می‌گیرد. اکنون پشته به صورت زیر خواهد بود.

سپس، ۱۴ (از فریم پشته 2#) انتخاب می‌شود. با توجه به آنکه ۳۰ > ۱۴ و ۱۸ > ۱۴، زیر ۱۸ درج می‌شود. اکنون پشته به صورت زیر خواهد بود.

اکنون، ۳- (از فریم پشته 1#) انتخاب می‌شود. به دلیل آنکه ۳۰ > ۳ و ۱۸ > ۳-، زیر ۱۴ قرار می‌گیرد. اکنون، پشته به صورت زیر خواهد بود.

در ادامه، پیاده‌سازی الگوریتم بالا در چند زبان برنامه‌نویسی ارائه شده است.

الگوریتم بازگشتی برای مرتب سازی پشته در زبان C

فیلم آموزش ساختمان داده ها و پیاده سازی در سی پلاس پلاس C++‎ در فرادرس

کلیک کنید

الگوریتم بازگشتی برای مرتب سازی پشته در زبان جاوا

الگوریتم بازگشتی برای مرتب سازی پشته در زبان #C

فیلم آموزش برنامه نویسی سی شارپ #C – مقدماتی در فرادرس

کلیک کنید

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

می‌توان با انجام دادن تغییرات کوچکی در قطعه کدهای بالا، کاری کرد که پشته به صورت نزولی مرتب شود.

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

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

^^