برنامه ریزی تا کنکور ارشد و دکتری: مشاوره خصوصیت با استاد رضوی رو رزرو کن!
ویس توضیحات مشاوره رزرو مشاوره
کنکور کامپیوتر
0
ورود | ثبت نام
نظرات
اشتراک
بالا
علاقه‌مندی

اشتراک
 

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

در این صفحه مرتب سازی درجی (Insertion Sort) به بهترین روش ممکن آموزش داده شده و روش‌های محتلف پیاده‌سازی الگوریتم مرتب سازی درجی بیان شده است.

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

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

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

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

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

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

  1. آموزش جامع مرتب سازی سریع
  2. آموزش جامع مرتب سازی حبابی
  3. آموزش جامع مرتب سازی ادغامی

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

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

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

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

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

نتیجه تعداد جابه‌جایی تعداد مقایسه گذر
لیست[2...1]a مرتب \[\mathrm{\circ }\le \ \ \ \ \ \le \mathrm{1}\] 1 اول
لیست[3...1]a مرتب \[\mathrm{\circ }\le \ \ \ \ \ \le \mathrm{2}\] \[\mathrm{1}\le \ \ \ \ \ \le \mathrm{2}\] دوم

\[\mathrm{\vdots }\]

\[\mathrm{\vdots }\]

\[\mathrm{\vdots }\]

\[\mathrm{\vdots }\]

لیست[n...1]a مرتب \[\mathrm{\circ }\le \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \le \mathrm{n}\mathrm{-}\mathrm{1}\] \[\mathrm{1}\le \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \le \mathrm{n}\mathrm{-}\mathrm{1}\] 1- n ام
  \[\mathrm{\circ }\le \text{جابه‌جایی‌ها}\mathrm{\ }\mathrm{\le }\frac{\mathrm{n}\left(\mathrm{n}\mathrm{-}\mathrm{1}\right)}{\mathrm{2}}\] \[\mathrm{n}\mathrm{-}\mathrm{1}\mathrm{\le }\text{مقایسات}\mathrm{\ }\mathrm{\ }\mathrm{\le }\frac{\mathrm{n}\left(\mathrm{n}\mathrm{-}\mathrm{1}\right)}{\mathrm{2}}\]  
نکته قابل توجه در مرتب‌سازی درجی آن است که تا گذر آخر (1- n) اٌم، محل هیچ‌کدام از عناصر ثابت نیست.

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


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}}$  باشد، مراحل مرتب‌سازی به شرح زیر است: 

در این تصویر مراحل انجام مثال فوق نشان داده شده است.ویژگی های مرتب سازی درجی

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

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

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

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

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

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

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

ما هزینه هر عملیات i را به صورت Ci در نظر می‌گیریم که 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 )

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

زمانیکه آرایه ورودی مرتب شده باشد، الگوریتم درجی در بهترین حالت پیچیدگی زمانی خود عمل می کند. (tj = 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

توضیحات جابه‌جایی مقایسه ورودی گذرها
2 با 1 مقایسه شده سپس بدون جابه‌جایی در جای خود قرار می‌گیرد. 0 1

\[1,\underline{\overline{\left|2\right|}}\]

گذر اول
3 با 2 مقایسه شده سپس بدون جابه‌جایی در جای خود قرار می‌گیرد. 0 1 \[1\ ,\ 2\ ,\underline{\overline{\left|\mathrm{3}\right|}}\] گذر دوم
\[\mathrm{\vdots }\] \[\mathrm{\vdots }\] \[\mathrm{\vdots }\] \[\mathrm{\vdots }\] \[\mathrm{\vdots }\]
n با 1 – n مقایسه شده سپس بدون جابه‌جایی در جای خود قرار می‌گیرد. 0 1 \[1\ ,\ 2\ ,\ ...\ ,\ n-1\ ,\underline{\overline{\left|\mathrm{\ }\mathrm{n}\mathrm{\ }\right|}}\] گذر 1-n ام

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

زمانیکه آرایه ورودی به صورت معکوس مرتب شده باشد، الگوریتم درجی در بدترین حالت پیچیدگی زمانی خود عمل می کند. (tj = 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}}\]

توضیحات جابه‌جایی مقایسه ورودی گذرها
1 – n با n مقایسه شده، سپس با 1 جابه‌جایی در مکان مناسب قرار می‌گیرد. 1 1 \[1\ ,\ \underline{\overline{\left|\mathrm{n-}\mathrm{n}\right|}}\] گذر اول
2 – n با n، 1 – n مقایسه شده سپس با 2 جابه‌جایی در مکان مناسب قرار می‌گیرد. 2 2 \[n-1\ ,\ n\ ,\underline{\overline{\left|\mathrm{n-}\mathrm{2}\right|}}\] گذر دوم
\[\mathrm{\vdots }\] \[\mathrm{\vdots }\] \[\mathrm{\vdots }\] \[\mathrm{\vdots }\] \[\mathrm{\vdots }\]
1 با n , ... , 2 مقایسه شده سپس با 1 – n جابه‌جایی در مکان مناسب قرار می‌گیرد. 1 – n 1 – n \[2\ ,\ ...\ ,\ n-1\ ,\ n\ ,\underline{\overline{\left|\mathrm{1}\right|}}\] گذر 1-n ام

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

در حالت متوسط :  tj = (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


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

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


# 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

		
// 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);
  }
}

کد مرتب سازی در JavaScript 

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

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

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

Sorting Algorithms Time Complexity Space Complexity stable
(متعادل)
In place
(درجا)
Best Case Average Case Worse Case Worce Case
مرتب سازی درجی (insertion sort) O(n) O(n²) O(n²) O(1) 1 1
مرتب سازی انتخابی (Selection sort) O(n²) O(n²) O(n²) O(1) 0 1
مرتب سازی حبابی (Bubble sort) O(n) O(n²) O(n²) O(1) 1 1
مرتب سازی ادغامی (Merg Sort) O(nlogn) O(nlogn) O(nlogn) O(n) 1 0

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

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

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

مرتب‌سازی حبابی یک الگوریتم مرتب‌سازی ساده است که به طور مکرر فهرستی را مرور می‌کند، جفت‌های مجاور را با هم مقایسه می‌کند و اگر ترتیب اشتباهی داشته باشند، آنها را تعویض می‌کند. می‌توانید برای آشنایی بیشتر با الگوریتم مرتب سازی حبابی به صفحه مرتب سازی حبابیآموزش مرتب سازی حبابی (Bubble Sort) بصورت 0 تا 100آموزش مرتب سازی حبابی (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(n2)است. میانگین مورد O(n2) است. بهترین حالت O(n) است.
  2. پیچیدگی مکانی: مرتب‌سازی ادغامی، بازگشتی بودن پیچیدگی مکانی O(n) را می‌گیرد، بنابراین نمی‌توان آن را برای جا هایی که حافظه نداریم، استفاده کرد. با این حال، مرتب‌سازی درجی فقط پیچیدگی فضای O(1) را اشغال می‌کند. کل آرایه را با استفاده از یک متغیر اضافی مرتب می کند.
  3. مجموعه داده ها: مرتب سازی ادغامی قطعا برای مجموعه داده‌های بزرگ ترجیح داده می شود. این به این دلیل است که مقایسه همه عناصر موجود در آرایه اتفاق می‌افتد، بنابراین برای مجموعه داده‌های کوچک چندان مفید نیست. با این حال، مرتب‌سازی درجی گزینه‌ای برای مجموعه داده‌های کمتر است. زمانی که داده ها از قبل مرتب شده باشند یا تقریبا مرتب شده باشند، سریع می شود زیرا به طور پیش فرض، مقادیر مرتب شده را رد می‌کند.
  4. کارایی: با توجه به میانگین پیچیدگی زمانی هر دو الگوریتم، به جرات می‌توان گفت مرتب‌سازی ادغامی از نظر زمان و مرتب‌سازی درجی از نظر مکان کارآمد هستند.
  5. روش مرتب سازی: مرتب‌سازی ادغامی یک روش مرتب‌سازی خارجی است که در آن داده‌هایی که قرار است مرتب شوند را نمی‌توان در حافظه جای داد و برای مرتب‌سازی به حافظه کمکی نیاز دارد، در حالی که مرتب‌سازی درجی بر اساس این ایده است که یک عنصر از عناصر ورودی در آن مصرف می‌شود و در هر تکرار در موقعیت صحیح خود (موقعیتی که در یک آرایه مرتب شده است) قرار می‌گیرد.

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

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

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

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

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

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

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

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

{35, 14}, {33, 19}, {42, 27} {10, 44}  در این تصویر گام اول برای مرتب سازی در Shell Sort را می‌توانید مشاهده کنید

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

نتیجه گام اول مرتب سازی Shell Sort در این تصویر نشان داده شده است.

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

 

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

 

در این تصویر گام دوم برای مرتب سازی در Shell Sort را می‌توانید مشاهده کنید

نتیجه :

نتیجه گام دوم مرتب سازی Shell Sort در این تصویر نشان داده شده است.

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

نتیجه نهایی Shell Sort در این تصویر نشان داده شده است.

پیچیدگی زمانی الگوریتم مرتب سازی شل در بهترین حالت O(n*logn)، در حالت میانگین O(n*log(n)*2)  و در بدترین حالت O(n2) است.

مرتب سازی درجی دودویی (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. گام دوم در الگوریتم مرتب سازی درجی باینری در این تصویر نشان داده شده است.
  6. حالا عنصر سوم را می‌گیریم، 1 (توجه داشته باشید که تمام عناصر قبل از عنصر فعلی مرتب شده‌اند.)
  7. ما 1 را در کلید ذخیره می‌کنیم و با استفاده از جستجوی باینری، عنصر بزرگتر از 1 در قسمت مرتب شده پیدا می‌کنیم.
  8. در اینجا، عنصر مورد نیاز 6 است. بنابراین، 6 و 8 را به سمت راست تغییر می دهیم و قبل از جابجایی، 1 را در موقعیت 6 قرار می دهیم. آرایه اکنون به شکل زیر است:
  9. گام سوم در الگوریتم مرتب سازی درجی باینری در این تصویر نشان داده شده است.
  10. اکنون عنصر 4، "5" را می گیریم و آن را در کلید ذخیره می کنیم.
  11. با استفاده از جستجوی دودویی، عنصری که فقط بزرگتر از 5 هستش را در قسمت مرتب شده پیدا می کنیم. در این حالت عنصر مورد نیاز 6 است.
  12. مجدداً 6 و 8 را یک اندیس به سمت راست می بریم و 5 را در موقعیت 6 قبل از جابجایی قرار می دهیم. آرایه اکنون به شکل زیر است:
  13. گام چهارم در الگوریتم مرتب سازی درجی باینری در این تصویر نشان داده شده است.
  14. اکنون آخرین عنصر را که 3 است می گیریم و عنصر را در قسمت مرتب شده بزرگتر از آن می یابیم.
  15. عنصر مورد نیاز 5 است. ما 5، 6، و 8 را یک شاخص به سمت راست تغییر می دهیم و قبل از جابجایی، 3 را در موقعیت 5 قرار می دهیم. آرایه به دست آمده به صورت زیر است:
  16. گام پنجم در الگوریتم مرتب سازی درجی باینری در این تصویر نشان داده شده است.

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

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

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

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

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

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

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

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

مرحله 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 قرار می دهیم:

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

پیچیدگی زمانی الگوریتم مرتب سازی درجی برای لیست پیوندی، در بهترین حالت O(n)، در حالت میانگین  و در بدترین حالت O(n2) است.

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

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

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

الگوریتم

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

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

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

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

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

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

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

الگوریتم

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

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

آیا می توانیم پیچیدگی زمانی (Time Complexity) در مرتب سازی درجی را بهتر کنیم؟

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

آیا مرتب سازی درجی دودویی یک الگوریتم مرتب سازی پایدار (Stable) است؟

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

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

همچنین هر گونه سوالی در مورد کلاس‌های آنلاین کنکور کامپیوتر و یا تهیه فیلم‌ها و یا رزرو مشاوره تک جلسه‌ای تلفنی با استاد رضوی دارید می‌توانید به طرق زیر از تیم پشتیبانی بپرسید:

آی دی تلگرام تیم پشتیبانی:     konkurcomputer_admin@

شماره ثابت موسسه:   09378555200

امتیازدهی4.3 1 1 1 1 1 1 1 1 1 14.30 امتیاز (5 رای)
اشتراک
بارگذاری نظرات
تلگرام اینستاگرام تماس با پشتیبانی: 09378555200 تماس با پشتیبانی: 09378555200