مرتب سازی
فرض کنید که به شما آرایه ای بدهند و از شما بخواهند که بزرگترین عنصر این آرایه را در خروجی نمایش دهید.
برای این کار برنامه ای خواهید نوشت که تنها عنصر ماکزیمم را به شما بدهد.
حال فرض کنید که از شما بپرسند عنصر 5 ام این آرایه به ترتیب بزرگ به کوچک چیست؟ آن وقت چکار خواهید کرد؟
برای حل این قبیل مسائل باید کل آرایه را مرتب کنیم!
الگوریتمهای مختلفی تا امروز برای مرتب سازی آرایه ها ارائه شده است. اما از ساده ترین آنها می توان به سه نوع مرتب سازی زیر اشاره نمود:
1- مرتب سازی انتخابی یا selection sort
2- مرتب سازی درجی یا insertion sort
3- مرتب سازی حبابی یا bubble sort
در ادامه الگوریتم مرتب سازی هر کدام از این روشها توضیح داده خواهند شد.
1- مرتب سازی انتخابی یا Selection sort
در این نوع مرتب سازی از اولین خانه آرایه شروع می کنیم و این خانه را با خانه های بعد از خودش تا آخر آرایه، یکی یکی مقایسه می کنیم و هر جا که مقدار خانه ای از خانه ی اولی بیشتر بود مقادیر این دو خانه را جا به جا می کنیم.
مثلا خانه ی سوم هستیم و خانه های صفرم تا دوم را مرتب کرده ایم. خانه ی سوم را با خانه های چهارم تا آخر آرایه یکی یکی مقایسه میکنیم. حال اگر خانه ی هفتم مقداری بیشتر از خانه ی سوم داشت مقدار این دو خانه را همان جا، جا به جا می کنیم.
بعد از آن دوباره خانه ی سوم را( که الان مقدارش عوض شده است) با خانه های هشتم و تا آخر آرایه مقایسه می کنیم و این کار را تا آخر ادامه میدهیم . در انتها خانه ی سوم با بزرگترین مقداری که در خانه های سوم تا آخر آرایه وجود داشته است، پر شده است.
این کار را برای تمام خانه های آرایه( غیر از آخرین خانه که به مقایسه ای احتیاج ندارد) انجام می دهیم.
در اشکال زیر مراحل این کار بخوبی نشان داده شده است:
برنامه ی این مرتب سازی در زیر آمده است:
#include <conio.h> #include <iostream> using namespace std; int main() { int n; cin>>n; int a[n]; for(int i=0;i<n;i++) { a[i]=rand()%50; } for(int i=0;i<n;i++) { cout<<a[i]<<" "; } cout<<endl; for(int i=0;i<n-1;i++) { for(int j=i+1;j<n;j++) { if(a[i]<a[j]) { int temp=a[i]; a[i]=a[j]; a[j]=temp; } } } for(int i=0;i<n;i++) { cout<<a[i]<<" "; } getch(); return 0; }
2- مرتب سازی درجی یا Insertion sort
#include <conio.h> #include <iostream.h> main() { int n; cin>>n; int a[n]; for(int i=0;i<n;i++) { a[i]=rand()%50; } for(int i=0;i<n;i++) //namayesh { cout<<a[i]<<" "; } cout<<endl; for(int i=1;i<n;i++) //sort { int j; int key=a[i]; for(j=i-1;j>=0;j--) { if(key>a[j]) { a[j+1]=a[j]; } else break; } a[j+1]=key; } for(int i=0;i<n;i++) //namayesh { cout<<a[i]<<" "; } getch(); }
3- مرتب سازی حبابی یا Bubble sort
#include <conio.h> #include <iostream.h> main() { int n; cin>>n; int a[n]; for(int i=0;i<n;i++) { a[i]=rand()%50; } for(int i=0;i<n;i++) //namayesh { cout<<a[i]<<" "; } cout<<endl; for(int i=0;i<n;i++) //sort { for(int j=0;j<n-1;j++) { if(a[j+1]>a[j]) { int temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; } } } for(int i=0;i<n;i++) //namayesh { cout<<a[i]<<" "; } getch(); }