• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۱۲۸ مگابایت

---

مرتب سازی سریع از جمله روش‌های محبوب و با سرعت بالای برای مرتب کردن داده‌ها محسوب می‌شود. این روش هم مثل روش ادعامی از الگوریتم تقسیم و حل برای مرتب کردن داده‌ها استفاده می‌کند. به این ترتیب که داده‌ها را به دو قسمت مجزا تقسیم و با مرتب‌کردن آن‌ها کل داده‌ها را مرتب می‌کند. برای اینکار یکی از داده‌ها(مثلا داده اول) به عنوان محور انتخاب می‌شود. داده‌ها براساس محور طوری چینش می‌شوند که همه‌داده‌های کوچکتر از محور، سمت چپ و داده‌های بزرگتر یا مساوی با آن در سمت راستش قرار می‌گیرند. با مرتب کردن دو قسمت به دست آمده کل داده‌ها مرتب می‌شوند. در این حالت مثل روش ادغام نیازی به ادغام کردن داده‌ها نیست، چرا که قسمت سمت راست همگی از قسمت سمت چپ کوچکتر هستند و بالعکس. مثلاً اعداد صحیح زیر را در نظر بگیرید:

5 61 9 0 4 5 15 3 1 14 10

عدد 5 را به عنوان محور در نظر می گیریم. داده‌ها به این صورت بازچینی می‌شوند:

1 0 4 3 1 4 5 6 9 5 15 10

همانطور که مشاهده می‌کنید اعداد سمت چپ عدد 5 همگی از 5 کوچکتر اعداد سمت راست همگی بزرگتر یا مساوی آن هستند. در تصویر زیر چگونگی انجام این الگوریتم نشان داده شده است. با این تفاوت که محور الگوریتم، عنصر وسط در نظر گرفته شده است:

برنامه‌ای بنویسید که یک رشته از کاربر دریافت کند و سپس رشته مرتب شده را چاپ کند.

ورودی

در تنها خط ورودی یک رشته از اعداد به شما داده می‌شود.

اعداد از ۱۰۰۰،۰۰۰،۰۰۰ کوچکترند.

همچنین تعداد اعداد از ۵۰۰،۰۰۰ کمتر است.

خروجی

در تنها خط خروجی اعداد را به صورت مرتب شده صعودی چاپ کنید.

مثال

نمونه ورودی ۱

0 1 5 3 6 2 4

نمونه خروجی ۱

0 1 2 3 4 5 6