مرتب سازی درجی (Insertion Sort) — به زبان ساده

«مرتب سازی درجی» (Insertion Sort) یک الگوریتم مرتب‌سازی ساده است که روش عملکرد آن مشابه روشی است که افراد کارت‌های بازی را در دست خود مرتب می‌کنند. در این مطلب، به الگوریتم مرتب سازی درجی پرداخته شده و سپس، پیاده‌سازی آن در زبان‌های برنامه‌نویسی گوناگون، شامل «سی‌پلاس‌پلاس» (++C ،(C، «جاوا» (Java)، «پایتون» (Python)، «سی‌شارپ» (#C) و «پی‌اچ‌پی» (PHP) انجام شده است.

الگوریتم مرتب سازی درجی

//مرتب‌سازی آرایه []arr با سایز n

1. (insertionSort(arr, n
2. از  i = 1 تا n-1 حلقه بزن
   • عنصر [arr[i را انتخاب کن و آن را در توالی مرتب شده [arr[0…i-1 درج کن

فیلم آموزش مبانی برنامه نویسی – الگوریتم و فلوچارت با رویکرد حل مساله در فرادرس

کلیک کنید

مثال اول از مرتب سازی درجی

مثال دوم از مرتب سازی درجی

12, 11, 13, 5, 6

از i = 1 (دومین عنصر از آرایه) تا ۴ (آخرین عنصر از آرایه) حلقه بزن.

i = 1. به دلیل آنکه ۱۱ از ۱۲ کوچک‌تر است، ۱۲ را جا به جا کن و ۱۱ را پیش از ۱۲ درج کن.

i = 2. عدد ۱۳ در جای خود باقی می‌ماند، زیرا همه عناصر [A[0..I-1 کوچک‌تر از ۱۳ هستند.

11, 12, 13, 5, 6

i = 3. عدد ۵ به آغاز منتقل می‌شود و همه عناصر دیگر، از ۱۱ تا ۱۳ یک خانه از خانه کنونی خود رو  به جلو، جا به جا می‌شوند.

5, 11, 12, 13, 6

i = 4. عدد ۶ به خانه پس از ۵ منتقل می‌شود و عناصر از ۱۱ تا ۱۳ به اندازه یک خانه از خانه کنونی‌شان، به جلو می‌روند.

5, 6, 11, 12, 13

کد مرتب سازی درجی در ++C

فیلم آموزش ساختمان داده ها و پیاده سازی در سی پلاس پلاس 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;  
}  
  
// This is code is contributed by rathbhupendra

کد مرتب سازی درجی در C

فیلم آموزش الگوریتم های مرتب سازی در زبان برنامه نویسی پایتون با مثال (رایگان) در فرادرس

کلیک کنید

// C program for insertion sort 
#include <math.h> 
#include <stdio.h> 
  
/* 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++) 
        printf("%d ", arr[i]); 
    printf("\n"); 
} 
  
/* Driver program to test insertion sort */
int main() 
{ 
    int arr[] = { 12, 11, 13, 5, 6 }; 
    int n = sizeof(arr) / sizeof(arr[0]); 
  
    insertionSort(arr, n); 
    printArray(arr, n); 
  
    return 0; 
}

کد مرتب سازی درجی در جاوا

فیلم آموزش رایگان اصول و مبانی برنامه نویسی در فرادرس

کلیک کنید

// Java program for implementation of Insertion Sort 
class InsertionSort { 
    /*Function to sort array using insertion sort*/
    void sort(int arr[]) 
    { 
        int n = arr.length; 
        for (int i = 1; i < n; ++i) { 
            int key = arr[i]; 
            int 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 array of size n*/
    static void printArray(int arr[]) 
    { 
        int n = arr.length; 
        for (int i = 0; i < n; ++i) 
            System.out.print(arr[i] + " "); 
  
        System.out.println(); 
    } 
  
    // Driver method 
    public static void main(String args[]) 
    { 
        int arr[] = { 12, 11, 13, 5, 6 }; 
  
        InsertionSort ob = new InsertionSort(); 
        ob.sort(arr); 
  
        printArray(arr); 
    } 
} /* This code is contributed by Rajat Mishra. */

کد مرتب سازی درجی در پایتون

فیلم آموزش الگوریتم های مرتب سازی در زبان برنامه نویسی پایتون با مثال (رایگان) در فرادرس

کلیک کنید

# Python program for implementation of Insertion Sort 
  
# Function to do insertion sort 
def insertionSort(arr): 
  
    # Traverse through 1 to len(arr) 
    for i in range(1, len(arr)): 
  
        key = arr[i] 
  
        # Move elements of arr[0..i-1], that are 
        # greater than key, to one position ahead 
        # of their current position 
        j = i-1
        while j >= 0 and key < arr[j] : 
                arr[j + 1] = arr[j] 
                j -= 1
        arr[j + 1] = key 
  
  
# Driver code to test above 
arr = [12, 11, 13, 5, 6] 
insertionSort(arr) 
for i in range(len(arr)): 
    print ("% d" % arr[i]) 
  
# This code is contributed by Mohit Kumra

کد مرتب سازی درجی در #C

// C# program for implementation of Insertion Sort 
using System; 
  
class InsertionSort { 
  
    // Function to sort array 
    // using insertion sort 
    void sort(int[] arr) 
    { 
        int n = arr.Length; 
        for (int i = 1; i < n; ++i) { 
            int key = arr[i]; 
            int 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 
    // array of size n 
    static void printArray(int[] arr) 
    { 
        int n = arr.Length; 
        for (int i = 0; i < n; ++i) 
            Console.Write(arr[i] + " "); 
  
        Console.Write("\n"); 
    } 
  
    // Driver Code 
    public static void Main() 
    { 
        int[] arr = { 12, 11, 13, 5, 6 }; 
        InsertionSort ob = new InsertionSort(); 
        ob.sort(arr); 
        printArray(arr); 
    } 
} 
  
// This code is contributed by ChitraNayal.

کد مرتب سازی درجی در PHP

فیلم آموزش برنامه نویسی پی اچ پی PHP در فرادرس

کلیک کنید

<?php  
// PHP program for insertion sort 
  
// Function to sort an array 
// using insertion sort 
function insertionSort(&$arr, $n) 
{ 
    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 
function printArray(&$arr, $n) 
{ 
    for ($i = 0; $i < $n; $i++) 
        echo $arr[$i]." "; 
    echo "\n"; 
} 
  
// Driver Code 
$arr = array(12, 11, 13, 5, 6); 
$n = sizeof($arr); 
insertionSort($arr, $n); 
printArray($arr, $n); 
  
// This code is contributed by ChitraNayal. 
?>

خروجی

خروجی قطعه کدهای بالا، برای آرایه [6, 5, 13, 11, 12] به صورت زیر است.

5 6 11 12 13

پیچیدگی زمانی: (O(n*2

فضای کمکی: (O(1

موارد مرزی (Boundary Cases): مرتب سازی درجی، در صورتی که عناصر دارای ترتیب برعکس باشند، بیشترین زمان اجرا را می‌برد. همچنین، در صورتی که عناصر مرتب شده باشند، کمترین زمان اجرا (از درجه n) را خواهد داشت.

مرتب‌سازی درجا: بله

پایدار: بله

آنلاین: بله

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

مرتب سازی درجی دودویی

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

فیلم آموزش درخت جستجوی دودویی (AVL) در ساختمان داده ها (رایگان) در فرادرس

کلیک کنید

در درج نرمال، مرتب‌سازی در بدترین حالت (O(i به طور می‌انجامد (در iاُمین تکرار). این مقدار را می‌توان با استفاده از جستجوی دودویی به (O(logi کاهش داد. به طور کلی،‌ الگوریتم همچنان دارای زمان اجرای (O(n² است، زیرا مجموعه‌ای از جا به جایی‌ها برای هر درج مورد نیاز است.

پیاده‌سازی مرتب سازی درجی برای لیست‌های پیوندی

در ادامه، پیاده‌سازی ساده‌ای از مرتب سازی درجی برای لیست‌های پیوندی ارائه شده است.

1. یک لیست خالی «مرتب شده» (Sorted) (یا «نتیجه» (Result)) بساز.
2. لیست داده شده را معکوس کن و اقدامات زیر را برای هر گره انجام بده:
   • گره کنونی را به صورت مرتب شده، در لیست «مرتب شده» (Sorted) یا «نتیجه» (Result) قرار بده.
3. سر لیست پیوندی داده شده را به سر لیست مرتب شده (یا نتیجه) تغییر بده.

کد مرتب سازی درجی در لیست‌های پیوندی در ++C

/* C program for insertion sort on a linked list */
#include<stdio.h> 
#include<stdlib.h> 
  
/* Link list node */
struct Node 
{ 
    int data; 
    struct Node* next; 
}; 
  
// Function to insert a given node in a sorted linked list 
void sortedInsert(struct Node**, struct Node*); 
  
// function to sort a singly linked list using insertion sort 
void insertionSort(struct Node **head_ref) 
{ 
    // Initialize sorted linked list 
    struct Node *sorted = NULL; 
  
    // Traverse the given linked list and insert every 
    // node to sorted 
    struct Node *current = *head_ref; 
    while (current != NULL) 
    { 
        // Store next for next iteration 
        struct Node *next = current->next; 
  
        // insert current in sorted linked list 
        sortedInsert(&sorted, current); 
  
        // Update current 
        current = next; 
    } 
  
    // Update head_ref to point to sorted linked list 
    *head_ref = sorted; 
} 
  
/* function to insert a new_node in a list. Note that this 
  function expects a pointer to head_ref as this can modify the 
  head of the input linked list (similar to push())*/
void sortedInsert(struct Node** head_ref, struct Node* new_node) 
{ 
    struct Node* current; 
    /* Special case for the head end */
    if (*head_ref == NULL || (*head_ref)->data >= new_node->data) 
    { 
        new_node->next = *head_ref; 
        *head_ref = new_node; 
    } 
    else
    { 
        /* Locate the node before the point of insertion */
        current = *head_ref; 
        while (current->next!=NULL && 
               current->next->data < new_node->data) 
        { 
            current = current->next; 
        } 
        new_node->next = current->next; 
        current->next = new_node; 
    } 
} 
  
/* BELOW FUNCTIONS ARE JUST UTILITY TO TEST sortedInsert */
  
/* Function to print linked list */
void printList(struct Node *head) 
{ 
    struct Node *temp = head; 
    while(temp != NULL) 
    { 
        printf("%d  ", temp->data); 
        temp = temp->next; 
    } 
} 
  
/* A utility function to insert a node at the beginning of linked list */
void push(struct Node** head_ref, int new_data) 
{ 
    /* allocate node */
    struct Node* new_node = new Node; 
  
    /* put in the data  */
    new_node->data  = new_data; 
  
    /* link the old list off the new node */
    new_node->next = (*head_ref); 
  
    /* move the head to point to the new node */
    (*head_ref)    = new_node; 
} 
  
  
// Driver program to test above functions 
int main() 
{ 
    struct Node *a = NULL; 
    push(&a, 5); 
    push(&a, 20); 
    push(&a, 4); 
    push(&a, 3); 
    push(&a, 30); 
  
    printf("Linked List before sorting \n"); 
    printList(a); 
  
    insertionSort(&a); 
  
    printf("\nLinked List after sorting \n"); 
    printList(a); 
  
    return 0; 
} 

کد مرتب سازی درجی در لیست‌های پیوندی در جاوا

// Java program to sort link list 
// using insertion sort 
  
public class LinkedlistIS  
{ 
    node head; 
    node sorted; 
  
    class node  
    { 
        int val; 
        node next; 
  
        public node(int val)  
        { 
            this.val = val; 
        } 
    } 
  
    void push(int val)  
    { 
        /* allocate node */
        node newnode = new node(val); 
        /* link the old list off the new node */
        newnode.next = head; 
        /* move the head to point to the new node */
        head = newnode; 
    } 
  
    // function to sort a singly linked list using insertion sort 
    void insertionSort(node headref)  
    { 
        // Initialize sorted linked list 
        sorted = null; 
        node current = headref; 
        // Traverse the given linked list and insert every 
        // node to sorted 
        while (current != null)  
        { 
            // Store next for next iteration 
            node next = current.next; 
            // insert current in sorted linked list 
            sortedInsert(current); 
            // Update current 
            current = next; 
        } 
        // Update head_ref to point to sorted linked list 
        head = sorted; 
    } 
  
    /* 
     * function to insert a new_node in a list. Note that  
     * this function expects a pointer to head_ref as this 
     * can modify the head of the input linked list  
     * (similar to push()) 
     */
    void sortedInsert(node newnode)  
    { 
        /* Special case for the head end */
        if (sorted == null || sorted.val >= newnode.val)  
        { 
            newnode.next = sorted; 
            sorted = newnode; 
        } 
        else 
        { 
            node current = sorted; 
            /* Locate the node before the point of insertion */
            while (current.next != null && current.next.val < newnode.val)  
            { 
                current = current.next; 
            } 
            newnode.next = current.next; 
            current.next = newnode; 
        } 
    } 
  
    /* Function to print linked list */
    void printlist(node head)  
    { 
        while (head != null)  
        { 
            System.out.print(head.val + " "); 
            head = head.next; 
        } 
    } 
      
    // Driver program to test above functions 
    public static void main(String[] args)  
    { 
        LinkedlistIS list = new LinkedlistIS(); 
        list.push(5); 
        list.push(20); 
        list.push(4); 
        list.push(3); 
        list.push(30); 
        System.out.println("Linked List before Sorting.."); 
        list.printlist(list.head); 
        list.insertionSort(list.head); 
        System.out.println("\nLinkedList After sorting"); 
        list.printlist(list.head); 
    } 
} 
  
// This code is contributed by Rishabh Mahrsee

کد مرتب سازی درجی در لیست‌های پیوندی در #C

// C# program to sort link list 
// using insertion sort 
using System; 
  
public class LinkedlistIS  
{ 
    public node head; 
    public node sorted; 
  
    public class node  
    { 
        public int val; 
        public node next; 
  
        public node(int val)  
        { 
            this.val = val; 
        } 
    } 
  
    void push(int val)  
    { 
        /* allocate node */
        node newnode = new node(val); 
          
        /* link the old list off the new node */
        newnode.next = head; 
          
        /* move the head to point to the new node */
        head = newnode; 
    } 
  
    // function to sort a singly  
    // linked list using insertion sort 
    void insertionSort(node headref)  
    { 
        // Initialize sorted linked list 
        sorted = null; 
        node current = headref; 
          
        // Traverse the given  
        // linked list and insert every 
        // node to sorted 
        while (current != null)  
        { 
            // Store next for next iteration 
            node next = current.next; 
              
            // insert current in sorted linked list 
            sortedInsert(current); 
              
            // Update current 
            current = next; 
        } 
          
        // Update head_ref to point to sorted linked list 
        head = sorted; 
    } 
  
    /* 
    * function to insert a new_node in a list. Note that  
    * this function expects a pointer to head_ref as this 
    * can modify the head of the input linked list  
    * (similar to push()) 
    */
    void sortedInsert(node newnode)  
    { 
        /* Special case for the head end */
        if (sorted == null || sorted.val >= newnode.val)  
        { 
            newnode.next = sorted; 
            sorted = newnode; 
        } 
        else
        { 
            node current = sorted; 
              
            /* Locate the node before the point of insertion */
            while (current.next != null &&  
                    current.next.val < newnode.val)  
            { 
                current = current.next; 
            } 
            newnode.next = current.next; 
            current.next = newnode; 
        } 
    } 
  
    /* Function to print linked list */
    void printlist(node head)  
    { 
        while (head != null)  
        { 
            Console.Write(head.val + " "); 
            head = head.next; 
        } 
    } 
      
    // Driver code 
    public static void Main(String[] args)  
    { 
        LinkedlistIS list = new LinkedlistIS(); 
        list.push(5); 
        list.push(20); 
        list.push(4); 
        list.push(3); 
        list.push(30); 
        Console.WriteLine("Linked List before Sorting.."); 
        list.printlist(list.head); 
        list.insertionSort(list.head); 
        Console.WriteLine("\nLinkedList After sorting"); 
        list.printlist(list.head); 
    } 
} 
  
// This code contributed by Rajput-Ji

فیلم آموزش برنامه نویسی پایتون + مثال های عملی در Python در فرادرس

کلیک کنید

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

• مجموعه آموزش‌‌های برنامه‌‌‌نویسی
• آموزش برنامه‌نویسی C++‎
• مجموعه آموزش‌های ریاضیات
• معرفی تکنیک‌های مرتب‌سازی (Sorting Techniques) — ساختار داده و الگوریتم ها
• ۵ الگوریتم مرتب‌سازی در پایتون — راهنمای کاربردی
• پیچیدگی زمانی الگوریتم‌های مرتب‌سازی با نماد O بزرگ — به زبان ساده

^^