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

در دنیای علم کامپیوتر، روش‌های مختلفی برای مرتب سازی وجود دارد. مرتب سازی درجی (Insertion Sort) یک الگوریتم ساده برای مرتب کردن داده های مختلف است. اگر به موضوعاتی از قبیل مرتب سازی و الگوریتم‌ها علاقه‌مند هستید می‌توانید به صفحه ساختمان دادهآموزش ساختمان داده و الگوریتمهر ساختمان داده یک نوع فرمت ذخیره‌سازی و مدیریت داده‌ها در کامپیوتر است، که امکان دسترسی و اصلاح کارآمد آن داده‌ها را برای یکسری از الگوریتم‌ها و کاربردها فراهم می‌کند، در این صفحه به بررسی و آموزش ساختمان داده و الگوریتم پرداخته شده است و طراحی الگوریتمآموزش طراحی الگوریتم به زبان سادهدرس طراحی الگوریتم‌ یکی از مهم‌ترین و بنیادیترین دروس‌ رشته کامپیوتر است. هدف از این درس، معرفی روش‌های مختلف طراحی الگوریتم‌ها برای حل مسائل گوناگون است، در این صفحه به معرفی و آموزش طراحی الگوریتم پرداخته شده است. الگوریتم مراجعه فرمائید.

تعریف ساده مرتب سازی درجی

تصور کنید در حال بازی با ورق هستید. دسته کارت‌هایی که در دست شماست، همگی مرتب هستند. بازیکن دیگر دقیقا یک کارت جدید به شما می‌دهد و شما باید آن را در جای درست قرار دهید تا کارت‌هایی که در دست دارید، دوباره مرتب شوند. شما باید کارت جدید را با هر کارتی که در دست دارید مقایسه کنید تا آن کارت را در جای مناسب، قرار دهید. سپس بازیکن یک کارت دیگر را به شما می‌دهد که باز باید همین رویه قبل را پیش بگیرید تا دسته کارت‌های شما مرتب شوند.

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

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

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

در این مرتب ‌سازی در هر مرحله (گذر) فقط یک کلید در داخل آرایه قابل بررسی است، بدین صورت که کلید k_i باید در بین 1- i کلید مرتب‌شده (k_i, … , k_i-1) به گونه‌ای قرار گیرد تا لیست حاصل به طول i مرتب بماند. در نهایت با 1- n گذر آرایه مرتب خواهد شد.

گذر اول: [2]a قبل یا بعد از [1]a به گونه‌ای قرار می‌گیرد، که لیست [2...1]a مرتب باشد.

گذر دوم: [2]a در لیست [2...1]a مرتب شده به گونه‌ای قرار می‌گیرد، که لیست [3...1]a مرتب باشد.

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

for j ← 2 to n do
	key ← A[j]
Insert A[j] Into the sorted sequence A[1 .. j – 1]
	1 ← j – 1
while l > 0 and A[l] > key
	do A[1 + 1] ← A[l]
		1 = l – l
A[1 + 1] ← key

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

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

در الگوریتم بالا، برای اینکه حلقه while در مواردی بی نهایت بار تکرار نشود، شرط (j>0) قرار می گیرد که مقایسه عناصر تا A[1] انجام شود.

for   i: = 2   to   n   do
  begin
  j: = i;
  while   A[j] < A[j – 1]   and   j > 1   do
      begin
      T: = A[j – 1];
      A[j – 1]: = A[j];
      A[j]: = T;
      j: = j – 1;
      end;
  end;

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

در صورتی که آرایه ورودی به صورت $36$، $90$، $12$، $74$، $\overrightarrow{\mathrm{50}}$  باشد، مراحل مرتب‌سازی به شرح زیر است: 

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

مرتب سازی درجی مانند روش‌های مرتب سازی دیگر دارای ویژگی‌هایی است که در این بخش بیان خواهد شد.

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

اکنون به چند مزیت عمده استفاده از مرتب‌ سازی درجی و چند سناریو که ثابت شده است مرتب‌سازی درج بهترین عملکرد را ارائه می‌کند، نگاه می‌کنید.

• الگوریتم درجی متعادل است در صورتیکه شرط درون while به صورت > ( بزرگتر و نه بزرگتر مساوی) باشد. الگوریتم متعادل یا Stable یعنی اگر ترتیب عناصر ورودی پس از مرتب کردن آن به وسیله ی الگوریتم های مرتب سازی حفظ شود، الگوریتم متعادل است.
• این الگوریتم مانند سایر الگوریتم‌های مرتب سازی، برای مجموعه داده های کوچک کارآمد است.
• این روش برای آرایه با تعداد عناصر کم‌تر یا مساوی 20 سریع‌ترین روش است.
• فقط به مقدار ثابت O(1) فضای حافظه اضافی نیاز دارد.
• با مجموعه داده‌هایی که به طور قابل توجهی مرتب شده اند به خوبی کار می کند.
• مرتب سازی درجی ، درجا (Inplace) است و نیازی به حافظه کمکی برای مرتب سازی ندارد.
• امکان مرتب سازی لیست در حال دریافت.

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

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

• مرتب سازی درجی در برابر مجموعه داده‌های گسترده تر ناکارآمد است
• مرتب‌سازی درجی بدترین پیچیدگی زمانی O(n²) را نشان می‌دهد (میانگین زمان الگوریتم مرتب سازی درجی در بدترین حالت و همینطور در حالت متوسط از مرتبه O(n²) است).
• نسبت به سایر الگوریتم‌های مرتب سازی پیشرفته تر عملکرد خوبی ندارد.

پیچیدگی زمانی مرتب سازی درجی

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

ما هزینه هر عملیات i را به صورت C_i در نظر می‌گیریم که i ∈ {1,2,3,4,5,6,8} است و تعداد دفعاتی که این عملیات ها اجرا می‌شوند را محاسبه می‌کنیم. بنابراین مجموع هزینه برای یک چنین عملیاتی حاصل ضرب هزینه یک عملیات و تعداد دفعات اجرای آن خواهد بود.

می توانیم آنها را به صورت زیر فهرست کنیم:

سپس زمان اجرای مرتب سازی درجی به صورت به دست می آید.

T(n) = C${}_{1}$* n + ( C${}_{2}$+ C${}_{3}$) * ( n - 1 ) + C${}_{4}$* $\Sigma$${}^{n\ -\ 1}$${}_{j\ =\ 1}$( t${}_{j}$) + ( C${}_{5}$+ C${}_{6}$) * $\Sigma$${}^{n\ -\ 1}$${}_{j\ =\ 1}$( t${}_{j}$) + C${}_{8}$* ( n - 1 )

بهترین حالت مرتب سازی درجی

زمانیکه آرایه ورودی مرتب شده باشد، الگوریتم درجی در بهترین حالت پیچیدگی زمانی خود عمل می کند. (t_j = 1 )

;T( n ) = C${}_{1}$* n + ( C${}_{2}$+ C${}_{3}$) * ( n - 1 ) + C${}_{4}$* ( n - 1 ) + ( C${}_{5}$+ C${}_{6}$) * ( n - 2 ) + C${}_{8}$* ( n - 1 )

T(n) = C * ( n ) or O(n)

بهترین حالت: ورودی مرتب          مقایسات: O(n) = n-1          جابه‌جایی: 0 = (1)O

بدترین حالت مرتب سازی درجی

زمانیکه آرایه ورودی به صورت معکوس مرتب شده باشد، الگوریتم درجی در بدترین حالت پیچیدگی زمانی خود عمل می کند. (t_j = j )

T( n ) = C${}_{1}$* n + ( C${}_{2}$+ C${}_{3}$) * ( n - 1 ) + C${}_{4}$* ( n - 1 ) ( n ) / 2 + ( C${}_{5}$+ C${}_{6}$) * ( ( n - 1 ) (n ) / 2 - 1) + C${}_{8}$* ( n - 1 )

T(n) = C * ( n${}^{2}$) or O( n${}^{2}$)

بدترین حالت: ورودی مرتب معکوسمقایسات:\[\mathrm{O(}{\mathrm{n}}^{\mathrm{2}}\mathrm{)\ =\ }\frac{\mathrm{n(n}-\ \mathrm{1}\mathrm{)}}{\mathrm{2}}\]          جابه‌جایی: \[\mathrm{O(}{\mathrm{n}}^{\mathrm{2}}\mathrm{)\ =\ }\frac{\mathrm{n(n}-\ \mathrm{1}\mathrm{)}}{\mathrm{2}}\]

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

در حالت متوسط :  t_j = (j-1)/2 فرض می کنیم .در اینصورت :

T( n ) = C${}_{1}$* n + ( C${}_{2}$+ C${}_{3}$) * ( n - 1 ) + C${}_{4}$/2 * ( n - 1 ) ( n ) / 2 + ( C${}_{5}$+ C${}_{6}$)/2 * ( ( n - 1 ) (n ) / 2 - 1) + C${}_{8}$* ( n - 1 )

T(n) = C * ( n${}^{2}$) or O( n${}^{2}$)

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

در این بخش الگوریتم مرتب سازی درجی را در زبان‌های برنامه نویسی مختلف بیان می کنیم.

// 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
    // Driver code
int main()
{
  int arr[] = { 12, 11, 13, 5, 6 };
  int N = sizeof(arr) / sizeof(arr[0]);
// 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;
}
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
    // Driver code
int main()
{
  int arr[] = { 12, 11, 13, 5, 6 };
  int N = sizeof(arr) / sizeof(arr[0]);
// 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;
}
insertionSort(arr, N);
  printArray(arr, N);
  
  return 0;
}

		
// Java program for implementation of Insertion Sort
public 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);
  }
}

// Java program for implementation of Insertion Sort
public 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);
  }
}

<?php
// PHP program for insertion sort
  
// Function to sort an array
// using insertion sort
$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;
function insertionSort(&$arr, $n)
{
  for ($i = 1; $i < $n; $i++)
  {
    $key = $arr[$i];
  }
}
  
// 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);
?>

<?php
// PHP program for insertion sort
  
// Function to sort an array
// using insertion sort
$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;
function insertionSort(&$arr, $n)
{
  for ($i = 1; $i < $n; $i++)
  {
    $key = $arr[$i];
  }
}
  
// 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);
?>

# 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])

# 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])

		
// C# program for implementation of Insertion Sort
using System;
  
class InsertionSort {
  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
// Function to sort array
// using insertion sort
void sort(int[] arr)
{
  // 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);
  }
}

// C# program for implementation of Insertion Sort
using System;
  
class InsertionSort {
  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
// Function to sort array
// using insertion sort
void sort(int[] arr)
{
  // 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);
  }
}  

	
<script>
// Javascript program for insertion sort 
    
// Function to sort an array using insertion sort
function insertionSort(arr, n) 
{ 
  let i, key, j; 
  for (i = 1; i < n; i++)
  { 
    key = arr[i]; 
    j = i - 1; 
    
    /* Move elements of arr[0..i-1], that are 
{ 
  let i; 
  for (i = 0; i < n; i++) 
    document.write(arr[i] + " "); 
  document.write("
");
} 
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) 
{
  // Driver code
  let arr = [12, 11, 13, 5, 6 ]; 
  let n = arr.length; 
    
  insertionSort(arr, n); 
  printArray(arr, n); 
}
    
</script>

<script>
// Javascript program for insertion sort 
    
// Function to sort an array using insertion sort
function insertionSort(arr, n) 
{ 
  let i, key, j; 
  for (i = 1; i < n; i++)
  { 
    key = arr[i]; 
    j = i - 1; 
    
    /* Move elements of arr[0..i-1], that are 
{ 
  let i; 
  for (i = 0; i < n; i++) 
    document.write(arr[i] + " "); 
  document.write("
");
} 
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) 
{
  // Driver code
  let arr = [12, 11, 13, 5, 6 ]; 
  let n = arr.length; 
    
  insertionSort(arr, n); 
  printArray(arr, n); 
}
    
</script>
 

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

در این بخش تفاوت روش مرتب سازی درجی  را با دیگر روش‌های مرتب سازی بررسی می‌کنیم.

تفاوت بین مرتب‌سازی درجی و مرتب‌سازی انتخابی

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

تفاوت بین مرتب‌سازی درجی و مرتب‌سازی حبابی

مرتب‌سازی حبابی یک الگوریتم مرتب‌سازی ساده است که به طور مکرر فهرستی را مرور می‌کند، جفت‌های مجاور را با هم مقایسه می‌کند و اگر ترتیب اشتباهی داشته باشند، آنها را تعویض می‌کند. می‌توانید برای آشنایی بیشتر با الگوریتم مرتب سازی حبابی به صفحه مرتب سازی حبابیآموزش مرتب سازی حبابی (Bubble Sort) بصورت 0 تا 100این صفحه مرتب سازی حبابی (Bubble Sort) را بصورت 0 تا 100 آموزش داده و کدهای مرتب سازی حبابی در C++، پایتون و جاوا آورده شده است شده مراجعه فرمائید. از طرف دیگر، مرتب سازی درجی یک الگوریتم مرتب سازی ساده است که با انتقال یک عنصر در یک زمان، فهرست مرتب شده نهایی را می سازد. بنابراین، این تفاوت اصلی بین مرتب‌سازی حبابی و مرتب‌سازی درجی است.

1. عملکرد: در حالی که مرتب سازی حبابی عناصر همسایه را بررسی می‌کند و آنها را بر این اساس جابه‌جا می‌کند، مرتب سازی درجی یک عنصر را در هر زمان به آرایه مرتب‌شده منتقل می‌کند.
2. تعداد swapها :همچنین، تعداد مبادله ها تفاوت مهمی بین مرتب سازی حبابی و مرتب سازی درجی است. مرتب سازی درجی تعداد تعویض کمتری نسبت به مرتب سازی حبابی دارد.
3. سرعت : علاوه بر این، مرتب سازی درجی دو برابر سریع‌تر از مرتب سازی حبابی است.
4. پیچیدگی :تفاوت دیگر بین مرتب‌سازی حبابی و مرتب سازی درجی این است که مرتب‌سازی درجی پیچیده‌تر از مرتب سازی حبابی است.

تفاوت بین مرتب‌سازی درجی و مرتب‌سازی ادغامی

1. پیچیدگی زمانی: در مرتب سازی ادغامی بدترین حالت O(n log n) است. میانگین مورد O(n log n) است. بهترین حالت O(n log n) است در حالی که در مرتب سازی درجی بدترین حالت O(n²)است. میانگین مورد O(n²) است. بهترین حالت O(n) است.
2. پیچیدگی مکانی: مرتب‌سازی ادغامی، بازگشتی بودن پیچیدگی مکانی O(n) را می‌گیرد، بنابراین نمی‌توان آن را برای جا هایی که حافظه نداریم، استفاده کرد. با این حال، مرتب‌سازی درجی فقط پیچیدگی فضای O(1) را اشغال می‌کند. کل آرایه را با استفاده از یک متغیر اضافی مرتب می کند.
3. مجموعه داده ها: مرتب سازی ادغامی قطعا برای مجموعه داده‌های بزرگ ترجیح داده می شود. این به این دلیل است که مقایسه همه عناصر موجود در آرایه اتفاق می‌افتد، بنابراین برای مجموعه داده‌های کوچک چندان مفید نیست. با این حال، مرتب‌سازی درجی گزینه‌ای برای مجموعه داده‌های کمتر است. زمانی که داده ها از قبل مرتب شده باشند یا تقریبا مرتب شده باشند، سریع می شود زیرا به طور پیش فرض، مقادیر مرتب شده را رد می‌کند.
4. کارایی: با توجه به میانگین پیچیدگی زمانی هر دو الگوریتم، به جرات می‌توان گفت مرتب‌سازی ادغامی از نظر زمان و مرتب‌سازی درجی از نظر مکان کارآمد هستند.
5. روش مرتب سازی: مرتب‌سازی ادغامی یک روش مرتب‌سازی خارجی است که در آن داده‌هایی که قرار است مرتب شوند را نمی‌توان در حافظه جای داد و برای مرتب‌سازی به حافظه کمکی نیاز دارد، در حالی که مرتب‌سازی درجی بر اساس این ایده است که یک عنصر از عناصر ورودی در آن مصرف می‌شود و در هر تکرار در موقعیت صحیح خود (موقعیتی که در یک آرایه مرتب شده است) قرار می‌گیرد.

در صورتی که به بررسی الگوریتم مرتب سازی ادغامی علاقه‌مند باشید می‌توانید در صفحه مرتب سازی ادغامیآموزش مرتب سازی ادغامی بصورت 0 تا 100این صفحه مرتب سازی ادغامی را بصورت 0 تا 100 آموزش داده و مثال مرتب سازی ادغامی آورده شده است، همچنین بهترین، متوسط و بدترین حالت مرتب سازی ادغامی بررسی شده اطلاعات بیشتری در مورد این الگوریتم مرتب سازی بدست آورید.

نسخه های مختلف از این الگوریتم

برای بهبود مرتب سازی درجی ، تغییراتی را در این الگوریتم به وجود آوردند. در این بخش نسخه‌های مختلف این الگوریتم ، ذکر شده است.

مرتب سازی شل (Shell Sort)

الگوریتم مرتب سازی شل (Shell Sort) نسخه تغییر یافته الگوریتم مرتب سازی درجی (Insertion Sort) است. در مرتب سازی درجی ما عناصر را فقط یک خانه به جلو حرکت می دهیم. همین موضوع باعث می شود تا برای انتقال یک عنصر به موقعیت خیلی جلوتر(دورتر)، تعداد حرکات افزایش یابد. در الگوریتم مرتب سازی شل امکان مبادله عناصر دور هم فراهم شده است.

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

مثالی از الگوریتم شل (Shell Sort)

در ابتدا تعداد عناصر آرایه برابر با 8 می باشد و ما باید از لیست مقابل لیست های را در بیاوریم که فاصله بین اعداد  لیست “4=8/2” باشد. سپس دو عدد درون لیست را مقایسه کرد و در صورت لزوم جابه جا می‌کنیم.

{35, 14}, {33, 19}, {42, 27} {10, 44}  

آرایه به این صورت در می آید:

سپس لیست‌هایی را در بیاوریم که فاصله اعداد برابر با “2=8/4” می باشد

نتیجه :

در حلقه سوم، عناصر در بازه 1 قرار دارند (1=n/8)، که در آن n = 8. در نهایت، ما از فاصله مقدار 1 برای مرتب کردن بقیه عناصر آرایه استفاده می کنیم. در این مرحله، مرتب‌سازی شل از مرتب‌سازی درجی برای این کار استفاده می کند.

مرتب سازی درجی دودویی (Binary-Insertion Sort) 

مرتب سازی درجی دودویی یک الگوریتم مرتب سازی مشابه مرتب سازی درجی است، اما به جای استفاده از جستجوی خطی برای یافتن موقعیتی که عنصر باید در آن درج شود، از جستجوی باینری استفاده می‌کنیم. بنابراین، تعداد مقایسه‌ها را برای درج یک عنصر از O(N) به O(log N) کاهش می‌دهیم.

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

در مرتب سازی درجی دودویی، آرایه را به دو زیر آرایه تقسیم می‌کنیم (مرتب شده و مرتب نشده). اولین عنصر آرایه در زیرآرایه مرتب شده و بقیه عناصر در زیرآرایه مرتب نشده قرار دارند. سپس از عنصر دوم به عنصر آخر تکرار می‌کنیم. برای تکرار i، عنصر فعلی را "کلید" خود می‌کنیم. این کلید عنصری است که باید به زیرآرایه مرتب شده موجود اضافه کنیم.

برای انجام این کار، ابتدا از جستجوی باینری در زیرآرایه مرتب شده استفاده می‌کنیم تا موقعیت عنصری را پیدا کنیم که فقط بزرگتر از کلید ما است. این موقعیت را "pos" می‌نامیم. سپس همه عناصر را از موقعیت pos به i-1 تغییر می‌دهیم و سپس Array[pos] =key  را می‌سازیم. می‌توان توجه داشت که برای هر تکرار i، قسمت چپ آرایه تا (i-1) همیشه مرتب می‌شود.

مثالی از الگوریتم درجی دودویی

1. ما فرض می‌کنیم که عنصر اول قبلا مرتب شده است.
2. عنصر دوم را می‌گیریم و در یک متغیر (کلید) ذخیره می‌کنیم.
3. اکنون، از جستجوی دودویی برای یافتن عنصر سمت چپ عنصر فعلی استفاده می‌کنیم که فقط بزرگتر از آن است.
4. در این حالت، ما فقط یک عنصر داریم، 8، و بزرگتر از 6 است. بنابراین، 8 را  به سمت راست تغییر می‌دهیم و 6 را در موقعیت آن قرار می دهیم .آرایه اکنون به شکل زیر است:

5. حالا عنصر سوم را می‌گیریم، 1 (توجه داشته باشید که تمام عناصر قبل از عنصر فعلی مرتب شده‌اند.)
6. ما 1 را در کلید ذخیره می‌کنیم و با استفاده از جستجوی باینری، عنصر بزرگتر از 1 در قسمت مرتب شده پیدا می‌کنیم.
7. در اینجا، عنصر مورد نیاز 6 است. بنابراین، 6 و 8 را به سمت راست تغییر می دهیم و قبل از جابجایی، 1 را در موقعیت 6 قرار می دهیم. آرایه اکنون به شکل زیر است:

8. اکنون عنصر 4، "5" را می گیریم و آن را در کلید ذخیره می کنیم.
9. با استفاده از جستجوی دودویی، عنصری که فقط بزرگتر از 5 هستش را در قسمت مرتب شده پیدا می کنیم. در این حالت عنصر مورد نیاز 6 است.
10. مجدداً 6 و 8 را یک اندیس به سمت راست می بریم و 5 را در موقعیت 6 قبل از جابجایی قرار می دهیم. آرایه اکنون به شکل زیر است:

11. اکنون آخرین عنصر را که 3 است می گیریم و عنصر را در قسمت مرتب شده بزرگتر از آن می یابیم.
12. عنصر مورد نیاز 5 است. ما 5، 6، و 8 را یک شاخص به سمت راست تغییر می دهیم و قبل از جابجایی، 3 را در موقعیت 5 قرار می دهیم. آرایه به دست آمده به صورت زیر است:

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

به شما یک لیست پیوندی منفرد داده می شود که حاوی تعداد محدودی گره است و باید آن را با استفاده از مرتب سازی درجی مرتب کنید. با توجه به اینکه اشاره گر به سر گره لیست پیوند شده، پس از مرتب سازی لیست را باید به سر جدید برگردانید.

لیست داده شده را به سه گروه تقسیم کنید:

• یک زیر مجموعه مرتب شده ثابت (فهرست پیوندی که با عناصر "مرتب شده" شروع می‌شود)
• آیتم فعلی (گره ای که با "key" نشان داده شده است)
• زیرمجموعه‌ای حاوی موارد باقی مانده (فهرست پیوندی که از گره بعدی شروع می‌شود)

زیرمجموعه‌های حاوی موارد باقیمانده در تکرارهای بعدی پردازش خواهند شد.

به یاد داشته باشید که در ابتدا، "key" به اولین مورد از لیست داده شده اشاره می‌کند. هنگام مرتب سازی لیست پیوندی با مرتب سازی درجی، در هر مرحله، باید مراحل زیر را دنبال کنیم:

• گره‌ای را که «key» را دنبال می‌کند در یک متغیر ذخیره کنید و گره‌ای را که با «key» مشخص شده است به فهرست پیوندی که از «مرتب‌سازی‌شده» شروع می‌شود، منتقل کنید. از نظر فنی، یک گره را از مجموعه مرتب نشده حذف می‌کنیم و آن را به مجموعه مرتب شده اضافه می‌کنیم.
• مکان صحیح مورد حذف شده را در لیست پیوندی که با «مرتب شده» شروع می‌شود، پیدا کنید. ما می توانیم این کار را به این روش انجام دهیم: از ابتدای لیست شروع کنید، ادامه دهید تا موقعیت مناسب را پیدا کنیم، پس از اتمام کار، آن مورد حذف شده را در آنجا قرار می‌دهیم و به مرحله بعدی می‌رویم.
• "key" به گره ذخیره شده اشاره می‌کند و تا زمانی که "key"، تهی (null) نباشد مراحل بالا را تکرار می‌شود.

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

موارد زیر را به عنوان ورودی در نظر بگیریم:

مرحله 1: با اولین مورد، 5 شروع می‌کنیم:

مرحله 2: مجموعه مرتب شده اکنون دارای 5 است، و ما مورد بعدی، 4 را از لیست فعلی حذف می‌کنیم:

مرحله 3: چون 4<5 است، 4 قبل از 5 در مجموعه مرتب شده درج می شود.

مرحله 4:  2<4، بنابراین آن را قبل از 4 در مجموعه مرتب شده قرار دهید:

مرحله 5 : چون 7>5 است، 7 را بعد از 5 قرار می دهیم:

مرحله 6 : 1 را حذف کرده و آن را قبل از 2 قرار می دهیم:

مرحله 7: چون 6>5 و 6<7 است پس 6 را بعد از 5 قرار می دهیم:

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

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

برای درج به روش مرتب شده، لیست "مرتب شده " خود را طی می‌کنیم و به مقایسه هر گره با گره فعلی خود ادامه می‌دهیم. به محض اینکه گره‌ای را پیدا کنیم که مقدار آن از گره فعلی بیشتر است، گره فعلی را درست قبل از آن گره وارد می‌کنیم. اگر مقدار گره فعلی از هر گره دیگری در لیست نتایج ما بیشتر باشد، گره فعلی را در پایان اضافه می‌کنیم. پس از پیمایش کامل، نشانه گر اول  لیست پیوند داده شده را به سر لیست "مرتب شده " تغییرمی‌دهیم.

الگوریتم

• لیست "مرتب شده " را به صورت NULL راه ایجاد می‌کنیم.
• از فهرست پیوندی داده شده، برای هر گره، گره بعدی را در یک متغیر temp ذخیره می‌کنیم و تمام پیوندهای آن را حذف می‌کنیم.
• گره فعلی را به صورت مرتب شده در لیست "مرتب شده" وارد می‌کنیم.
• برای درج به روش مرتب شده، از لیست "مرتب شده" عبور کرده و هر گره را با گره فعلی خود مقایسه می‌کنیم. به محض اینکه گره‌ای پیدا شد که مقدار آن از گره فعلی بیشتر باشد، گره فعلی را درست قبل از آن گره وارد می‌کنیم. اگر مقدار گره فعلی بیشتر از هر گره لیست نتایج باشد، گره فعلی را در انتهای لیست نتایج اضافه کنید.
• مقدار گره فعلی را با temp آپدیت می‌کنیم.
• نشانگر سر را با نشان دادن آن به لیست "مرتب شده" آپدیت می‌کنیم.

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

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

ما می توانیم مزایای هر دو الگوریتم مرتب سازی را در یک الگوریتم واحد ترکیب کنیم و پیچیدگی زمانی الگوریتم ترکیبی خواهد بود.

O(n+k * (log n/k))

مرتب سازی ادغامی (Merg Sort) 

Sort یک الگوریتم مرتب‌سازی است که بر اساس رویکرد تقسیم و غلبه عمل می کند. آرایه را به دو نیمه کوچکتر با اندازه مساوی تقسیم می کند و سپس هر دو نیمه مرتب شده را ادغام می کند. تابع merge هر دو آرایه را در اینجا ادغام می کند، با این فرض که هر دو نیمه مرتب شده اند.

الگوریتم

روش مرتب سازی با ترکیب دو الگوریتم مرتب سازی به این صورت است:

1. تقسیم :ابتدا تمام عناصر N را به گروه های (N/K) با اندازه K تقسیم می کنیم. 

2. مرتب سازی :برای مرتب سازی ابتدا به سراغ زیر آرایه ها رفته و برای هر زیرآرایه با اندازه K یک مرتب سازی درجی انجام می دهیم.
3. ادغام :پس از اعمال مرتب‌سازی درجی بر روی زیرآرایه‌های (N/K) با اندازه K، اکنون این گروه‌ها را با استفاده از تکنیک مرتب‌سازی ادغامی، ترکیب می‌کنیم.

26849 نفر تاکنون در دوره‌های آموزشی کنکور کامپیوتر شرکت کرده‌اند.

ساجده فدائی

کیان انواری

علیرضا بهدوست

احسان داستانی

معین منعمی

علیرضا حسن زاده باقی

سعيد نوروزيان

بهمن قائدی

مهدی مزارعی

سینا مهرآبادی

محمد امین شنابی

سارا مختاری همامی

Amir hossein

محمد مهدی باقی سعدی

emelkabi

آرش آریا

محمد چاروسایی

علیرضا ملکی

علی فتحی وافق

غزل موسوی

mitra joodaki

امیرحسین پژوهان

سجاد محمدنیا

یاسمین

بهنام پروین

مرتضی آشوری

انوش مه جبین

علیرضا حسن نیا

سعید راصدی

مهدی فرح روز

یوسف عباسی

مهدی حسنی

احمد بنائیان

فاطمه سادات لطفی فاطمی

پریسا محمودی

محمد رضا کمالی

امیرحسین بلکامه

zahra mansouri

نازنین ایلخانی

محیا اشرفی

حسین پری نور

سمیه نعمتی زاد

sadra

پریسا نکوگل

فاطمه ابراهیم زاده نامور

محسن سروری

فاطمه اکبرنژاد

hadi saadati

علی بابایی

علی اله وردی

فاطمه دارپرنیا

مسعود علی اصغری

مجید محمددوست

هانیه طالبی

ندا نوروزی

اسما سهرابی

فرح رضایی

حامد ترابی

Ali.Hp

مجید جنگی زهی

فرزانه مصطفی پور

امیر ارسلان ساختیانچی

محمدامین حکیمی پور

نگین دبیران

تست نام منحصربفرد

سیدمحمدمهدی

محمدهادی قاسمی

امیر سعادت

dorsa sadat zarrabi

الینا اشرف پور

پیمان بهادرانی

محبوبه طالبی

مطالب مرتبط

همه مقالات

ساختمان داده چیست؟ آموزش ساختمان داده به زبان ساده

آشنایی با ویژگی های الگوریتم - خصوصیات الگوریتم چیست؟

7 کاربرد ریاضیات گسسته که روزمره با آن ها سر و کار دارید

درخت AVL