منتظر ارسال های شماییم!!!
یکی از مباحث اساسی دروس ساختمان داده ها و اصول طراحی الگوریتم ، یافتن الگوریتم هایی برای مرتب سازی اعدادی بهم ریخته ای است که در یک آرایه پشت سر هم قرار گرفته اند. تا کنون الگوریتم های مختلفی برای اینکار ایجاد شده است که در این مقاله با چند تا از این الگوریتم ها آشنا میشوید. همچنین مرتبه پیچیدگی هر الگوریتم (میزان زمانی که از CPU برای اجرای هر الگوریتم می گیرد) را ذکر خواهیم کرد.
الگوریتم مرتب سازی انتخابی (Selection Sort): در این روش، برنامه کوچکترین مقدار را یافته و آنرا در اولین خانه ی آرایه قرار می دهد. حال که کوچکترین عضو یافت شده است، برنامه به سراغ یافتن دومین عنصر کوچک در میان اعداد باقی مانده که از ۲ تا n هستند می رود و دومین عدد کوچک را در خانه دوم قرار میدهد. حال به سراغ سومین عدد کوچک می رود و این رویه را تا یافتن آخر عدد و قرار دادن آن در جای خودش تکرار میکند. با توجه به اینکه برنامه باید n عدد را n بار با هم مقایسه کند مرتبه ی پیچیدگی این الگوریتم O(n^2) است.
مرتب سازی حبابی (Bubble Sort): در این روش هر عنصر با عنصر بعدی اش مقایسه میشود. در صورتی که عنصر دومی کوچکتر از عنصر اولی باشد، جای دو عنصر با هم عوض میشود. برنامه به کارش ادامه میدهد و عناصر دوم و سوم را با هم مقایسه میکند و این کار را تا اخر آرایه ادامه میدهد. دوباره الگوریتم ، پویش را از اول آرایه شروع میکند و مراحل قبل را تکرار میکند و این مراحل آنقدر تکرار میشوند تا آرایه کاملا مرتب شده باشد. مرتبه ی پیچیدگی این الگوریتم O(n^2) است.
مرتب سازی درجی (Insertion Sort): در این روش عنصر اول و دوم با هم مقایسه شده و در صورت نیاز مرتب میشوند و سپس سومین عنصر با عناصر اول و دوم مقایسه میشود. در صورتی که عنصر سوم از اولی کوچکتر باشد به جای اولین عنصر می نشیند و عناصر قبلی به سمت راست هل داده میشوند. اگر عنصر سوم از اولی بزرگتر و از دومی کوچکتر باشد، بین آنها درج میشود و عنصر دوم به بعد یکی به سمت راست هل داده میشود. (پس در این روش همیشه عناصر ِ قبل از عنصری که میخواهیم مرتبش کنیم، مرتب هشتند.) این روال برای بقیه عناصر نیز اجرا میشود و هر عنصر در جای خودش قرار می گیرد تا تمام عناصر مرتب شوند. مرتبه ی پیچیدگی این الگوریتم O(n^2) است.
مرتب سازی سریع(Quick Sort) : در این الگوریتم یک عنصر را بعنوان محور (pilot) مرتب سازی انتخاب میکنیم. و تمام عناصر کوچکتر از آن را به سمت چپ آن برده و عناصر بزرگتر را به سمت راست اش می‌بریم. حالا بخش چپ خودش یک بخش جدید است که با الگوریتمی که گفتیم آنرا مرتب میکنیم و سمت راست را نیز همینطور. یعنی در سمت چپی ها دوباره یک عنصر را بعنوان pilot در نظر میگیریم و عناصر کوچکتر از pilot را به سمت چپ آن و عناصر بزرگتر از pilot این قسمت را ، به سمت راست pilot می بریم. دوباره الگوریتم را روی یک چهارم های به وجود آمده اجرا میکنیم و اینکار را آنقدر ادامه میدهیم تا کل آرایه مرتب شود. مرتبه پیچیدگی این الگوریتم در بدترین حالت O(n^2) است. اما در حال نرمال O(n log n) است که کمترین مرتبه پیچیدگی برای مرتب سازی اعداد به حساب می آید.
مرتب سازی ادغام (Merge Sort): این الگوریتم به روش بازگشتی (Recursive) عمل میکند و آرایه را به چند آرایه ی دو عنصری تقسیم میکند و آنها را مرتب میکند. سپس آرایه های کوچک را دوبه‌دو با هم ادغام میکند تا آرایه های مرتب ۴ عنصری ایجاد شوند و بعد آرایه های ۸ عنصری و به همین ترتیب پیش می رود تا آرایه اصلی بصورت مرتب شده ظاهر شود. مرتبه پیچیدگی این الگوریتم O(n log n) است.
مرتب سازی هرمی (Heap Sort): در این روش، برنامه از کل آرایه ی داده شده یک درخت MaxHeap می سازد. (درخت مکس هیپ درختی دودویی و کامل است که مقدار ذخیره شده در هر گره ، بزرگتر و یا مساوی مقدار ذخیره شده در گره فرزندانش است) سپس مقدار ماگزیمم را از درخت حذف میکند و آنرا در انتهای آرایه میگذارد و دوباره از بقیه اعداد یک درخت maxHeap میسازد و باز روش مذکور را روی آن نیز اعمال میکند تا دومین عدد بزرگ یافت شود. در این روش آرایه از آخر به اول مرتب میشود. مرتبه پیچیدگی این الگوریتم O(n log n) است.
در تصویر زیر میتوانید مقایسه ای بین سرعت سه الگوریتم که مرتبه پیچیدگی شان n log n است مشاهده کنید.
![[تصویر: 80733_1_1379093581.jpg]](https://img.manesht.ir/80733_1_1379093581.jpg)
روش هایی وجود دارند که حداقل مرتبه ی پیچیدگی هر الگوریتم را با روابطی اثبات میکنند. بطور مثال برای الگوریتم های مرتب سازی ، میزان O(n Log n) حداقل است و کمتر از این میزان ممکن نیست و همانطور که میدانیم الگوریتم های ادغام و هرمی و سریع هر سه با همین میزان پیچیدگی مرتب سازی را انجام میدهند. بنابراین الگوریتمی نمیتوان نوشت که سریعتر از این حالت عمل کند و الگوریتم های مینیمم پیچیدگی در این زمینه ،قبلا کشف و ایجاد شده اند . اما مواردی هستند مانند ضرب دو ماتریس n در n که مرتبه ی پیچیدگی شان O(n^3) است و روش های جدیدی مانند روش استراسن آنرا به O(n^2.81) کاهش داده است. طبق روشهای اثبات شده امکان کمتر شدن این میزان وجود دارد. اما هنوز الگوریتمی که هزینه ی پیچیدگی کمتری از الگوریتم استراسن داشته باشد کشف نشده است. بنابراین هنوز شما میتوانید وقت خود را روی کاهش مرتبه ی پیچیدگی این الگوریتم و یافتن الگوریتم بهینه تر بگذارید.
-----------------------------------------------------------------------------------------
الگوریتم های مرتب سازی اغلب بر اساس زیر دسته بندی می شوند:
• پیچیدگی زمانی مقایسه عناصر برحسب اندازه لیست (n) . معمولا برای یک الگوریتم مرتب سازی عادی O(n log n) بهترین حالت و O(n2) بدترین حالت است. زمان ایده آل O(n) است.
• پیچیدگی زمانی تعداد جابه جائی ها برای الگوریتم های درجا (in place).
• مصرف حافظه (و استفاده از منابع دیگر سیستم). برخی از الگوریتم های مرتب سازی برون از جا (out place) هستند. که به محل کمکی برای نگهداری داده های موقت علاوه بر داده های در حال مرتب شدن نیاز دارند.
• بعضی از الگوریتم ها بازگشتی یا غیر بازگشتی یا هردو هستند.
• پایداری. الگوریتم های مرتب سازی پایدار ترتیب نسبی رکوردها با کلیدهای مساوی را برقرار می کنند. یعنی اگر دو رکورد R و S با یک کلید وجود داشته باشد و R قبل از S در لیست اصلی آمده باشد، در لیست مرتب شده هم R قبل از S می آید.
• متد کلی. روش مرتب سازی داده ها که می تواند درج، تعویض، انتخاب، ادغام و غیره باشد. برای مثال مرتب سازی حبابی و سریع مرتب سازی تعویضی هستند.
مرتب‌سازی انتخابی
روش مرتب‌سازی انتخابی (Selection Sort) یکی از روشهای اولیه مرتب‌سازی بر اساس مقایسه عناصر است. این الگوریتم طی چند مرحله عناصر لیست را به صورت صعودی یا نزولی مرتب میکند. به این ترتیب که در هر مرحله با بررسی عناصر نامرتب، بزرگترین (یا کوچکترین) عنصر را پیدا کرده، و به انتهای لیست منتقل میکند.
(void selection_sort( int arr[ ], int n
}
;int i, j, max, temp
( --for( i = n - 1 ; i > 0 ; i
}
; max = 0
( ++for( j = 1 ; j <= i ; j
}
( [ if( arr[ max ] < arr[ j
}
; max = j
{
{
;[temp = arr[ i
; [ arr[ i ] = arr[ max
; [ arr[ max ] = temp
{
{
}
;int i, j, max, temp
( --for( i = n - 1 ; i > 0 ; i
}
; max = 0
( ++for( j = 1 ; j <= i ; j
}
( [ if( arr[ max ] < arr[ j
}
; max = j
{
{
;[temp = arr[ i
; [ arr[ i ] = arr[ max
; [ arr[ max ] = temp
{
{
[/align]
حلقه بیرونی حد نصاب پیمایش را مشخص کرده، و حلقه درونی به ازای هر تکرار حلقه بیرونی، بزرگترین عنصر لیست نامرتب را می‌یابد. سپس محل این عنصر با عنصر انتهای بخش نامرتب جابجا میشود.
پیچیدگی زمانی مرتب‌سازی انتخابی
تعداد عناصر لیست را n در نظر میگیریم. بر اساس توضیحات فوق این الگوریتم n - 1 مرحله دارد. در هر مرحله، عنصر ابتدایی در max قرار گرفته، و بقیه عناصر با آن مقایسه میشوند. پس در مرحله اول تعداد n - 1 مقایسه، در مرحله دوم تعداد n - 2 مقایسه، و به همین ترتیب در مرحله iام تعداد n - i مقایسه صورت می‌گیرد. پس اگر ( T( n تعداد کل مقایسه‌ها را نشان دهد، می‌توان نوشت:
T( n ) = ( n - 1 ) + ( n - 2 ) + ( n - 3 ) + ... + 2 + 1 = n ( n - 1 ) / 2
که از مرتبه ( Θ( n^2 است.ویژگی‌های مرتب‌سازی انتخابی
۱- پیچیدگی زمانی اجرای این الگوریتم بر اساس محاسبات فوق در بدترین حالت ( Θ( n^2 است. با توجه به قطعه کد نوشته شده، ترتیب عناصر تغییری در عملکرد آن اینجا نمی‌کند. یعنی این الگوریتم برای داده‌های کاملا مرتب، نامرتب تصادفی و مرتب معکوس به یک ترتیب عمل کرده و تمام مقایسه‌های محاسبه شده در رابطه فوق را انجام میدهد. بنابراین پیچیدگی این الگوریتم در بهترین حالت و حالت منوسط نیز ( Θ( n^2 است.
۲- مرتب‌سازی انتخابی یک روش مرتب‌سازی درجا است. یعنی عملیات مرتب‌سازی به در داخل خود لیست و بدون نیاز به حافظه کمکی بزرگ انجام می‌گیرد.
۳- در پیاده‌سازی مرتب‌سازی انتخابی به روش فوق، اگر دو عنصر با مقدار بیشینه داشته باشیم، اولی انتخاب شده و به انتهای لیست منتقل میشود. در نتیجه ترتیب آنها به هم می‌خورد. بنابراین این پیاده‌سازی روش پایدار نیست. در روش پایدار ترتیب عناصر با مقدار یکسان تغییر نمی‌کند. اما اگر در مقایسه عناصر آرایه به جای > از => استفاده کنید، مرتب‌سازی پایدار خواهد شد.
مرتب‌سازی درجی
روش مرتب‌سازی درجی (Insertion Sort) یکی از روشهای مقدماتی مرتب‌سازی مبتنی بر مقایسه عناصر است که در مقایسه با روشهای دیگر بیشتر مورد توجه قرار دارد.
قفسه کتابی را در نظر بگیرید که قصد دارید کتاب‌ها را بر اساس عنوان و به ترتیب حروف الفبا مرتب کنید. از یک سمت قفسه شروع به مرتب کردن می‌کنید. ابتدا کتاب دوم را با کتاب اول مقایسه کرده و در صورت لزوم جابجا می‌کنید. سپس کتاب سوم را از محل خود برداشته، و در مقایسه با دو کتاب قبلی در محل مناسب قرار می‌دهید. به همین ترتیب کتاب‌های بعدی را نیز نسبت به کتاب‌های مرتب‌شده قبلی در محل مناسب درج می‌کنید، تا به آخر قفسه برسید.
عملکرد این الگوریتم به گونه‌ای است که در پایان هر مرحله قسمتی از داده‌ها به صورت کامل مرتب هستند. در مرحله بعدی نیز داده‌ای از میان داده‌های غیرمرتب به این قسمت مرتب وارد شده و در محل مناسب درج میشود.
پیاده‌سازی مرتب‌سازی درجی
الگوریتم مرتب‌سازی درجی به زبان برنامه‌نویسی ++C برای مرتب کردن عناصر آرایه‌ای از اعداد صحیح به صورت زیر پیاده‌سازی میشود:
(void insertion_sort( int arr[ ], int n
}
; int i, j, t
( ++ for( i = 1 ; i < n ; i
}
;[ t = arr[ i
( --for( j = i ; j > 0 ; j
}
[ if( t >= arr[ j - 1
}
; break
{
;[ arr[ j ] = arr[ j - 1
{
; arr[ j ] = t
{
{
}
; int i, j, t
( ++ for( i = 1 ; i < n ; i
}
;[ t = arr[ i
( --for( j = i ; j > 0 ; j
}
[ if( t >= arr[ j - 1
}
; break
{
;[ arr[ j ] = arr[ j - 1
{
; arr[ j ] = t
{
{
پیچیدگی زمانی مرتب‌سازی درجی
بدترین حالت این الگوریتم زمانی اتفاق می‌افتد که لیست به صورت معکوس مرتب باشد. در این حالت حلقه داخلی در مرحله اول یک بار، در مرحله دوم دو بار، در مرحله سوم سه بار، و در حالت کلی در مرحله iام (i < n) به تعداد i بار تکرار میشود. پس اگر ( T( n تعداد مقایسه‌های حلقه داخلی به ازای n عنصر را نشان دهد، می‌توان نوشت:
T( n ) = 1 + 2 + 3 + ... + (n - 1) = n ( n - 1 ) / 2 ≈ n2 / 2
که از مرتبه اجرای ( Θ( n^2 است.
بهترین حالت الگوریتم زمانی است است که لیست از پیش مرتب‌شده باشد. در این حالت هر حلقه درونی با یکبار مقایسه خاتمه پیدا میکند. در نتیجه تعداد کل مقایسه‌ها از مرتبه ( Θ( n خواهد بود.
حالت متوسط برای شرایطی که عناصر به صورت تصادفی پخش شده باشند محاسبه میشود. در این حالت در هر تکرار حلقه بیرونی، حلقه داخلی برای یافتن محل مناسب درج عنصر جدید به طور میانگین نصف لیست مرتب‌شده را پیمایش میکند. در نتیجه حدود n2 / 4 مقایسه صورت خواهد گرفت (چرا؟). این تعداد اگرچه از مرتبه اجرایی ( Θ( n^2 است، اما در مقایسه با بدترین حالت (تقریبا n2 / 2 مقایسه) عملکرد بهتری را نشان میدهد.
ویژگی‌های مرتب‌سازی درجی
۱- پیچیدگی زمانی الگوریتم مرتب‌سازی درجی در بدترین حالت و حالت متوسط ( Θ( n^2، و در بهترین حالت ( Θ( n است.
۲- یکی از ویژگی‌های مهم مرتب‌سازی درجی این است که در حالت متوسط برای درج عنصر جدید در لیست مرتب‌شده نیاز به مقایسه عنصر با تمامی عناصر ندارد. به همین دلیل کارآیی آن در مقایسه با بدترین حالت بهتر است. از سوی دیگر، این روش برای مرتب کردن عناصر به جای عمل جابجایی - که نیاز به سه عمل اصلی مقداردهی دارد - از کپی کردن استفاده میکند. در این روش ابتدا مقدار عنصر جدید در یک متغیر کمکی (در قطعه کد فوق متغیر t) ذخیره شده و جابجا کردن عناصر بزرگتر به انتهای لیست با یک عمل اصلی انجام می‌گیرد. در انتها نیز مقدار عنصر جدید در محل مناسب درج میشود. در چنین حالتی تعداد اعمال اصلی انچام شده کمتر از تعداد اعمال مورد نیاز در عمل جابجایی است. به همین دلیل این روش به روشهای مقدماتی دیگر (مانند روش مرتب‌سازی حبابی و انتخابی) ارجحیت داشته و در مراحل نهایی مرتب‌سازی‌های پیشرفته (مانند روش مرتب‌سازی سریع) از این روش به عنوان روش مرتب‌سازی جایگزین استفاده میشود. اگر تعداد عناصر لیست کمتر از بیست عنصر باشد، این روش در مقایسه بار روشهای متداول مرتب‌سازی سریعتر عمل میکند.
۳- حافظه مصرفی مرتب‌سازی درجی از مرتبه ( Θ( ۱ بوده و مستقل از اندازه لیست است. چنین الگوریتمی را مرتب‌سازی درجا گویند.
۴- در صورتی که مرتب‌سازی درجی به صورت قطعه‌کد فوق پیاده‌سازی شود، یک مرتب‌سازی پایدار خواهد بود. یعنی ترتیب عناصر با مقادیر یکسان در حین مرتب‌سازی تغییر نمی‌کند. اما اگر به جای شرط [ t >= arr[ j - 1 از شرط [ t > arr[ j - 1 استفاده شود، الگوریتم ناپایدار خواهد شد.
منابع : متفاوت از ویکی پدیا یا راهیان ارشد ...
منابع : متفاوت از ویکی پدیا و ....