Borna66
07-08-2012, 11:30 PM
یکی از روش‌های مرتب‌سازی، روش مرتب‌سازی حبابی (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- مرتب‌سازی حبابی - با پیاده‌سازی به یکی از روش‌های فوق - یک روش مرتب‌سازی پایدار است. یعنی در حین مرتب‌سازی ترتیب عناصری که مقدار یکسانی دارند تغییر نمی‌کند. اگر در قطعه‌کدهای فوق، در مقایسه عناصر آرایه به جای < از =< استفاده می‌کردیم، مرتب‌سازی ناپایدار می‌شد. چرا که عناصری با مقادیر یکسان را نیز جابجا کرده، و ترتیب آنها را به هم می‌زد.
لیست زیر را در نظر بگیرید، که می‌خواهیم به صورت صعودی (از کوچک به بزرگ) مرتب کنیم:
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- مرتب‌سازی حبابی - با پیاده‌سازی به یکی از روش‌های فوق - یک روش مرتب‌سازی پایدار است. یعنی در حین مرتب‌سازی ترتیب عناصری که مقدار یکسانی دارند تغییر نمی‌کند. اگر در قطعه‌کدهای فوق، در مقایسه عناصر آرایه به جای < از =< استفاده می‌کردیم، مرتب‌سازی ناپایدار می‌شد. چرا که عناصری با مقادیر یکسان را نیز جابجا کرده، و ترتیب آنها را به هم می‌زد.