طراحی الگوریتم

[کاربر حذف شده 8031]

مرتب‌سازی ادغامی

روش مرتب‌سازی ادغامی (Merge Sort) یک روش مرتب‌سازی مبتنی بر مقایسه عناصر با استفاده از روش تقسیم و غلبه است. این روش از مراحل بازگشتی زیر تشکیل یافته است:

1- آرایه را به دو زیرآرایه با اندازه تقریبا یکسان تقسیم کن.

2- دو زیرآرایه را به روش مرتب‌سازی ادغامی مرتب کن.

3- دو زیرآرایه مرتب‌شده را ادغام کن.

پیاده‌سازی مرتب‌سازی ادغامی

بر اساس توضیحات فوق قطعه کد زیر به زبان برنامه‌نویسی ++C الگوریتم مرتب‌سازی ادغامی را پیاده‌سازی می‌کند:

void merge_sort( int arr[ ], int low, int high )

{

if( low >= high )

{

return;

}

int mid = ( low + high ) / 2;

merge_sort( arr, low, mid );

merge_sort( arr, mid + 1, high );

merge( arr, low, mid, high );

}​

این قطعه کد بازه‌های low تا mid و mid + 1 تا high را به صورت بازگشتی مرتب کرده، و سپس توسط تابع merge ادغام می‌کند. به این ترتیب آرایه arr از بازه low تا high مرتب می‌شود.

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

قطعه کد زیر یک پیاده‌سازی درجا برای تابع merge است:

void merge( int arr[ ], int low, int mid, int high )

{

int i, j, k, t;

j = low;

for( i = mid + 1 ; i <= high ; i++ )

{

while( arr[ j ] <= arr[ i ] && j < i )

{

j++;

}

if( j == i )

{

break;

}

t = arr[ i ];

for( k = i ; k > j ; k -- )

{

arr[ k ] = arr[ k - 1 ];

}

arr[ j ] = t;

}

}
​

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

به عنوان مثال اگر هدف ادغام کردن زیرآرایه‌های زیر باشد:



1 3 6 9 / 2 4 5 8



ترتیب چینش عناصر پس از اتمام هر تکرار حلقه بیرونی قطعه کد فوق، به این ترتیب خواهد بود:

1) 1 3 6 9 / 2 4 5 8 => 1 2 3 6 9 / 4 5 8

2) 1 2 3 6 9 / 4 5 8 => 1 2 3 4 6 9 / 5 8

3) 1 2 3 4 6 9 / 5 8 => 1 2 3 4 5 6 9 / 8

4) 1 2 3 4 5 6 9 / 8 => 1 2 3 4 5 6 8 9 /


​

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

تعداد عناصر آرایه را n و تعداد مقایسه‌های مورد نیاز جهت مرتب‌سازی این عناصر را ( T( n در نظر می‌گیریم.

بر اساس تعریف بازگشتی این الگوریتم، مرتب کردن n عنصر نیاز به مرتب شدن دو زیر آرایه تقریبا n / 2 عنصری دارد. پس از این مرحله، این دو زیرآرایه توسط تابع merge ادغام می‌شوند.

جهت ادغام دو زیرآرایه با قطعه کد فوق - که در مجموع n عنصر دارند - حداکثر n مقایسه اتفاق خواهد افتاد (چرا؟). پس می‌توان نوشت:

T( n ) = 2 T( n / 2 ) + n​

حل این رابطه بازگشتی نشان از مرتبه اجرای ( Ө( n log n دارد.



حافظه مصرفی مرتب‌سازی ادغامی

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



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

1- پیچیدگی زمانی اجرای الگوریتم در تمامی حالات ( Ө( n log n است. چرا که این الگوریتم تحت هر شرایطی آرایه را به دو قسمت کرده و مرتب‌سازی را انجام می‌دهد.

2- پیچیدگی حافظه مصرفی بستگی به روش پیاده‌سازی مرحله ادغام دارد، که تا ( O( n افزایش می‌یابد. پیاده‌سازی درجای این الگوریتم حافظه مصرفی مرتبه ( Ө( 1 دارد. اما اجرای آن در بدترین حالت زمانبر است.

3- الگوربتم مرتب‌سازی ادغامی با پیاده‌سازی فوق یک روش پایدار است. چنین الگوریتمی ترتیب عناصر با مقدار یکسان را پس از مرتب‌سازی حفظ می‌کند.

منبع : الگوریتمستان

 

[کاربر حذف شده 8031]

پاسخ : اموزش الگوریتم

مرتب‌سازی سریع

روش مرتب‌سازی سریع (Quick Sort) یکی از الگوریتم‌های مشهور مرتب‌سازی داده‌ها است. این الگوریتم طی مراحل بازگشتی زیر یک روش تقسیم و غلبه برای مرتب کردن داده‌ها ارائه می‌نماید:

1- انتخاب عنصر محوری: یکی از عناصر آرایه به عنوان عنصر محوری (pivot) - به عنوان مثال عنصر اول - انتخاب می‌شود.

2- تقسیم آرایه: چینش عناصر آرایه به قسمی تغییر داده می‌شود که تمامی عناصر کوچکتر یا مساوی محور در سمت چپ آن، و تمامی عناصر بزرگتر در سمت راست آن قرار بگیرند. این دو قسمت زیر آرایه‌های چپ و راست نامیده می‌شوند.

3- مرتب‌سازی بازگشتی: زیرآرایه‌های چپ و راست به روش مرتب‌سازی سریع مرتب می‌شوند.



پیاده‌سازی تقسیم آرایه

با استفاده از تابع زیر - با فرض انتخاب عنصر اول به عنوان محور- می‌توان مرحله تقسیم آرایه را پیاده‌سازی کرد:

int partition( int arr[ ], int low, int high )

{

int left = low + 1, right = high, temp, pivot = arr[ low ];

while( left < right )

{

while( arr[ left ] <= pivot && left <= right )

{

left++;

}

while( arr[ right ] > pivot && left <= right )

{

right--;

}

if( left < right )

{

temp = arr[ left ];

arr[ left ] = arr[ right ];

arr[ right ] = temp;

}

}

arr[ low ] = arr[ right ];

arr[ right ] = pivot;

return right;

}
​

تابع partition آرایه arr و اندیس بازه مورد نظر از آرایه جهت مرتب‌سازی را با low و high دریافت می‌کند. در متغیر pivot مقدار عنصر ابتدای بازه به عنوان عنصر محوری ذخیره می‌شود. همینطور در متغیر left اندیس عنصر دوم - اولین عنصر غیر محور بازه - و در متغیر right اندیس عنصر آخر ذخیره می‌شوند.

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

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

3 0 6 1 7 2 5
​

تابع به صورت ( partision( arr, 0, 6 فراخوانی می‌شود:

3 0 6 1 7 2 5: pivot = 3, left = 1, right = 6​

شرط left < right برقرار است. پس وارد حلقه شده و حلقه‌های درونی اجرا می‌شوند. پس از اجرای حلقه‌ها مقدار left و right به اندیس دو و پنج تغییر می‌کنند و مقادیر متناظر آنها جابجا می‌شوند:

3 0 2 1 7 6 5: pivot = 3, left = 2, right = 5​

شرط left < right همچنان برقرار است. حلقه‌های درونی مقدار left و right را به چهار و سه تغییر می‌دهند. اما چون left < right نیست جابجایی انجام نمی‌شود:

3 0 2 1 7 6 5: pivot = 3, left = 4, right = 3​

با نادرست بودن شرط left < right از حلقه بیرونی نیز خارج شده و به دستورات جابجایی نهایی می‌رسیم:

1 0 2 3 7 6 5​

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



پیاده‌سازی مرتب‌سازی سریع

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

void quick_sort( int arr[ ], int low ,int high )

{

if( low < high )

{

int pivot = partition( arr, low, high );

quick_sort( arr, low, pivot - 1 );

quick_sort( arr, pivot + 1, high );

}

}
​

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

در مثال فوق وضعیت آرایه پس از اجرای دستور تقسیم آرایه در هر فراخوانی به صورت زیر خواهد بود:

مرتب‌سازی سریع

0) 3 0 6 1 7 2 5: low = 0, high = 6

1) quick_sort( arr, 0, 6 ) -> 1 0 2 3 7 6 5, pivot = 3

2) quick_sort( arr, 0, 2 ) -> 0 1 2 3 7 6 5, pivot = 1

3) quick_sort( arr, 0, 0 ) -> 0 1 2 3 7 6 5

4) quick_sort( arr, 2, 2 ) -> 0 1 2 3 7 6 5

5) quick_sort( arr, 4, 6 ) -> 0 1 2 3 5 6 7, pivot = 6

6) quick_sort( arr, 4, 5 ) -> 0 1 2 3 5 6 7, pivot = 4

7) quick_sort( arr, 5, 5 ) -> 0 1 2 3 5 6 7
​

در پایان آرایه مرتب شده است.



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

در مرتب‌سازی‌های مبتنی بر مقایسه عموما تعداد مقایسه‌ها ملاک بررسی پیچیدگی زمانی است. ( T( n را تعداد مقایسه‌های لازم برای مرتب کردن آرایه‌ای به طول n با روش مرتب‌سازی سریع در نظر می‌گیریم. تابع partition برای تقسیم‌بندی بازه‌ای به طول n به غیر از عنصر محوری تمامی عناصر را مقایسه می‌کند و به n - 1 مقایسه نیاز دارد.

بهترین حالت قرار گرفتن عنصر محوری زمانی است که این عنصر در وسط بازه قرار بگیرد، و آن بازه را به دو بازه با اندازه تقریبا برابر تقسیم کند. در این حالت هر زیربازه ( T( n / 2 مقایسه نیاز خواهد داشت، و می‌توان نوشت:

T( n ) = 2 T( n / 2 ) + n - 1
​

با استفاده از قضیه اصلی یا حل رابطه بازگشتی مشخص می‌شود که ( T( n از مرتبه اجرای ( Ө( n log n است.

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

T( n ) = T( 0 ) + T( n - 1) + n - 1 = T( n - 1 ) + n - 1​

حل این رابطه بازگشتی نشان از مرتبه اجرایی ( Ө( n2 در بدترین حالت اجرای الگوریتم دارد.



ویژگی‌های مرتب‌سازی سریع

1- پیچیدگی زمانی اجرای الگوریتم در بهترین حالت ( Ө( n log n و در بدترین حالت ( Ө( n2 است. با استفاده محاسبات ریاضی می‌توان نشان داد در حالت متوسط نیز مرتبه اجرا ( Ө( n log n است.

2- این الگوریتم یک مرتب‌سازی درجا است. یعنی میزان حافظه مصرفی الگوریتم مستقل از طول آرایه است.

3- زمانی که تعداد عناصر آرایه کم باشد، سرعت اجرای مرتب‌سازی درجی بهتر از مرتب‌سازی سریع است. به همین دلیل طی مراحل بازگشتی مرتب‌سازی سریع، اگر طول بازه عدد کوچکی باشد، معمولا بازه با مرتب‌سازی درجی مرتب می‌شود.

4- الگوربتم مرتب‌سازی سریع با پیاده‌سازی فوق یک روش ناپایدار است. چنین الگوریتمی لزوما ترتیب عناصر با مقدار یکسان را پس از مرتب‌سازی حفظ نمی‌کند.

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

منبع : الگوریتمستان

 

[کاربر حذف شده 8031]

پاسخ : اموزش الگوریتم

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

روش مرتب‌سازی درجی (Insertion Sort) یکی از روش‌های مقدماتی مرتب‌سازی مبتنی بر مقایسه عناصر است که در مقایسه با روش‌های دیگر بیشتر مورد توجه قرار دارد.

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

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

0) 5 1 2 7 3 6



1) 1 5 2 7 3 6

2) 1 2 5 7 3 6

3) 1 2 5 7 3 6

4) 1 2 3 5 7 6

5) 1 2 3 5 6 7

​

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

الگوریتم مرتب‌سازی درجی به زبان برنامه‌نویسی ++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;

}

}
​

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

5 1 2 7 3 6​

در مرحله اول i = 1 و t = 1 است:

j = 1: 5 5 2 7 3 6

: 1 5 2 7 3 6​

در مرحله دوم i = 2 و t = 2 است:

j = 2: 1 5 5 7 3 6

j = 1: 1 5 5 7 3 6

: 1 2 5 7 3 6​

در مرحله سوم i=3 و t = 7 است:

j = 3: 1 2 5 7 3 6

: 1 2 5 7 3 6​

در مرحله چهارم i = 4 و t = 3 است:

j = 4: 1 2 5 7 7 6

j = 3: 1 2 5 5 7 6

j = 2: 1 2 5 5 7 6

: 1 2 3 5 7 6



و​

در مرحله پنجم i = 5 و t = 6 است:

j = 5: 1 2 3 5 7 7

j = 4: 1 2 3 5 7 7

: 1 2 3 5 6 7


​

در پایان لیست مرتب شده است.



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

بدترین حالت این الگوریتم زمانی اتفاق می‌افتد که لیست به صورت معکوس مرتب باشد. در این حالت حلقه داخلی در مرحله اول یک بار، در مرحله دوم دو بار، در مرحله سوم سه بار، و در حالت کلی در مرحله iام (i < n) به تعداد i بار تکرار می‌شود. پس اگر ( T( n تعداد مقایسه‌های حلقه داخلی به ازای n عنصر را نشان دهد، می‌توان نوشت:

T( n ) = 1 + 2 + 3 + ... + (n - 1) = n ( n - 1 ) / 2 ≈ n2 / 2​

که از مرتبه اجرای ( Θ( n2 است.

بهترین حالت الگوریتم زمانی است است که لیست از پیش مرتب‌شده باشد. در این حالت هر حلقه درونی با یکبار مقایسه خاتمه پیدا می‌کند. در نتیجه تعداد کل مقایسه‌ها از مرتبه ( Θ( n خواهد بود.

حالت متوسط برای شرایطی که عناصر به صورت تصادفی پخش شده باشند محاسبه می‌شود. در این حالت در هر تکرار حلقه بیرونی، حلقه داخلی برای یافتن محل مناسب درج عنصر جدید به طور میانگین نصف لیست مرتب‌شده را پیمایش می‌کند. در نتیجه حدود n2 / 4 مقایسه صورت خواهد گرفت (چرا؟). این تعداد اگرچه از مرتبه اجرایی ( Θ( n2 است، اما در مقایسه با بدترین حالت (تقریبا n2 / 2 مقایسه) عملکرد بهتری را نشان می‌دهد.



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

1- پیچیدگی زمانی الگوریتم مرتب‌سازی درجی در بدترین حالت و حالت متوسط ( Θ( n2، و در بهترین حالت ( Θ( n است.

2- یکی از ویژگی‌های مهم مرتب‌سازی درجی این است که در حالت متوسط برای درج عنصر جدید در لیست مرتب‌شده نیاز به مقایسه عنصر با تمامی عناصر ندارد. به همین دلیل کارآیی آن در مقایسه با بدترین حالت بهتر است. از سوی دیگر، این روش برای مرتب کردن عناصر به جای عمل جابجایی - که نیاز به سه عمل اصلی مقداردهی دارد - از کپی کردن استفاده می‌کند. در این روش ابتدا مقدار عنصر جدید در یک متغیر کمکی (در قطعه کد فوق متغیر t) ذخیره شده و جابجا کردن عناصر بزرگتر به انتهای لیست با یک عمل اصلی انجام می‌گیرد. در انتها نیز مقدار عنصر جدید در محل مناسب درج می‌شود. در چنین حالتی تعداد اعمال اصلی انچام شده کمتر از تعداد اعمال مورد نیاز در عمل جابجایی است. به همین دلیل این روش به روش‌های مقدماتی دیگر (مانند روش مرتب‌سازی حبابی و انتخابی) ارجحیت داشته و در مراحل نهایی مرتب‌سازی‌های پیشرفته (مانند روش مرتب‌سازی سریع) از این روش به عنوان روش مرتب‌سازی جایگزین استفاده می‌شود. اگر تعداد عناصر لیست کمتر از بیست عنصر باشد، این روش در مقایسه بار روش‌های متداول مرتب‌سازی سریعتر عمل می‌کند.

3- حافظه مصرفی مرتب‌سازی درجی از مرتبه ( Θ( 1 بوده و مستقل از اندازه لیست است. چنین الگوریتمی را مرتب‌سازی درجا گویند.

4- در صورتی که مرتب‌سازی درجی به صورت قطعه‌کد فوق پیاده‌سازی شود، یک مرتب‌سازی پایدار خواهد بود. یعنی ترتیب عناصر با مقادیر یکسان در حین مرتب‌سازی تغییر نمی‌کند. اما اگر به جای شرط [ t >= arr[ j - 1 از شرط [ t > arr[ j - 1 استفاده شود، الگوریتم ناپایدار خواهد شد.


منبع الگوریتمستان

 

[کاربر حذف شده 8031]

پاسخ : اموزش الگوریتم

مرتب‌سازی انتخابی

روش مرتب‌سازی انتخابی (Selection Sort) یکی از روش‌های اولیه مرتب‌سازی بر اساس مقایسه عناصر است. این الگوریتم طی چند مرحله عناصر لیست را به صورت صعودی یا نزولی مرتب می‌کند. به این ترتیب که در هر مرحله با بررسی عناصر نامرتب، بزرگترین (یا کوچکترین) عنصر را پیدا کرده، و به انتهای لیست منتقل می‌کند.

لیست اعداد زیر را در نظر بگیرید، که باید به صورت صعودی (کوچک به بزرگ) مرتب شود:

2 8 4 1 7​

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

1) 2 8 4 1 7 -> 2 7 4 1 8​

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

2) 2 7 4 1 8 -> 2 1 4 7 8​

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

3) 2 1 4 7 8 -> 2 1 4 7 8​

و در مرحله آخر دو عنصر باقیمانده مقایسه می‌شوند:

4) 2 1 4 7 8 -> 1 2 4 7 8​

و به این ترتیب لیست مرتب می‌شود.



پیاده‌سازی مرتب‌سازی انتخابی

الگوریتم مرتب‌سازی انتخابی به زبان برنامه‌نویسی ++C برای مرتب کردن عناصر آرایه‌ای از اعداد صحیح به صورت زیر پیاده‌سازی می‌شود:

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;

}

}

​

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



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

تعداد عناصر لیست را 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​

که از مرتبه ( Θ( n2 است.



ویژگی‌های مرتب‌سازی انتخابی

1- پیچیدگی زمانی اجرای این الگوریتم بر اساس محاسبات فوق در بدترین حالت ( Θ( n2 است. با توجه به قطعه کد نوشته شده، ترتیب عناصر تغییری در عملکرد آن اینجا نمی‌کند. یعنی این الگوریتم برای داده‌های کاملا مرتب، نامرتب تصادفی و مرتب معکوس به یک ترتیب عمل کرده و تمام مقایسه‌های محاسبه شده در رابطه فوق را انجام می‌دهد. بنابراین پیچیدگی این الگوریتم در بهترین حالت و حالت منوسط نیز ( Θ( n2 است.

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

3- در پیاده‌سازی مرتب‌سازی انتخابی به روش فوق، اگر دو عنصر با مقدار بیشینه داشته باشیم، اولی انتخاب شده و به انتهای لیست منتقل می‌شود. در نتیجه ترتیب آنها به هم می‌خورد. بنابراین این پیاده‌سازی روش پایدار نیست. در روش پایدار ترتیب عناصر با مقدار یکسان تغییر نمی‌کند. اما اگر در مقایسه عناصر آرایه به جای > از => استفاده کنید، مرتب‌سازی پایدار خواهد شد.

 

[کاربر حذف شده 8031]

پاسخ : اموزش الگوریتم

مرتب‌سازی حبابی

یکی از روش‌های مرتب‌سازی، روش مرتب‌سازی حبابی (Bubble Sort) است، که به آن روش تعویض استاندارد (Standard Exchange) نیز می‌گویند. این روش شامل چند مرحله است، که در هر مرحله یک عنصر از لیست به طور قطع در محل مناسب خود قرار می‌گیرد.

لیست زیر را در نظر بگیرید، که می‌خواهیم به صورت صعودی (از کوچک به بزرگ) مرتب کنیم:

4 3 8 1 6 2​

عنصر اول را با دومی مقایسه کرده، و در صورتی که اولی بزرگتر باشد، جای آنها را تعویض می‌کنیم:

1 - 1) 4 3 8 1 6 2 -> 3 4 8 1 6 2​

همین کار را با عناصر دوم و سوم انجام می‌دهیم:

1 - 2) 3 4 8 1 6 2 -> 3 4 8 1 6 2​

و همینطور عناصر سوم و چهارم:

1 - 3) 3 4 8 1 6 2 -> 3 4 1 8 6 2​

و الی آخر:

1 - 4) 3 4 1 8 6 2 -> 3 4 1 6 8 2

1 - 5) 3 4 1 6 8 2 -> 3 4 1 6 2 8​

زمانی که به انتهای لیست رسیدیم، بزرگترین عنصر بین داده‌ها به انتهای لیست منتقل شده است.

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

2 - 1) 3 4 1 6 2 8 -> 3 4 1 6 2 8

2 - 2) 3 4 1 6 2 8 -> 3 1 4 6 2 8

2 - 3) 3 1 4 6 2 8 -> 3 1 4 6 2 8

2 - 4) 3 1 4 6 2 8 -> 3 1 4 2 6 8
​

در هر مرحله، طول بازه‌ای که مرتب‌سازی روی آن انجام می‌گیرد، یک واحد کم شده، و در نتیجه تعداد گام‌ها نیز یک گام کمتر می‌شود:

3 - 1) 3 1 4 2 6 8 -> 1 3 4 2 6 8

3 - 2) 1 3 4 2 6 8 -> 1 3 4 2 6 8

3 - 3) 1 3 4 2 6 8 -> 1 3 2 4 6 8



4 - 1) 1 3 2 4 6 8 -> 1 3 2 4 6 8

4 - 2) 1 3 2 4 6 8 -> 1 2 3 4 6 8
​

5 - 1) 1 2 3 4 6 8 -> 1 2 3 4 6 8​

در پایان این مراحل، لیست مرتب شده است.

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



کد پیاده‌سازی مرتب‌سازی حبابی

این الگوریتم را به زبان برنامه‌نویسی ++C - برای آرایه‌ای از اعداد صحیح - می‌توان به صورت زیر پیاده‌سازی کرد:

void bubble_sort_1( int arr[ ], int n )

{

int i, j, t;

for( i = n - 2 ; i >= 0 ; i-- )

{

for( j = 0 ; j <= i ; j++ )

{

if( arr[ j ] > arr[ j + 1 ] )

{

t = arr[ j ];

arr[ j ] = arr[ j + 1 ];

arr[ j + 1 ] = t;

}

}

}

}
​

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



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

فرض کنیم لیستی با n عنصر با روش مرتب‌سازی حبابی مرتب می‌شوند. عمل اصلی روش‌های مرتب‌سازی مبتنی بر مقایسه، مقایسه‌ها هستند. در مرحله اول، n - 1 مقایسه صورت می‌گیرد، تا بزرگترین عنصر به انتهای لیست منتقل شود. در مرحله دوم، n - 2 مقایسه، و به همین ترتیب، در مرحله iام ( i < n ) تعداد n - i مقایسه صورت می‌گیرد. این تعداد را می‌توان از کد برنامه‌نویسی ذکر شده فوق هم استخراج کرد. پس تعداد کل مقایسه‌ها برای مرتب کردن n عنصر برابر است با:

T( n ) = ( n - 1 ) + ( n - 2 ) + ( n - 3 ) + ... + 2 + 1 = n ( n - 1 ) / 2​

چنین عبارتی از مرتبه ( Θ( n2 است.



بهینه کردن الگوریتم مرتب‌سازی حبابی

قطعه کد فوق برای تمامی حالات چینش عناصر لیست به یک ترتیب عمل می‌کند. یعنی حتی اگر عناصر از قبل مرتب باشند، تمامی مقایسه‌ها - بدون جابجا شدن عنصری - انجام می‌شود. قطعه کد فوق در بهترین حالت، بدترین حالت، و حالت متوسط از مرتبه ( Θ( n2 خواهد بود.

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

void bubble_sort_2( int arr[ ], int n )

{

int i, j, t, c;

for( i = n - 2 ; i >= 0 ; i-- )

{

c = 0;

for( j = 0 ; j <= i ; j++ )

{

if( arr[ j ] > arr[ j + 1 ] )

{

t = arr[ j ];

arr[ j ] = arr[ j + 1 ];

arr[ j + 1 ] = t;

c++;

}

}

if( c == 0 )

{

break;

}

}

}

​

مقدار متغیر c قبل از شروع هر مرحله صفر شده، و با هر جابجایی یک واحد به آن اضافه می‌شود. در پایان هر مرحله، این متغیر تعداد جابجایی‌های عناصر در آن مرحله را نشان می‌دهد. بنابراین، اگر مقدار آن در پایان مرحله صفر باشد، یعنی هیچگونه جابجایی در لیست صورت نگرفته، و می‌توان نتیجه گرفت لیست مرتب است (چرا؟).

چنین کدی مرتبه زمانی اجرای الگوریتم را در بهترین حالت به ( Θ( n تقلیل می‌دهد. چرا که اگر لیست از همان ابتدا مرتب باشد، با تمام شدن اولین مرحله (با n - 1 مقایسه) و بررسی مقدار متغیر c، مرتب بودن لیست مشخص شده، و ادامه روند مرتب‌سازی متوقف می‌شود.



ویژگی‌های مرتب‌سازی حبابی

1- همانگونه که بحث شد، پیچیدگی زمانی اجرای این الگوریتم در بدترین حالت و حالت متوسط از مرتبه ( Θ( n2 است. پیچیدگی زمانی بهترین حالت، با تابع bubble_sort_1 از مرتبه ( Θ( n2، و با تابع bubble_sort_2 از مرتبه ( Θ( n است.

2- مرتب‌سازی حبابی یک روش مرتب‌سازی درجا است. یعنی نیاز به فضای کمکی نداشته، و با جابجا کردن عناصر در داخل خود لیست، آنها را مرتب می‌کند.

3- مرتب‌سازی حبابی - با پیاده‌سازی به یکی از روش‌های فوق - یک روش مرتب‌سازی پایدار است. یعنی در حین مرتب‌سازی ترتیب عناصری که مقدار یکسانی دارند تغییر نمی‌کند. اگر در قطعه‌کدهای فوق، در مقایسه عناصر آرایه به جای < از =< استفاده می‌کردیم، مرتب‌سازی ناپایدار می‌شد. چرا که عناصری با مقادیر یکسان را نیز جابجا کرده، و ترتیب آنها را به هم می‌زد.

منبع : الگوریتمستان

 

[hanifi135]

پاسخ : طراحی الگوریتم

خیلی عالی بود .
فقط اگه تونستی الگوریتم های محاسبات ریاضی رو هم یه توضیحی در بارشمون بده.

 

[ErfanDK]

پاسخ : طراحی الگوریتم

توی الگوریتم Quick Sort اگه عنصر Pivot رو به صورت رندوم بگیریم چه تغییری تو زمان اجرا می ذاره؟ اصلا تاثیری می ذاره؟

 

[sjazayeri]

پاسخ : طراحی الگوریتم

نه, شما چه محور رو رندم انتخاب کنین چه به یک روش دیگه حالت میانگین O(n lg n) هست و بدترین حالت O(n^2) اما توی تحلیل حالت میانگین(در روشی که محور رو رندم انتخاب نمیکنیم) این مساله فرض میشه که تمام جایگشت های ورودی به یک اندازه ممکن هستن, اما معمولا در واقیعت این اتفاق نمی افته, بنابراین با رندم انتخاب کردن محور این خاصیت رو بدست میاریم.(میشه گفت رندم انتخاب کردن محور مثل این میمونه که اول آرایه رو به یک جایگشت تصادفی تغییر بدیم).

 

[daneshvar.amrollahi]

پاسخ : طراحی الگوریتم

کسی الگوریتمی به جز تابع بازگشتی برای نوشتن زیر مجموعه های n عضوی یک مجموعه رو داره؟ میدونم که به n تا حلقه for تو در تو نیازمندیم اما این الگوریتم فقط با استفاده از توابع بازگشتی ممکنه. کسی الگوریتمی میتونه بگه؟
اگر هم پیدا نکرد الگوریتم بازگشتیش رو بگه که چجوری باید بنویسم؟

 

[Dark Eagle]

پاسخ : طراحی الگوریتم

بازگشتیش : یه عضو رو میزاریم کنار بقی رو تموم حالتاشونو پیدا میکنیم .... بعد اون عضو رو به آخرش اضافه میکنیم.
بعد جایه این عضو که گذاشتیم کنار رو با یکی دیگه عوض میکنیم تا همه عضو هارو یه باز گذاشته باشیم کنار ...

بازگشتیش 2:باسه n-1 همه جایگشتارو پیدا میکنیم بعد n رو همه جاش میزاریم....

غیر بازگشتیش : با گراف و dfs و bfs (صفشون) میشه یه کد نوشت ولی هم کد زنیش سخته هم الگوریتمش ... یه سری if میخواد.

^-^

 

[rezaezio]

پاسخ : طراحی الگوریتم

غیر بازگشتیش : با گراف و dfs و bfs (صفشون) میشه یه کد نوشت ولی هم کد زنیش سخته هم الگوریتمش ... یه سری if میخواد.

این که گفتی رو بزن ، جایزه بگیر !

غیر بازگشتیش ،، صفحه 172 کتاب مسئله های الگوریتمی دکتر قدسی نوشته شده . این قدر که فک می کنی هم سخت نیست .

 

[sjazayeri]

پاسخ : طراحی الگوریتم

یه آرایه به اندازه مجموعت بگیر, n تا سمت راستشو یک کن, بعد توی while پشت سر هم next_permutation بزن روش.

 

[tiberium]

پاسخ : طراحی الگوریتم

کسی الگوریتمی به جز تابع بازگشتی برای نوشتن زیر مجموعه های n عضوی یک مجموعه رو داره؟ میدونم که به n تا حلقه for تو در تو نیازمندیم اما این الگوریتم فقط با استفاده از توابع بازگشتی ممکنه. کسی الگوریتمی میتونه بگه؟
اگر هم پیدا نکرد الگوریتم بازگشتیش رو بگه که چجوری باید بنویسم؟

من یه راه دیگه اومد به ذهنم برا این.
ببین یه جمع باینری باید بسازی برا اعداد باینری
بعد یه string درست کن که n تا ۰ داره
مثلا به ازای n=7
۰۰۰۰۰۰۰۰
بعد هی با ۱ جمع کن
۰۰۰۰۰۰۱
۰۰۰۰۰۱۰
۰۰۰۰۰۱۱
همینجوری باید با یک جمع کنی(برا جمع String با ۱ باید خودت یه تابع بنویسی.یا اینکه میتونی تبدیل اینا کنی اگر با جاوا میزدی(با بقیه رو اطلاع ندارم))
بعد هردفعه رو این String میری هر indexi ‌که ۱ بودو چاپ می کنی میشه همه زیر مجموعه ها

ویرایش:‌ انگار راه من همین راه نفر بالایی هست