الگوریتم مرتب‌سازی سریع چیست؟

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

یکی از معروف‌ترین و محبوب‌ترین الگوریتم‌های مرتب‌سازی الگوریتم مرتب‌سازی سریع یا Quicksort است. از جمله سایر الگوریتم های مرتب سازی می توان به الگوریتم مرتب سازی ادغامی اشاره کرد. در این مقاله قصد داریم این الگوریتم را معرفی کنیم و خصوصیات و پیچیدگی‌های آن را بررسی کنیم. در انتها نیز نحوه پیاده‌سازی این الگوریتم را در زبان برنامه‌نویسی پایتون بررسی می‌کنیم.

الگوریتم مرتب‌سازی سریع چیست؟

الگوریتم مرتب‌سازی سریع یکی از الگوریتم‌های مرتب‌سازی از نوع تعویضی یا مقایسه‌ای است که بر اساس جا به جایی عناصر مختلف کار می‌کند. این الگوریتم دارای محبوبیت زیادی است و می‌تواند برای مرتب‌سازی داده‌های تصادفی بسیار مفید واقع شود. یکی از مزیت‌های این الگوریتم این است که برای مرتب‌سازی داده‌هایی که پراکندگی زیادی دارند نسبت به الگوریتم‌های دیگری نظیر مرتب‌سازی هرمی و مرتب‌سازی ادغامی بسیار بهتر عمل می‌کند.

الگوریتم مرتب‌سازی سریع چگونه کار می‌کند؟

این الگوریتم یک ساختمان از داده‌ها را برای ما مرتب می‌کند. کارایی این الگوریتم بسیار بالا است و بر اساس روش تقسیم و غلبه یا تقسیم و حل عملمی کند. این الگوریتم یک عنصر را به عنوان عنصر اصلی انتخاب می‌کند که به طور معمول این عنصر اولین عنصر داده‌ها است. سپس با استفاده از الگوریتم partition آرایه‌های دیگر مرتب‌سازی می‌شوند و آرایه‌های کوچک‌تر در یک طرف عنصر اصلی و آرایه‌های بزرگ‌تر در طرف دیگر قرار می‌گیرند. سپس عناصر موجود در هر سمت عنصر اصلی یا لولا را دوباره به همین طریق مرتب‌سازی می‌کنند و این کار تا حدی ادامه پیدا می‌کند تا تنها یک عنصر باقی می‌ماند.

مطلب پیشنهادی: پرامپت‌ نویسی چیست؟

عنصر محوری را چگونه انتخاب کنیم؟

همان طور که در بالا توضیح دادیم روش کار الگوریتم مرتب‌سازی به این صورت است که یک عنصر را به عنوان عنصر اصلی انتخاب می‌کنیم. سپس باقی داده‌ها با توجه به آن مرتب می‌شوند و این روند در زیر آرایه‌ها نیز ادامه پیدا می‌کند. عنصر محوری را می‌توانید به شیوه‌های مختلفی انتخاب کنید. راه‌های انتخاب عنصر محوری شامل موارد زیر است.

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

الگوریتم مرتب‌سازی دارای چه مراحلی است؟

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

انتخاب عنصر اصلی

در اولین مرحله لازم است یکی از داده‌ها را به عنوان داده اصلی انتخاب کنید. انتخاب این عنصر نقطه شکست آرایه را مشخص می‌کند و لیست داده‌های اولیه را تعیین می‌کند.

تقسیم

داده‌های مسأله را از عنصر انتخابی به ۲ نیمه تقسیم می‌کنیم. در این مرحله عناصر کوچک‌تر یا مساوی را در یک قسمت و عناصر بزرگ‌تر را در طرف دیگر قرار می‌دهیم.

تکرار و ترکیب

مراحل بالا را ادامه می‌دهیم و آن قدر تکرار می‌کنیم تا به آرایه‌های تک عضوی برسیم. در نهایت نیز زیرآرایه‌های مرتب شده را با یکدیگر ترکیب می‌کنیم.

گام‌های الگوریتم مرتب‌سازی سریع کدام‌ها هستند؟

در الگوریتم مرتب‌سازی داده‌های اصلی را مطابق با گام‌های زیر تقسیم‌بندی می‌کنیم.

گام اول

در اولین گام از میان داده‌ها یک عنصر اصلی انتخاب می‌کنیم. می‌توانی این کار را با روش‌های مختلفی انجام دهیم مثلاً اولین یا آخرین داده را به عنوان عنصر اصلی انتخاب می‌کنیم.

گام دوم

در این مرحله دو متغیر تحت عنوان i و j را تعریف می‌کنیم و آن‌ها را به اولین و آخرین عناصر لیست داده‌ها منتسب می‌کنیم.

گام سوم

تا زمانی‌که شرطlist[i] > pivot برقرار شود، مقدار i افزایش می‌یابد و سپس متوقف می‌شود.

گام چهارم

تا هنگام برقراری شرط list[j] < pivot، مقدار j کاهش پیدا می‌کند.

گام پنجم

اگر i < j باشد آنگاه، عناصر list[i] و list[j] را جا به جا می‌کنیم.

گام ششم

تا پیش از اینکه i > j شود، گام‌های ۳، ۴ و ۵ را تکرار می‌کنیم.

گام هفتم

عنصر Pivot را با عنصر list[j] جابه‌جا می‌کنیم.

پیچیدگی زمانی الگوریتم مرتب‌سازی سریع

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

پیچیدگی زمانی

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

پیچیدگی فضایی

پیچیدگی فضایی نشان می‌دهد که الگوریتم به چه میزانی از حافظه برای انجام عملکرد خود نیاز دارد. در واقع پیچیدگی فضایی نشان می‌دهد که یک الگوریتم برای مرتب‌سازی داده‌ها علاوه بر حجم داده‌های ورودی به چه میزانی از حافظه احتیاج دارد. صف در ساختمان داده نیز نشان دهنده همین مرتب سازی می باشد. الگوریتم مرتب‌سازی سریع یک الگوریتم درجا است و این مسأله باعث می‌شود که این الگوریتم به میزان حافظه زیادی علاوه بر داده‌های ورودی نیاز ندارد. به عبارت دیگر فضایی که این الگوریتم به آن نیاز دارد، برابر با میزان حافظه‌ای است که برای فراخوانی‌های بازگشتی تابع و پشته فراخوانی در حین اجرا لازم است.

مطلب پیشنهادی:ماشین لرنینگ چیست؟

الگوریتم مرتب‌سازی سریع چه کاربرد‌هایی دارد؟

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

آنالیز عددی

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

مدیریت پایگاه داده‌ها

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

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

مزایای الگوریتم مرتب‌سازی سریع چیست؟

الگوریتم مرتب‌سازی سریع دارای مزایای زیادی است که باعث محبوبیت فراوان آن شده‌اند. برخی از این مزایا شامل موارد زیر هستند.

بازدهی بالا

همان طور که اشاره کردیم الگوریتم مرتب‌سازی سریع دارای بازدهی بالایی است و می‌تواند در مواردی که با حجم بالایی از داده‌ها رو به رو هستیم بسیار کارآمد باشد.

مرتب‌سازی درجا

یکی از مزیت‌های مهم الگوریتم مرتب‌سازی سریع این است که داده‌ها را به صورت درجا مرتب می‌کند. این در واقع به این معنا است که این الگوریتم نیازی به حافظه کمکی برای ذخیره‌سازی نتایج و داده‌های موقتی ندارد.

پیاده‌سازی راحت

الگوریتم مرتب‌سازی سریع نسبت به سایر الگوریتم‌های مرتب‌سازی دارای منطق ساده‌ای است. این مسأله باعث می‌شود روش کار آن به سادگی قابل درک باشد و بتوان به سادگی آن را پیاده‌سازی کرد.

معایب الگوریتم مرتب‌سازی سریع

اگرچه الگوریتم مرتب‌سازی سریع دارای مزایای فراوانی است، اما معایبی نیز دارد. برخی از مهم‌ترین معایب این الگوریتم شامل موارد زیر هستند.

مرتب‌سازی ناپایدار

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

ایجاد قسمت‌های نامتعادل

همان طور که توضیح دادیم عنصر اصلی در میان داده‌های موجود می‌تواند به روش‌های مختلفی انتخاب شود. فرض کنید عنصر اصلی کوچک‌ترین یا بزرگ‌ترین داده در میان داده‌های موجود باشد. در این حالت ممکن است تقسیم‌بندی‌هایی که توسط این الگوریتم صورت می‌گیرد منجر به ایجاد برخی قسمت‌های نامتعادل شود. در نتیجه، این الگوریتم در بدترین حالت خود می‌تواند پیچیدگی زمانی برابر با Ο(n²) داشته باشد.

تأثیرگذاری عنصر اصلی

این که کدام عنصر را به عنوان عنصر اصلی انتخاب می‌کنید می‌تواند به صورت مستقیم بر روی عملکرد الگوریتم مرتب‌سازی سریع اثر بگذارد. به خصوص اگر داده‌های مورد نظر به طور تقریبی مرتب شده باشند این مسأله می‌تواند تأثیر بیشتری داشته باشد.

سربار بازگشتی

در الگوریتم مرتب‌سازی سریع فراخوانی‌های بازگشتی متعددی انجام می‌شود. این مسأله باعث می‌شود حافظه بیشتری مصرف شود و در اثر این مسأله احتمال وقوع خطا‌های سر ریز پشته یا به اصلاح Stack Overflow به خصوص هنگام کار با داده‌های حجیم افزایش می‌یابد.

تطبیق ناپذیری

یکی از معایب الگوریتم مرتب‌سازی سریع تطبیق ناپذیری است. این در واقع به این معنا است که حتی اگر داده‌های ورودی از قبل مرتب شده باشند این الگوریتم به این مسأله اهمیتی نمی‌دهد و داده‌ها را دوباره مرتب‌سازی می‌کند.

بازدهی ناکارآمد برای داده‌های کم

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

چگونه از ایجاد بدترین حالت در الگوریتم مرتب‌سازی سریع جلوگیری کنیم؟

برای جلوگیری از ایجاد بدترین حالت در الگوریتم مرتب‌سازی در جا راهکار‌هایی وجود دارد. برخی از مهم‌ترین این راهکار‌ها را در ادامه توضیح می‌دهیم.

الگوریتم مرتب‌سازی سریع تصادفی

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

انتخاب عنصر اصلی به صورت هوشمندانه

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

یکی از راهکار‌هایی که در این روش از آن استفاده می‌شود، این است که عنصر اصلی را نزدیک به میانه حقیقی داده‌ها انتخاب کنید. این کار به طور معمول باعث می‌شود زیرآرایه‌های متوازن‌تری ایجاد شوند. برای انجام این کار کافی است داده‌های ابتدایی، انتهایی و میانی را پیدا کنید و با استفاده از آن‌ها میانه را به دست بیاورید و سپس آن را به عنوان عنصر اصلی به کار ببرید.

روش Introspection

در طی این روش برای فراخوانی‌های بازگشتی که در طی این الگوریتم انجام می‌شود یک حد آستانه تعیین می‌شود و در صورتی که فراخوان‌های بازگشتی از تعداد مشخص شده بیشتر شود از یک الگوریتم جایگزین استفاده می‌شود.

پیش پردازش

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

مطلب پیشنهادی:الگوریتم کروسکال چیست؟

الگوریتم مرتب‌سازی سریع در پایتون چگونه پیاده‌سازی می‌شود؟

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

سخن نهایی

الگوریتم‌های فراوانی وجود دارند که از آن‌ها برای مرتب‌سازی داده‌ها و پردازش داده ها استفاده می‌شود. یکی از محبوب‌ترین این الگوریتم‌ها الگوریتم مرتب‌سازی سریع است که دارای مزایای زیادی نیز هست. الگوریتم مرتب‌سازی سریع از روش تقسیم و غلبه برای مرتب‌سازی حجم انبوهی از داده‌ها استفاده می‌کند. این الگوریتم یکی از داده‌ها را به عنوان عنصر اصلی انتخاب می‌کند و سپس داده‌های کوچک‌تر از آن را در یک طرف و داده‌های بزرگ‌تر را در طرف دیگر قرار می‌دهد و این گونه دو زیر آرایه ایجاد می‌کند. الگوریتم مرتب‌سازی سریع دارای کاربرد‌های زیادی است و مزایای زیادی نیز دارد. البته این الگوریتم نیز مانند دیگر الگوریتم‌ها دارای معایبی نیز هست که در بالا آن‌ها را توضیح دادیم.