برنامه نویسی - سورس - پروژه // سی // سی پلاس پلاس

برنامه مرتب‌ سازی حبابی (Bubble sort) در زبان برنامه نویسی C , ++C

نوشته شده توسط donyafile Comments

برنامه مرتب‌ سازی حبابی (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;

}

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

این سورس یک عدد گرفته و به تعداد همان عدد از ورودی دریافت می‌کند و آن‌ها را با روش Bubble sort مرتب می‌کند.

<span style="font-size: 12pt;"><span class="cp" style="color: #ff9900;"># include&lt;cstdio&gt;
</span><span style="color: #ff9900;"><span class="cp"># include</span><span class="cpf">&lt;cstdlib&gt;</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">&lt;</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">&amp;</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">&lt;</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">&lt;</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">&lt;</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">&gt;</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">&amp;</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>

# include<cstdio>

# include<cstdlib>

//--------------------------------------------

void read_list(int a[],int n){

int i;

for(i=0;i<n;i++){

printf("\n\n\t ENTER THE ELEMENT [%d] :: ",i);

scanf("%d",&a[i]);

}

//--------------------------------------------

void print_list(int a[],int n){

int i;

printf("\t%d",a[i]);

}

//--------------------------------------------

void bubble_sort(int a[],int n){

int i,j,temp;

for(i=0;i<n-1;i++){

for(j=0;j<n-1;j++)

if(a[j]>a[j+1]){

temp=a[j];

a[j]=a[j+1];

a[j+1]=temp;

}

printf("\n\n\t PASS %d :: ",i);

print_list(a,n);

}

//----------------------------------------------

int main(){

int a[20],n;

printf("\n\n\t ENTER THE ARRAY LENGTH :: ");

scanf("%d",&n);

read_list(a,n);

printf("\n\n\t THE ARRAY ELEMENTS ARE AS FOLLOWS :: ");

print_list(a,n);

bubble_sort(a,n);

printf("\n\n\t THE SORTED LIST IS :: ");

print_list(a,n);

return 0;

}

//--------------------------------------

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

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