مرتب سازی آرایه دو بعدی

[borghian]

بهترین نوع مرتب سازی برای آرایه دو بعدی براساس ستون چیست ؟
اگه برنامه‌ای موجود است الان میخوام؟

[amir_cpp]

خوب الگوریتم برای مرتب سازی زیاده، مثل حبابی، انتخابی، دودویی و ... .
اما فکر می کنم بهترینش دودویی باشه، اگه بخای کدشو می زارم.

[emad_67]

بهترین نوع مرتب سازی برای آرایه دو بعدی براساس ستون چیست ؟
اگه برنامه‌ای موجود است الان میخوام؟

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

[kiani.mehdi]

خوب الگوریتم برای مرتب سازی زیاده، مثل حبابی، انتخابی، دودویی و ... .
اما فکر می کنم بهترینش دودویی باشه، اگه بخای کدشو می زارم.

تا اونجایی که من میدونم دودویی یه الگوریتم جستجو هست نه مرتب سازی که پیچیدگی اون از



O(log n)

هست

البته ممکن منظورتون یه چیز دیگه باشه که من نمی دونم
اگه اینطوره بگید تا ما هم یاد بگیریم
البته فکر کنم منظورتون از دودویی نصف کردن آرایه و مرتب کردن زیر آرایه ها می باشد م در نهایت ادغام زیر آرایه ها که در این صورت باز هم به ان mergesort میگن
شاید هم واقعا مرتب سازی به نام دودویی هست و من نمیدونم
به هر حال اگه هست ممنون میشم راجع به اون نوضیح بدین

و اما در مورد سوال دوستمون :
الگوریتم ها مرتب سازی را میتونید در کتاب طراحی الگوریتم ها پیدا کنید
اکثرشون با پیچیدگی هاشون با هم مقایسه شدند

در حالت کلی بگم در مورد الگوریتم های مرتب سازی بهترین حالت الگوریتمی است که از
مرتبه




O(n log n)

باشه
چون ثابت شده که در مورد مرتب سازی نمی توان الگوریتمی بهتر از




O(n log n)


پیدا کرد
البته




O(n log n)


یک حالت کلی است

مثلا 2 تا الگوریتم با پیچیدگی های 2 به توان 2n+1 و 2 به توان 3n+5 هردو از مرتبه نمایی و اصطلاحا


O(2^n)

هستند ولی خوب الگوریتم اول مشخص است که بهتر است البته این تفاوت برای n های خیلی بزرگ آشکار میشه

امیدوارم مطالبم مفید بوده باشه
موفق باشید
مهدی کیانی

[amir_cpp]

خوب الگوریتم برای مرتب سازی زیاده، مثل حبابی، انتخابی، دودویی و ... .
اما فکر می کنم بهترینش دودویی باشه، اگه بخای کدشو می زارم.
حق با شماست، دودویی یه الگوریتم جستجو هستش!
اما من منظورم مرتب سازی سریع بود که تا حدودی مکانیزم کارش شبیه دودویی هست.
معذرت می خوام!:لبخند:

[someCoder]

چون ثابت شده که در مورد مرتب سازی نمی توان الگوریتمی بهتر از


O(n log n)

پیدا کردغلطه!
این موضوع در مورد مرتب سازی نیست، در مورد مرتب سازی بر اساس مقایسه (http://en.wikipedia.org/wiki/Comparison_sort) است که فقط یه حالت خاص از sort به حساب میاد. (و اتفاقا زیاد هم استفاده میشه)

برای مثال نقض هم میتونم Radix Sort (http://en.wikipedia.org/wiki/Radix_sort) رو مثال بزنم که (O(nk هست. (k تعداد رقمهای بزرگترن عدد در لیست در مبنایی که sort در اون مبنا انجام شده) که در اکثر موارد از nlogn کمتره.

اینم بدون که الگوریتم های سورت با (O(n هم هستند.