وبلاگ رسمی مهدی غلامی میاندهی

 تابع مرتب سازی درجی (Insertion Sort) در ++C

مرتب‌ساز درجی (Insertion Sort) یک الگوریتم مرتب‌سازی ساده بر مبنای مقایسه است. این الگوریتم برای تعداد داده‌های زیاد، کارآمد نیست و در این موارد، الگوریتم‌های بهتری مثل مرتب‌ساز سریع، مرتب‌ساز ادغامی و مرتب‌ساز پشته وجود دارد.

این الگوریتم به این صورت عمل می‌کند که تمام عناصر لیست را یکی یکی برمی‌دارد و آن را در موقعیت مناسب در بخش مرتب شده قرار می‌دهد. انتخاب عنصر مورد نظر، اختیاری است و می‌تواند توسط هر الگوریتم انتخابی، انتخاب شود. مرتب‌سازی درجی به صورت درجا عمل می‌کند. نتیجه عمل بعد از k مرحله، حاوی k عنصر انتخاب شده به صورت مرتب شده است.

بهترین حالت زمانی است که آرایه از قبل مرتب شده باشد. در این حالت زمان اجرای الگوریتم از (O(n است: در هر مرحله اولین عنصر باقیمانده از لیست اولیه فقط با آخرین عنصر لیست مرتب شده مقایسه می‌شود. این حالت بدترین حالت برای مرتب‌ساز سریع (غیرتصادفی و با پیاده‌سازی ضعیف) است که زمان (O(n^۲ صرف می‌کند. بدترین حالت این الگوریتم، زمانی است که آرایه به صورت معکوس مرتب شده باشد. در این حالت هر اجرای حلقه داخلی، مجبور است که تمام بخش مرتب شده را بررسی کرده و انتقال دهد. در این زمان اجرای الگوریتم، مثل حالت متوسط، دارای زمان اجرای (O(n^۲ است که باعث می‌شود استفاده از این الگوریتم برای مرتب‌سازی تعداد داده‌های زیاد، غیرعملی شود. گرچه حلقه داخلی مرتب‌ساز درجی، خیلی سریع است و این الگوریتم را به یکی از سریع‌ترین الگوریتم‌های مرتب‌سازی، برای تعداد داده‌های کم (معمولاً کمتر از ۱۰)، تبدیل می‌کند.