sorting a;gorithm

مرتب سازی مقایسه ای و شمارشی

جهت مرتب سازی یک حجم از دیتای ورودی دو مکانیزم قالب مرتب سازی شمارشی و مرتب سازی مقایسه ای وجود دارد. حد پایین مجانب مرتب سازی مقایسه ای برابر ((Θ(nlog(n است، که در الگوریتم های مرتب سازی هیپ و مرتب سازی ادغام پیاده شده اند. کاهش مجانب پایین در الگوریتم های شمارشی محقق شده است. ازجمله آن می توان مرتب سازی مبنایی نام برد.

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

جدول1: مقایسه الگوریتم های مرتب سازی مختلف از این لینک آورده شده است.

نام بهترین میانگین بدترین حافظه پایدار مقایسه‌ای روش توضیحات
مرتب‌سازی حبابی (Bubble sort) (O(n (O(n۲ (O(۱ بله بله جابجایی Times are for best variant
Cocktail sort (O(n (O(n۲ (O(۱ بله بله جابجایی
Comb sort (O(n log n (O(n log n (O(۱ خیر بله جابجایی
Gnome sort (O(n (O(n۲ (O(۱ بله بله جابجایی
Selection sort (O(n۲ (O(n۲ (O(n۲ (O(۱ خیر بله گزینشی
Insertion sort (O(n (O(n۲ (O(۱ بله بله درجی
Shell sort (O(n log n (O(n log۲n (O(۱ خیر بله درجی Times are for best variant
Binary tree sort (O(n log n (O(n log n (O(۱ بله بله درجی
Library sort (O(n (O(n log n (O(n۲ ε+۱)n) بله بله درجی
Merge sort (O(n log n (O(n log n (O(n بله بله Merging
In-place merge sort (O(n log n (O(n log n (O(۱ بله بله Merging Times are for best variant
Heapsort (O(n log n (O(n log n (O(۱ خیر بله گزینشی
Smoothsort (O(n (O(n log n (O(۱ خیر بله گزینشی
Quicksort (O(n log n (O(n log n (O(n۲ (O(n خیر بله Partitioning Naive variants use (O(n space
Introsort (O(n log n (O(n log n (O(n log n (O(n خیر بله Hybrid
Pigeonhole sort (O(n+k (O(n+k (O(k بله خیر Indexing
Bucket sort (O(n (O(n (O(n۲ (O(k بله خیر Indexing
Counting sort (O(n+k (O(n+k (O(n+k بله خیر Indexing
Radix sort (O(nk (O(nk (O(n بله خیر Indexing
Patience sorting (O(n (O(n log n (O(n خیر بله درجی تمام زیر دنباله‌های صعودی را با (O(n log (log(n پیدا می‌کند.

Sharing is caring!

پاسخ دهید

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