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

پنجشنبه ۹ آبان ۱۳۹۸
بازدید ۵,۰۳۴ نفر
یعثوب سیفی زاده
(39 امتیاز از 8 رای)
Loading...

تصویر insertion-sort-algorithm_7313 الگوریتم مرتب سازی درجی (Insertion Sort)

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

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

تصویر insertion-sort-algorithm_7313_1 الگوریتم مرتب سازی درجی (Insertion Sort)

مثال

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

12, 11, 13, 5, 6

1	12, 11, 13, 5, 6

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

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

11, 12, 13, 5, 6

1	11, 12, 13, 5, 6

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

11, 12, 13, 5, 6

1	11, 12, 13, 5, 6

i = 3، مقدار 5 به ابتدای آرایه انتقال می یابد و مقادیر 11 و 13 یک واحد به جلو انتقال می یابند.

5, 11, 12, 13, 6

1	5, 11, 12, 13, 6

i = 4، مقدار 6 به موقعیت بعد از 5 انتقال می یابد و مقادیر 11 و 13 یک واحد به جلو انتقال می یابند.

پیاده سازی این الگوریتم با استفاده از زبان 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; 
}

// 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

1	5 6 11 12 13

تغییر به حالت نزولی

برای تغییر به حالت نزولی کافیست در تابع insertionSort شرط while (j >= 0 && arr[j] > key) را به while (j >= 0 && arr[j] < key) تغییر دهید.

نکات

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

الگوریتم ها - مرتب سازی ادغامی الگوریتم ها - مرتب سازی انتخابی