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

شبه کد مربوط به مرتب سازی درجی به صورت زیر است که در آن اعداد ورودی به صورت درجا مرتب می‌شوند یعنی اعداد در داخل آرایه دوباره چیده می‌شوند و ورودی الگوریتم آرایه‌ی A می‌باشد و پس از اجرای الگوریتم آرایه‌ی ورودی A شامل خروجی است :

نمونه‌ی روبه‌رو طریق عملکرد آن را روی {3, 7, 4, 9, 5, 2, 6, 1} نشان می‌دهد :

زمانی که رویه‌ی Insertion-Sort صرف می‌کند به اندازه ی ورودی بستگی دارد. مرتب سازی هزار عدد زمان بیش‌تری از مرتب سازی ده عدد مصرف می‌کند و هم‌چنین Insertion-Sort بسته به این که اعداد ورودی چقدر مرتب باشند برای دودنباله به طول‌های برابر زمان متفاوتی را مصرف می‌کند.

به ازای هر i>j اگر $a_i$ <$a_j$ این را یک نابه‌جایی تعریف می‌کنیم. زمان اجرای الگوریتم از مرتبه‌ی بیشینه‌ی تعداد نابه‌جایی های دنباله‌ی ورودی و اندازه‌ی ورودی می‌باشد و از آن جایی که تعداد نابه‌جایی‌ها از $O(n^2)$ می‌باشد پس الگوریتم در بدترین حالت $O(n^2)$ می‌باشد. اگر یک دنباله‌ی ورودی به ترتیب صعودی باشد الگوریتم از $O(n)$ زمان مصرف می‌کند چون هر حلقه یک واحد زمانی طول می‌کشد و اگر هم دنباله به ترتیب نزولی باشد تعداد نابه‌جایی‌ها برابر است با 1+2+3+…+n(n-1)/2=n که از مرتبه‌ی $O(n^2)$ می‌باشد و در این حالت الگوریتم از مرتبه‌ی $O(n^2)$ زمان می‌برد. حال که بهترین و بدترین حالت را بررسی کردیم بررسی حالت میانگین خالی از لطف نمی‌باشد.

حالت میانگین غالبا به بدی بدترین حالت است. فرض کنید n عدد تصادفی انتخاب کرده و عمل مرتب سازی را روی آن انجام می‌دهیم. به طور متوسط نیمی از عناصر در $A[1…j-1]$ کم‌تر از $A[j]$ هستند ونیمی بزرگ‌تر از آن می‌باشند بنابراین در حالت میانگین از مرتبه‌ی نصف تعداد نابه‌جایی‌ها زمان مصرف می‌کند که آن هم از مرتبه‌ی $O(n^2)$ می‌باشد.

Insertion_Sort.cpp

#include <iostream>
 
 
using namespace std;
 
const int maxn=1000+100;
 
int n,a[maxn];
 
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=2;i<=n;i++)
        for(int j=i-1;j>=1;j--){
            if(a[j]>a[j+1])
                swap(a[j+1],a[j]);
            else
                break;
        }
    for(int i=1;i<=n;i++)
        cout<<a[i]<<" ";
    cout<<endl;
 
 
    return 0;
}

• https://en.wikipedia.org/wiki/Insertion_sort