موضوع مقاله: مرتب‌سازی سریع | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # مرتب‌سازی سریع | مقدمه: کوییک‌سورت ، یکی از الگوریتم‌های مرتب‌سازی است که به‌دلیل مصرف حافظه کم، سرعت اجرای مناسب و پیاده‌سازی ساده بسیار مورد قبول واقع شده‌است. | ## بخش 1: مرتب‌سازی سریع | این الگوریتم طی مراحل بازگشتی زیر یک روش تقسیم و غلبه برای مرتب کردن داده‌ها ارائه می‌نماید: ۱- انتخاب عنصر محوری: یکی از عناصر آرایه به عنوان عنصر محوری (pivot) - به عنوان مثال عنصر اول - انتخاب می‌شود. ۲- تقسیم آرایه: چینش عناصر آرایه به قسمی تغییر داده می‌شود که تمامی عناصر کوچکتر یا مساوی محور در سمت چپ آن، و تمامی عناصر بزرگتر در سمت راست آن قرار بگیرند. ۳- مرتب‌سازی بازگشتی: زیر‌آرایه‌های چپ و راست به روش مرتب‌سازی سریع مرتب می‌شوند. i، ۱، ۲، ۳، ۴، ۵، ۶، ۷، ۸، ۹، ۱۰، i، P A[i]، ۶۵، ۷۰، ۷۵، ۸۰، ۸۵، ۶۰، ۵۵، ۵۰، ۴۵، ∞، ۲، ۹ جا به جایی ۴۵ با ۷۰: ۹ ،۲، ∞ ،۷۰ ،۵۰ ،۵۵ ،۶۰، ۸۵ ،۸۰ ،۷۵، ۴۵ ،۶۵ جا به جایی ۷۵ با ۵۰: ۸ ،۳، ∞ ،۷۰ ،۷۵ ،۵۵ ،۶۰ ،۸۵ ،۸۰ ،۵۰ ،۴۵ ،۶۵ جا به جایی ۸۰ با ۵۵: ۷ ،۴، ∞، ۷۰ ،۵۰ ،۸۰ ،۶۰ ،۸۵ ،۵۵ ،۷۵ ،۴۵ ،۶۵ جا به جایی ۸۵ با ۶۰: ۶ ،۵، ∞ ،۷۰ ،۵۰ ،۸۰ ،۸۵ ،۶۰ ،۵۵ ،۷۵ ،۴۵ ،۶۵ جا به جایی ۶۵ با ۶۰: ۵ ،۶، ∞ ،۷۰ ،۵۰ ،۸۰ ،۸۵ ،۶۵ ،۵۵ ،۷۵ ،۴۵ ،۶۰ الگوریتم انتخاب kامین عنصر کوچک آرایه [A[1..n فرض کنید که بعد از فراخوانی الگوریتم Partition عنصر افراز در مکان j ام قرار بگیرد، در این صورت بدیهی است که j-1 عنصر آرایهٔ کوچکتر یا مساوی A[j] است و n-j عنصر باقی‌مانده بزرگتر یا مساوی آن خواهد بود؛ بنابراین سه حالت زیر امکان‌پذیر است: اگر k<j آنگاه kامین عنصر کوچکتر آرایه در A[1...j-1] قرار دارد. این کار با تعویض عنصر [ A[r با عنصری که از [A[p..r به‌طور تصادفی انتخاب می‌شود انجام می‌دهیم. این تغییر که در آن به‌طور تصادفی از ادامه r...p یک نمونه انتخاب می‌کنیم، اطمینان می‌دهد که عنصر محوری [x= A[r با احتمال برابر می‌تواند هر یک از r-p+1 عنصر زیر آرایه باشد. چون عنصر محوری به شکلی تصادفی انتخاب می‌شود انتظار داریم تقسیمات آرایه ورودی در حالت میانگین به شکل مناسبی متوازن باشد. هر تکرار حلقه for یک مقایسه انجام می‌دهد، مقایسه بین عنصر محوری و عنصر دیگری از آرایه A. بنابراین اگر بتوانیم تعداد کل دفعاتی که این مقایسه‌ها اجرا می‌شود را محاسبه کنیم، می‌توانیم کل زمانی را که در حلقه for در طی اجرای کامل quickSort صرف می‌شود را محدود کنیم. | ## بخش 2: مرتب‌سازی سریع | پیاده‌سازی صنعتی الگوریتم مرتب‌سازی در دنیای واقعی برای آرایه نسبتاً کوچک مناسب نیست. برای همین پیشنهاد می‌گردد برای آرایه‌هایی از طول کمتر از ۷ از مرتب‌سازی‌های دیگر مانند مرتب‌سازی درجی یا حبابی استفاده شود. به علاوه به جای پیاده‌سازی بخش partition به صورت عادی با احتمالاتی می‌توان از میانه ۹ برای آرایه‌های بزرگ (بیش از ۴۰ درایه) و میانه ۳ برای ارایه‌های متوسط (کمتر از ۴۰ درایه) و عضو وسط برای آرایه‌های کوچک استفاده کرد. به علاوه در چنین پیاده‌سازی‌هایی ابتدا اعداد صفر (برای آرایه از اعداد مثبت) را ابتدا به شروع آرایه منتقل می‌کنند. و همچنین درایه‌های غیر عددی را نیز هندل می‌کنند تا در اجرای الگوریتم اختلالی به وجود نیاورد. برای توضیحات بیشتر دربارهٔ نسخه‌های بهینه مرتب‌سازی سریع می‌توانید به مرجع بنتلی و مک ایلوری مراجعه نمایید. زمان اجرا مرتب‌سازی سریع چه در پیاده‌سازی عادی و چه در پیاده‌سازی احتمالی در حالت متوسط در زمان اجرای اجرا می‌شود. در اکثر تقسیمات ممکن، Partition دو زیر مسئله ایجاد می‌کند که اندازهٔ هر یک از آن‌ها بیش از n/2 نیست، در این حالت، مرتب‌سازی سریع خیلی سریع تر انجام می‌شود، لذا موازنه برابر دو طرف تقسیم در هر مرحله از بازگشت، الگوریتمی ایجاد می‌کند که به‌طور مجانبی سریع تر است. بدترین حالت تقسیم‌بندی: بدترین حالت برای مرتب‌سازی سریع هنگامی رخ می‌دهد که روال تقسیم‌بندی یک زیر مسئله با n-1 عنصر و یک زیر مسئله با ۰ عنصر ایجاد کند. | ## بخش 3: مرتب‌سازی سریع | چون فراخوانی بازگشتی روی آرایه‌ای با اندازهٔ ۰، دقیقا که همان است را برگردانده و رابطهٔ بازگشتی برای زمان اجرا به این صورت می‌باشد:. به‌طور شهودی اگر هزینه‌های ایجاد شده در هر مرحله بازگشت را با هم جمع کنیم یک سری حسابی به دست می‌آوریم که برابر است؛ بنابراین زمان اجرای مرتب‌سازی سریع در بدترین حالت بهتر از مرتب‌سازی درجی نیست. علاوه بر این، زمان اجرای زمانی نیز که که آرایه ورودی از قبل مرتب باشد رخ می‌دهد، در شرایطی مشابه، مرتب‌سازی درجی در زمان اجرا می‌شود. حتی اگر سطح جدیدی با نامتوازن‌ترین تقسیم‌بندی ممکن را در بین این سطوح اضافه کنیم زمان کل، باقی می‌ماند. ویژگی‌های مرتب‌سازی سریع ۱- پیچیدگی زمانی اجرای الگوریتم در بهترین حالت (Ө(n log n و در بدترین حالت (Ө(n2 است. با استفاده محاسبات ریاضی می‌توان نشان داد در حالت متوسط نیز مرتبه اجرا (Ө(n log n است. ۳- زمانی که تعداد عناصر آرایه کم باشد، سرعت اجرای مرتب‌سازی درجی بهتر از مرتب‌سازی سریع است. به همین دلیل طی مراحل بازگشتی مرتب‌سازی سریع، اگر طول بازه عدد کوچکی باشد، معمولاً بازه با مرتب‌سازی درجی مرتب می‌شود. | ## جمع‌بندی | اگرچه انتخاب عنصر محوری مناسب باعث بالا رفتن کارایی الگوریتم می‌شود، اما عموماً هزینه لازم برای یافتن چنین محوری بالا بوده و مقرون به صرفه نیست.