الگوریتم مرتب سازی سریع یا Quick-sort

در دو پست قبل مفهوم مرتب سازی و مرتب سازی حبابی (Bubble sort) را بررسی کردیم. امروز می خواهیم به مرتب سازی سریع  (Quick sort ) بپردازیم. قبل از این که به ادامه بحث بپردازیم یک مرور بکنیم از سایر الگوریتم ها که در روز های آینده آن ها را بررسی خواهیم کرد:

مرتب سازی سریع

مرتب سازی سریع یکی از بهترین الگوریتم های مرتب سازی  است است که سرعت بسیار مناسبی دارد و اگر درست پیاده سازی شود یکی از سریع ترین الگوریتم ها خواهد بود . Quick sort  یک روش مرتب سازی بازگشتی است، البته ممکن است این سوال برای شما پیش بیاید اگر بازگشتی است پس چرا می گوییم از لحاظ حافظه و سرعت خوب است دلیلش این است که این الگوریتم دقیقا فیتِ کش است .

هسته quick sort تابع partition  است .

تابع  partition   :

این تابع عنصر اول بازه ای را که قرار است رویش عمل کند را در نظر می گیرد  و بعد این تابع عنصر ها رو به ۲ دسته تقسیم می کند آن هایی که بزرگ تر از عنصر اول هستند و آن هایی که کوچک تر از عنصر اول هستند و عنصر اول را بین این دو دسته قرار می دهد و بعد مکانی را که عنصر ما بین این دو دسته قرار دارد را بر می گرداند . اول کد بالا را خوب نگاه کنید و بعد عکس های زیر را ببینید تا تابع partition  را بهتر درک کنید :

partition job

 

 

partition 1

partition 2partition 3partition 4

 

partition 6

partition 7

 

partition 9

partition 10

حالا می رویم سراغ خود تابع مرتب سازی سریع  Quick sort  :

همین طور که می بینید quick sort  یک الگوریتم بازگشتی است که مرتب  partition  و خود را را فرا می خواند این کار را می کند تا زمانی که  آرایه هایی به طول یک به دست آید  و آرایه به طول یک خود مرتب است و اینگونه است که با استفاده از روش تقسیم و حل می توانیم آرایه را سورت کنیم.

در کد زیر تابع پارتیشن (تقسیم) و مرتب سازی سریع به همراه یک تست در Main  آمده است :

 

کد کلاس مرتب سازی سریع (Quick sort) به زبان جاوا:

 

۲۷ نظر

  • سلام. چطور میتونم قسمت پارتیشن و کوییک سورت رو در یک تابع بازگشتی بنویسم؟!

    • سلام.
      می تونید در محل فراخوانی تابع partition (در تابع Quick_sort) ، بدنه تعریف اون رو بذارید و به جای دستور

      به سادگی مقدار i رو به q انتساب بدید.
      موفق باشید

  • سلام چجوری میتونم مرتب سازی سریع رو به زبان پایتون براتون بفرستم؟

  • واقعا ممنونم خیلی خوب بود

  • محمد روشنی

    سلام ،
    استفاده کردیم ….
    از زحمات شما مچکرم.

  • سلام خسته نباشید
    میخواستم بدونم ک کدام یک از مرتب سازیهای مبتنی بر مقایسه در بهترین حالت، دارای مرتبه زمانی بهتری است؟
    ممنون میشم پاسخ بدین

    • در حالت متوسط Quick-sort، با داشتن درجه زمانی ((O(nlg(n و سربار حافظه بسیار کم، سریع ترین عملکرد را دارد.
      البته برای جلوگیری از به وجود آمدن درجه زمانی (O(n^2 در Quick-sort در بدترین حالت، Quick-sort با روش میانه سه، پیاده سازی می شود.

  • سلام
    اگه در مرتب سازی سریع بجای انتخاب عنصر اول بعنوان عنصر محوری ، عنصر وسط بعنوان عنصر محوری انتخاب شود الگوریتم آن به چه صورت خواهد بود؟
    ممنون میشم جوابشو به ایمیلم ارسال کنید

    • از لحاظ آماری و با توجه امید ریاضی محاسبه شده برای مرتب سازی سریع، تفاوتی ایجاد نمیشه

  • سلام خیلی سایت خوبی دارید واقعا کداتون خیلی خوب و کاربردی هست

    مرتب سازی ادغامی راهم اگر دارید بذارید ممنون میشم

  • سلام میشه برام سورس کد الگوریتم quick sort به زبان ++c را ایمیل بکنید ممنون از همکاری شما و تلاش برای بهتر شدن معلومات آموزشی ما….

  • سلام میشه لطف کنید کد radix sortبرای اعداد ۳۲ بیتی برام ایمیل کنید ممنون

  • سلام
    میخواستم الگوریتم در روش مرتب سازی به غیر از حبابی همراه با توضیح و کدشون برام ایمیل کنید

    • فرهاد دلیرانی

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

  • با سلام
    ببخشید اگر بخوام radix sort رو برای اعداد ۳۲ بیتی بنویسم چیکار کنم؟میشه برام ایمیل کنید ممنون

  • سیاوشی

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

نظرتان را برای ما بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *