مرتب کردن آرایه [بایگانی]

sa1378

سه شنبه 27 آبان 1393, 16:28 عصر

سلام
یه سوال ساده و کلاسیک هست که میگه با کمترین تعداد جابجایی یا swap یه آرایه رو مرتب کنین
میخواستم بدونم کمترین اوردرش چنده؟
و الگوریتمش چجوری میشه؟

omid_kma

سه شنبه 27 آبان 1393, 18:56 عصر

کمترین تعداد swap اوردر n هست یا الگوریتم هایی مثل radix sort یا counting sort یا selection sort
الگوریتم +‌ مقایسه تعداد swap ها این جا هست :‌ http://www.cs.carleton.edu/faculty/adalal/teaching/fall03/cs127/notes/nov03.pdf

البته چیزی که داخل الگوریتم های مرتب سازی بیشتر مهم هست time complexity هست که معیارش تعداد مقایسه هست و الگوریتم selection sort چون تعداد مقایسه هاش از (O(n^2 هست برای تعداد بالا بهینه نیست .
radix sort , counting sort هم فقط برای مرتب سازی رشته ها و عدد ها قابل استفاده ان .