Quick sort

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

 

Quick sort

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

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

bubble sort

-insertion sort

-merge sort

-quick sort

-Distribution sorts

– Concurrent sorts

– Heap sort

-Radix sort

Counting sort

مرتب سازی سریع یکی از بهترین الگوریتم های مرتب سازی  است است که سرعت بسیار مناسبی دارد و اگر درست پیاده سازی شود یکی از سریع ترین الگوریتم ها خواهد بود . 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  آمده است :

 

Digg This
Reddit This
Stumble Now!
Buzz This
Vote on DZone
Share on Facebook
Bookmark this on Delicious
Kick It on DotNetKicks.com
Shout it
Share on LinkedIn
Bookmark this on Technorati
Post on Twitter
Google Buzz (aka. Google Reader)

۳۶ دیدگاه

پاسخ دهید

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