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

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

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

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

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

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

حالت میانگین غالبا به بدی بدترین حالت است. فرض کنید $n$ عدد تصادفی انتخاب کرده و عمل مرتب سازی را روی آن انجام می‌دهیم. به طور متوسط نیمی از عناصر در $A[1…j-1]$ کم‌تر از $A[j]$ و نیمی بزرگ‌تر از آن می‌باشند. بنابراین در حالت میانگین از مرتبه‌ی نصف بیشترین تعداد نابه‌جایی‌ها زمان مصرف می‌کند که آن هم از مرتبه‌ی $\mathcal{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