بهترین روش برای ذخیره 100000 اعداد در آرایه

[ByRoad]

سلام

می خواستم بدونم اگه اعداد در رنج بالا را بخوام در ارایه ذخیره کنم از چه راهی برم بهتر و راحتر هست

مثلا اگه بخوام اطلاعات رو مرتب یا جستجو کنم راحت باشم


مرسی.

[Developer Programmer]

یعنی چی؟
میخوای ده هزار عدد رو توی آرایه مرتب کنی؟ خوب به چیدمان اعداد در آرایه هم بستگی داره.

ببین مرتب سازی تعویضی و انتخابی، کلا n^2 تا مقایسه انجام میدن پس به نظر میاد هردو یکسان عمل میکنن... اما اگر آرایه از قبل مرتب باشه، مرتب سازی تعویضی Flip (یا همون Swap) انجام نمیده پس تا اینجا تعویضی بهتر بود... اما اگه رکوردهات خیلی بزرگ باشه، انتخابی بهتر عمل میکنه چون انتساب رکوردهاش از مرتبه n هست اما تعویضی از مرتبه n^2.

مرتب سازی درجی، در بدترین حالت n^2 تا میره و در بهترین حالت( آرایه از قبل مرتب باشه) تنها n تا مقایسه انجام میده. پس از تعویضی و انتخابی بهتره... اما بازهم چون انتساب رکوردهاش از مرتبه n^2 هست در رکوردهای بزرگ، انتخابی بهتر عمل میکنه.

مرتب سازی سریع هم که در بهترین حالت و حالت متوسط مثل بدترین حالت ادغامی عمل میکنه... پس ادغامی میتونه بهتر باشه... اما انتساب رکوردهای ادغامی 2nlogn (و در حالت اصلاح شده ، صفر) است و در مرتب سازی سریع nlogn است.

Heap Sort هم که از مرتبه 2nlogn و انتساب رکوردهاش nlogn.


البته باید فضای مورد نیاز رو هم در نظر بگیری؛ مثلا مرتب سازی ادغامی، درجا(inplace) نیست چون به ازای n عدد به 2n تا جا نیاز داره...اما مرتب سازی سریع، تنها logn !!

گاهی هم میشه که آرایه اعداد تکراری داشته باشه، (مثلا 5 تا یک) در این صورت مرتب سازی جبابی و درجی و ادغامی اونها رو جابجا نمیکنن ( به اصطلاح متعادل هستن) اما مثلا heap sort و تعویضی و سریع، متعادل نیستن.