تبلیغات


الگوریتم های مرتب سازی: مرتب سازی سریع (Quick-sort)

اشتراک گذاری
Share on FacebookTweet about this on TwitterShare on Google+Share on LinkedInPin on PinterestPrint this pageEmail this to someone

 

Quick sort

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

– مفهوم مرتب سازی

bubble sort

-insertion sort

– Heap sort

-Radix sort

Counting sort

-merge sort

-quick sort

-Distribution sorts

– Concurrent sorts

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

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

تابع  partition   :

 

 

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

partition job

 

 

partition 1

partition 2partition 3partition 4

 

partition 6

partition 7

 

partition 9

partition 10

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

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

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

 


تبلیغات:

۳۲ دیدگاه

نظر خود را بنویسید.

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