برنامه مرتب سازی حبابی (Bubble sort) در زبان برنامه نویسی C , ++C
برنامه مرتب سازی حبابی (Bubble sort) در زبان برنامه نویسی ++ C , C
یکی از روشهای مرتبسازی، روش مرتبسازی حبابی (Bubble Sort) است که به آن روش تعویض استاندارد (Standard Exchange) نیز میگویند. این روش شامل چند مرحله است که در هر مرحله یک عنصر از لیست به طور قطع در محل مناسب خود قرار میگیرد.
لیست زیر را در نظر بگیرید که میخواهیم به صورت صعودی (از کوچک به بزرگ) مرتب کنیم:
۴ ۳ ۸ ۱ ۶ ۲
عنصر اول را با دومی مقایسه کرده و در صورتی که اولی بزرگتر باشد، جای آنها را تعویض میکنیم:
۱ – ۱) ۴ ۳ ۸ ۱ ۶ ۲ → ۳ ۴ ۸ ۱ ۶ ۲
همین کار را با عناصر دوم و سوم انجام میدهیم:
۱ – ۲) ۳ ۴ ۸ ۱ ۶ ۲ → ۳ ۴ ۸ ۱ ۶ ۲
و همینطور عناصر سوم و چهارم:
۱ – ۳) ۳ ۴ ۸ ۱ ۶ ۲ → ۳ ۴ ۱ ۸ ۶ ۲
و الی آخر:
۱ – ۴) ۳ ۴ ۱ ۸ ۶ ۲ → ۳ ۴ ۱ ۶ ۸ ۲
۱ – ۵) ۳ ۴ ۱ ۶ ۸ ۲ → ۳ ۴ ۱ ۶ ۲ ۸
زمانی که به انتهای لیست رسیدیم، بزرگترین عنصر بین دادهها به انتهای لیست منتقل شده است.
در مرحلهی بعد، مجددا از ابتدا شروع کرده و تا انتها ادامه میدهیم. اما با توجه به این که به طور قطع عنصر nام در جای اصلی خود قرار دارد، تا عنصر (n – 1)ام پیش میرویم. در پایان این مرحله، بزرگترین عدد در لیست نامرتب باقیمانده، به انتهای آن منتقل میشود که دومین عدد از نظر بزرگی در کل لیست است:
۲ – ۱) ۳ ۴ ۱ ۶ ۲ ۸ → ۳ ۴ ۱ ۶ ۲ ۸
۲ – ۲) ۳ ۴ ۱ ۶ ۲ ۸ → ۳ ۱ ۴ ۶ ۲ ۸
۲ – ۳) ۳ ۱ ۴ ۶ ۲ ۸ → ۳ ۱ ۴ ۶ ۲ ۸
۲ – ۴) ۳ ۱ ۴ ۶ ۲ ۸ → ۳ ۱ ۴ ۲ ۶ ۸
در هر مرحله، طول بازهای که مرتبسازی روی آن انجام میگیرد، یک واحد کم شده و در نتیجه تعداد گامها نیز یک گام کمتر میشود:
۳ – ۱) ۳ ۱ ۴ ۲ ۶ ۸ → ۱ ۳ ۴ ۲ ۶ ۸
۳ – ۲) ۱ ۳ ۴ ۲ ۶ ۸ → ۱ ۳ ۴ ۲ ۶ ۸
۳ – ۳) ۱ ۳ ۴ ۲ ۶ ۸ → ۱ ۳ ۲ ۴ ۶ ۸
۴ – ۱) ۱ ۳ ۲ ۴ ۶ ۸ → ۱ ۳ ۲ ۴ ۶ ۸
۴ – ۲) ۱ ۳ ۲ ۴ ۶ ۸ → ۱ ۲ ۳ ۴ ۶ ۸
۵ – ۱) ۱ ۲ ۳ ۴ ۶ ۸ → ۱ ۲ ۳ ۴ ۶ ۸
در پایان این مراحل، لیست مرتب شده است.
در مراحل مختلف، عناصر بزرگ رفته رفته به انتهای لیست و محل اصلی خود حرکت میکنند. مانند حباب آبی که از درون آب به سمت سطح آن حرکت میکند. به همین دلیل این روش مرتبسازی را مرتبسازی حبابی نامیدهاند.
پیادهسازی مرتبسازی حبابی در ++C
سورس مرتبسازی حبابی به زبان c++ به شرح زیر است:
#include <iostream>
int main()
{
int len=10;
int a[len],i,j,temp;
for(i=0;i<len;i++)
{
std::cin>>a[i]; // دریافت اعضای آرایه (لیست مورد نظر) برای مرتبسازی
}
for(i=len-2;i>=0;i–)
{
for(j=0;j<=i;j++)
{
if(a[j]>a[j+1]) //مقایسهٔ تک به تک هر عضو آرایه با عضو کناری
{
temp=a[j]; //و جابهجایی اعضا یا یکدیگر در صورت برقراری شرط
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
for(i=0;i<len;i++)
{
std::cout<<a[i]; //چاپ اعضا
}
return 0;
}
1 |
پیادهسازی مرتبسازی حبابی در C
این سورس یک عدد گرفته و به تعداد همان عدد از ورودی دریافت میکند و آنها را با روش Bubble sort مرتب میکند.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
<span style="font-size: 12pt;"><span class="cp" style="color: #ff9900;"># include<cstdio> </span><span style="color: #ff9900;"><span class="cp"># include</span><span class="cpf"><cstdlib></span> </span> <span class="c1">//--------------------------------------------</span> <span class="kt">void</span> <span class="nf" style="color: #3366ff;">read_list</span><span class="p">(</span><span class="kt">int</span> <span class="n">a</span><span class="p">[],</span><span class="kt">int</span> <span class="n">n</span><span class="p">){</span> <span class="kt" style="color: #ff6600;">int</span> <span class="n">i</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="n">i</span><span class="o"><</span><span class="n">n</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">){</span> <span class="n">printf</span><span class="p">(</span><span style="color: #ff0000;"><span class="s">"</span><span class="se">\n\n\t</span><span class="s"> ENTER THE ELEMENT [%d] :: "</span></span><span class="p">,</span><span class="n">i</span><span class="p">);</span> <span class="n">scanf</span><span class="p">(</span><span class="s">"%d"</span><span class="p">,</span><span class="o">&</span><span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">]);</span> <span class="p">}</span> <span class="p">}</span> <span class="c1">//--------------------------------------------</span> <span class="kt">void</span> <span class="nf" style="color: #3366ff;">print_list</span><span class="p">(</span><span class="kt">int</span> <span class="n">a</span><span class="p">[],</span><span class="kt">int</span> <span class="n">n</span><span class="p">){</span> <span class="kt" style="color: #ff6600;">int</span> <span class="n">i</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="n">i</span><span class="o"><</span><span class="n">n</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">printf</span><span class="p">(</span><span class="s">"</span><span class="se">\t</span><span class="s">%d"</span><span class="p">,</span><span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">]);</span> <span class="p">}</span> <span class="c1">//--------------------------------------------</span> <span class="kt">void</span> <span class="nf" style="color: #3366ff;">bubble_sort</span><span class="p">(</span><span class="kt">int</span> <span class="n">a</span><span class="p">[],</span><span class="kt">int</span> <span class="n">n</span><span class="p">){</span> <span class="kt" style="color: #ff6600;">int</span> <span class="n">i</span><span class="p">,</span><span class="n">j</span><span class="p">,</span><span class="n">temp</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="n">i</span><span class="o"><</span><span class="n">n</span><span class="o">-</span><span class="mi">1</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">){</span> <span class="k">for</span><span class="p">(</span><span class="n">j</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="n">j</span><span class="o"><</span><span class="n">n</span><span class="o">-</span><span class="mi">1</span><span class="p">;</span><span class="n">j</span><span class="o">++</span><span class="p">)</span> <span class="k">if</span><span class="p">(</span><span class="n">a</span><span class="p">[</span><span class="n">j</span><span class="p">]</span><span class="o">></span><span class="n">a</span><span class="p">[</span><span class="n">j</span><span class="o">+</span><span class="mi">1</span><span class="p">]){</span> <span class="n">temp</span><span class="o">=</span><span class="n">a</span><span class="p">[</span><span class="n">j</span><span class="p">];</span> <span class="n">a</span><span class="p">[</span><span class="n">j</span><span class="p">]</span><span class="o">=</span><span class="n">a</span><span class="p">[</span><span class="n">j</span><span class="o">+</span><span class="mi">1</span><span class="p">];</span> <span class="n">a</span><span class="p">[</span><span class="n">j</span><span class="o">+</span><span class="mi">1</span><span class="p">]</span><span class="o">=</span><span class="n">temp</span><span class="p">;</span> <span class="p">}</span> <span class="n">printf</span><span class="p">(</span><span style="color: #ff0000;"><span class="s">"</span><span class="se">\n\n\t</span><span class="s"> PASS %d :: "</span></span><span class="p">,</span><span class="n">i</span><span class="p">);</span> <span class="n">print_list</span><span class="p">(</span><span class="n">a</span><span class="p">,</span><span class="n">n</span><span class="p">);</span> <span class="p">}</span> <span class="p">}</span> <span class="c1">//----------------------------------------------</span> <span class="kt" style="color: #ff6600;">int</span> <span class="nf" style="color: #3366ff;">main</span><span class="p">(){</span> <span class="kt" style="color: #ff6600;">int</span> <span class="n">a</span><span class="p">[</span><span class="mi">20</span><span class="p">],</span><span class="n">n</span><span class="p">;</span> <span class="n">printf</span><span class="p">(</span><span style="color: #ff0000;"><span class="s">"</span><span class="se">\n\n\t</span><span class="s"> ENTER THE ARRAY LENGTH :: "</span></span><span class="p">);</span> <span class="n">scanf</span><span class="p">(</span><span class="s">"%d"</span><span class="p">,</span><span class="o">&</span><span class="n">n</span><span class="p">);</span> <span class="n">read_list</span><span class="p">(</span><span class="n">a</span><span class="p">,</span><span class="n">n</span><span class="p">);</span> <span class="n">printf</span><span class="p">(</span><span style="color: #ff0000;"><span class="s">"</span><span class="se">\n\n\t</span><span class="s"> THE ARRAY ELEMENTS ARE AS FOLLOWS :: "</span></span><span class="p">);</span> <span class="n">print_list</span><span class="p">(</span><span class="n">a</span><span class="p">,</span><span class="n">n</span><span class="p">);</span> <span class="n">bubble_sort</span><span class="p">(</span><span class="n">a</span><span class="p">,</span><span class="n">n</span><span class="p">);</span> <span class="n">printf</span><span class="p">(</span><span style="color: #ff0000;"><span class="s">"</span><span class="se">\n\n\t</span><span class="s"> THE SORTED LIST IS :: "</span></span><span class="p">);</span> <span class="n">print_list</span><span class="p">(</span><span class="n">a</span><span class="p">,</span><span class="n">n</span><span class="p">);</span> <span class="k">return</span> <span class="mi">0</span><span class="p">;</span> <span class="p">}</span> </span><span class="c1"><span style="font-size: 12pt;">//--------------------------------------</span> </span> |
پیچیدگی زمانی مرتبسازی حبابی
فرض کنیم لیستی با n عنصر با روش مرتبسازی حبابی مرتب میشوند. عمل اصلی روشهای مرتبسازی مبتنی بر مقایسه، مقایسهها هستند. در مرحلهی اول، n – 1 مقایسه صورت میگیرد، تا بزرگترین عنصر به انتهای لیست منتقل شود. در مرحلهی دوم، n – 2 مقایسه و به همین ترتیب، در مرحلهی iام (i < n) تعداد n – i مقایسه صورت میگیرد. این تعداد را میتوان از کد برنامهنویسی ذکر شدهی فوق هم استخراج کرد. پس تعداد کل مقایسهها برای مرتب کردن nعنصر برابر است با:
1 |
<span class="c1"> </span> |
بدترین حالت
این الگوریتم در بدترین حالت از مرتبهٔ ( Θ(n۲ است. چون در بدترین حالت هر عنصر باید n-1 بار فهرست را بپیماید.
بهترین حالت
بهترین حالت این است که فهرست مرتب شدهباشد که در این حالت الگوریتم از مرتبه (O(n است.
1 |
فرستادن دیدگاه
نوشتههای تازه
- دانلود پیاده سازی رمزنگاری اثر انگشت
- دانلود پیاده سازی مقاله رمزنگاری چندگانه تصویر بر اساس جایگشت عناصر تصویر در متلب
- دانلود ترجمه مقاله رمزنگاری تصویر رنگی مبتنی بر سیستم فوق آشوب
- دانلود پیاده سازی مقاله رمزنگاری تصویر مبتنی بر دنباله های DNA و چندین نگاشت آشوب یک بعدی بهبود یافته در متلب
- رمزنگاری تصویر رنگی مبتنی بر ترکیب سیستم آشوب و دنباله های DNA
- دانلود ترجمه مقاله الگوریتم رمزنگاری تصویر مبتنی بر آشوب با استفاده از عملیات دنباله DNA
- دانلود ترجمه مقاله یک روش جدید رمزنگاری تصویر مبتنی بر اغتشاش و انتشار با استفاده از اتوماتای سلولی و دنباله DNA
- پیاده سازی مقاله رمزنگاری تصویر رنگی مبتنی بر سیستم های فوق آشوب و اتوماتی سلولی
- پیاده سازی مقاله رمزنگاری تصویر مبتنی بر دنباله های DNA و توابع آشوب
- دانلود سورس پیاده سازی مقاله رمزنگاری تصویر رنگی مبتنی بر عملگر های DNA و سیستم فوق آشوب