خبرگزاری آیصد (جدیدترین و جذاب ترین اخبار ایران و جهان)

نشر توسط:admin Views 79 تاریخ : 2 خرداد 1395

Heap Sort بهتر است یا Merge Sort  یا Quick Sort :

چه تفاوتی بین کارایی این الگوریتم ها وجود دارد؟

مرتبه زمانی این مرتب سازی ها تقریبا شبیه به هم است.پس کدام یک از آن ها نسبت به دیگری کارایی بیشتری دارد؟

یکی از ارجحیت های heap sort و merge sort نسبت به quick sort :

مرتبه ی زمانی مرتب سازی سریع (quick sort) در بدترین حالت O(n^2) است.اما در دو الگوریتم دیگر O(nlogn) است.

از ارجحیت هایی که heapSort  نسبت به MergeSort دارد این است که این الگوریتم درجا  (in place) است.یعنی از حافظه ی اضافی استفاده نمی کند.در mergesort ما نیاز به یک حافظه ی کمکی داریم تا داده ها را در آن ذخیره کنیم.

فرض کنید یک سری داده ی مشابه داریم که می خواهیم آن ها را مرتب کنیم.اگر این داده ها را به heapsort  دهیم مرتبه زمانی آن mergesort ، O(n) مرتبه زمانی O(logn) و مرتبه زمانی   O(n^2) ,quicksort را خواهند داشت.

از طرفی در مرتب سازی سریع از یک pivot استفاده می شود و دو قسمت ایجاد شده هر کدام به صورت بازگشتی مرتب می شوند، که اگرpivot را به درستی تعیین نکنیم(مثلا maximum pivot  یا  minimum باشد). امکان دارد بدترین حالت در مرتبه زمانی یعنی O(n^2) پیش بیاید.

Merge sort یک الگوریتم stable است، در صورتی که quick وunstable ,heap  هستند.