الگوریتم مرتب سازی درجی (Insertion Sort)

الگوریتم مرتب سازی درجی (Insertion Sort)

الگوریتم مرتب سازی درجی (Insertion Sort) یکی الگوریتم های  برای مرتب سازی یک آرایه نامرتب است. این الگوریتم برای مرتب سازی مجموعه های بزرگ کارایی خیلی کمتری در مقایسه با الگوریتم هایی مثل Merge Sort، Heap Sort و Quick Sort دارد. روش کار به این صورت است که عناصر آرایه را یکی یکی برداشته و در جای مناسب در بخش مرتب شده، قرار می دهد. در زیر می توانید تصویری از نحوه عملکرد الگوریتم Insertion Sort را مشاهه کنید.

مثال

فرض کنید یک آرایه با مقادیر زیر داریم:

12, 11, 13, 5, 6

در این مثال i از ۱ (یعنی عنصر دوم) تا ۴ (یعنی عنصر آخر) ادامه می یابد.

i = 1، چون ۱۲ از ۱۱ بزرگتر است، ۱۱ به قبل از ۱۲ انتقال می یابد.

11, 12, 13, 5, 6

i = 2، ۱۳ در جای خودش باقی می ماند. چون عناصر باقی مانده کوچکتر از آن هستند.

11, 12, 13, 5, 6

i = 3، مقدار ۵ به ابتدای آرایه انتقال می یابد و مقادیر ۱۱ و ۱۳ یک واحد به جلو انتقال می یابند.

5, 11, 12, 13, 6

i = 4، مقدار ۶ به موقعیت بعد از ۵ انتقال می یابد و مقادیر ۱۱ و ۱۳ یک واحد به جلو انتقال می یابند.

پیاده سازی این الگوریتم با استفاده از زبان C++:

// C++ program for insertion sort 
#include <bits/stdc++.h>
using namespace std;
/* Function to sort an array using insertion sort*/
void insertionSort(int arr[], int n) 
{ 
    int i, key, j; 
    for (i = 1; i < n; i++)
    { 
        key = arr[i]; 
        j = i - 1; 
        /* Move elements of arr[0..i-1], that are 
        greater than key, to one position ahead 
        of their current position */
        while (j >= 0 && arr[j] > key)
        { 
            arr[j + 1] = arr[j]; 
            j = j - 1; 
        } 
        arr[j + 1] = key; 
    } 
} 
// A utility function to print an array of size n 
void printArray(int arr[], int n) 
{ 
    int i; 
    for (i = 0; i < n; i++) 
        cout << arr[i] << " "; 
    cout << endl;
} 
/* Driver code */
int main() 
{ 
    int arr[] = { 12, 11, 13, 5, 6 }; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    insertionSort(arr, n); 
    printArray(arr, n); 
    return 0; 
}

امتحان کنید

خروجی:

5 6 11 12 13

نکات

• پیچیدگی زمانی برابر است با O(n*2).
• فضای موقت برابر است با O(1).
• این الگوریتم زمانی که آرایه به صورت برعکس مرتب شده باشد، بیشترین زمان را می گیرد و زمانی که به صورت مرتب شده باشد، کمترین زمان را می گیرد.
• این الگوریتم برای مجموعه هایی که تعداد عناصر کمی دارند و همچنین مجموعه هایی که تقریبا مرتب شده هستند، کارایی خوبی دارد.
  

نوشته الگوریتم مرتب سازی درجی (Insertion Sort) اولین بار در سورس سرا - آموزش برنامه نویسی. پدیدار شد.