حل تشریحی سوال شماره 6 حل مسئله

فرض کنید می خواهید الگوریتم مرتب سازی سریع (Quick sort) را برای یک آرایه A با اندازه n پیاده سازی کنید. اما شرایط زیر بر الگوریتم اعمال شده است:

شما فقط میتوانید از دو صف معمولی (Queues) استفاده کنید و دسترسی مستقیم به آرایه مجاز نیست.

برای انتخاب محور (Pivot)، همیشه باید عنصر میانی آرایه را در نظر بگیرید، اما پیدا کردن عنصر میانی باید از طریق یکی از صف ها انجام شود.

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

تقسیم آرایه به دو بخش و مرتب سازی آنها باید بدون استفاده از بازگشت (Recursion) انجام شود.

پیچیدگی زمانی این الگوریتم در بدترین حالت چیست؟