آموزش زبان برنامه نویسی سی پلاس پلاس

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

برای مشاهده متن کامل بخش پنجم آموزش زبان برنامه نویسی سی پلاس پلاس، به ادامه مطلب مراجه نمایید.

آموزش زبان برنامه نویسی سی پلاس پلاس

بخش پنجم

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

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

void  bubbleSort(int  A[], int n) {
   int  i, Sw;
   do {
     Sw = 0;
     n --;
     for  (i=0; i<n;  i++)
         if  (A[i] > A[i+1]) {
             swap(A[i], A[i+1]) ;
            Sw = 1;
         }
   } while (Sw) ;
}

در تابع فوق از متغیر Sw برای تشخیص لزوم ادامه کار استفاده شده است. در ابتدای حلقه do این متغیر برابر 0 قرار داده شده است که به معنای عدم نیاز به ادامه حلقه است. اما در داخل حلقه for، هر عنصر با عنصر بعدی خود مقایسه می گردد و درصورت نیاز به جابجایی، این کار با استفاده از تابع swap انجام گرفته و علاوه براین مقدار متغیر Sw نیز برابر 1 می شود که به معنای نیاز به ادامه حلقه است. در پایان حلقه do-while ، مقدار Sw بررسی می شود و چنانچه برابر درست ارزیابی شد (به یاد دارید که در زبان C هر عدد غیر صفر از جمله یک برابر درست ارزشیابی می شود)، اجرای حلقه ادامه می یابد. نکته ای دیگری که لازم است به آن توجه کنید، کم کردن از اندازه آرایه در هر بار اجرای حلقه است.دلیل نامگذاری این روش بنام حبابی آن است که همانطور که حبابهای سبک وزن در یک ظرف آب درحال جوش به سطح آب می آیند، در این روش نیز داده های کوچک در هر مرحله یک خانه بالاتر می آیند تا به بالای آرایه برسند.

حال برای آشنایی بیشتر با این الگوریتم به این مثال که به زبان سی پلاس پلاس نوشته شده توجه نمایید.

برنامه ای بنویسید که تعدادی عدد را گرفته و آن ها را به صورت نزولی مرتب نماید.

#include<conio.h>
#include<iostream.h>
void swap(int &a,int &b){
int temp;
temp=a;
a=b;
b=temp;
}
void bubbleSort(int a[],int n){
int i,sw;
do{
sw=0;
n--;
for(i=0;i<n;i++)
if(a[i]>a[i+1]){
swap(a[i],a[i+1]);
sw=1;
}
}while(sw);
}
void main(){
int arr[100],n;
cout<<"please enter the number of the numbers:"<<endl;
cin>>n;
cout<<"please enter the numbers: "<<endl;
for(int i=0;i<n;i++)
cin>>arr[i];
bubbleSort(arr,n);
for(int i=0;i<n;i++)
cout<<arr[i]<<" ";
getch();
}

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

برای کسب اطلاعات بیشتر درباره زبان برنامه نویسی سی پلاس پلاس می توانید به cplusplus و  tutorialspoint مراجعه نمایید.

همچنین برای کسب اطلاعات  بیشتر درباره الگوریتم مرتب سازی حبابی می توایند به wikipedia مراجعه نمایید.

در شماره بعدی به الگوریتم های موجود برای جست و جو در آرایه ها میپردازیم.