مرتب‌سازی داخلی
مرتب‌سازی داخلی (به انگلیسی: Internal sort) به خانواده‌ای از مرتب‌سازی‌ها گفته می‌شود که تمام عملیات‌های الگوریتم و ذخیره داده‌ها در حافظه اصلی برنامه نگهداری می‌شود.
در مقابل آن، خانواده مرتب‌سازی خارجی هستند که به علت زیاد بودن حجم داده‌ها، آنها در فضایی خارج حافظه برنامه نگهداری می‌شوند و هنگام اجرای برنامه در هر لحظه مقدار کمی از آنها مورد تحلیل قرار می‌گیرد.
از مرتب‌سازی‌های داخلی می‌توان مرتب‌سازی‌های درجا را نام برد.
ویژگی‌ها ویرایش
در این نوع مرتب‌سازی‌ها چون تمام عملیات‌ها داخل حافظه است معمولاً اندازه داده‌ها کوچک و محدود است. اما چون دسترسی به تمام داده‌ها سریع است، سرعت آن نسبتاً بالاست.[۱]
چه الگوریتم‌هایی برای این دسته مناسبند؟ ویرایش
در این دسته چون حافظه محدود است الگوریتم‌هایی کارایی بیشتری دارند که مقدار حافظه ای که مصرف می‌کنند حداکثر به اندازه ضریبی ثابت از اندازه داده‌ها بزرگتر باشد یا به‌طور دقیق تر از O(اندازه داده‌ها) باشد.[۲]
از الگوریتم‌هایی که این شرایط را دارند موارد زیر را می‌توان نام برد:
- الگوریتم مرتب‌سازی درجی
- الگوریتم مرتب‌سازی حبابی
- الگوریتم مرتب‌سازی سریع
- الگوریتم مرتب‌سازی با استفاده از پشته
یک مثال ویرایش
آرایه A:
برای i=۰ تا ۱-(اندازهA) انجام بده:
برای j برابر ۱-(اندازهA) تا j=i انجام بده:
اگر [A[j> A[j+1 :
جای [A[j و [A[j+1 را عوض کن.
این الگوریتم از نوع مرتب‌سازی داخلی است چون داده‌ها همیشه داخل همان حافظه اولیه هستند و تنها جایشان عوض می‌شود.
مقایسه با مرتب‌سازی خارجی ویرایش
در مقایسه با مرتب‌سازی خارجی حجم کمتری از داده‌ها را می‌تواند تحلیل کند چون تنها از حافظه داخلی برنامه استفاده می‌شود و حافظه خارجی موجود نیست.
اما از طرف دیگر در مقیاس یکسانی از داده، سرعت بیشتری دارد زیرا داده‌ها همیشه در دسترسند و در مرتب‌سازی خارجی برای دسترسی به داده‌ها باید از حافظه ای خارجی با سرعتی کمتر نسبت به رم خوانده شوند.[۳]