روشهای مرتب سازی در C++
روش مرتب سازی حبابی:
در این روش ابتدا داده اول با داده دوم مقایسه میشود، اگر داده اول بزرگتر باشد با داده دوم جابجا میشود.
به همین ترتیب داده دوم با داده سوم و سومی با چهارمی و الی آخر مقایسه میشوند که در صورت نیاز جابجایی صورت میگیرد.
هنگامی که به انتهای لیست برسیم بزرگترین داده در آخر لیست است.
روی داده های باقیمانده این عمل را تکرار میکنیم تا در نهایت لیست مرتب شود.
در صورتی که در یک دور جا به جایی صورت نگیرد به معنای آن است که لیست مرتب شده است و نیازی به ادامه کار نیست.
مثال:
برنامه مرتب سازی در c++ بنویسید که 100 عدد را از ورودی دریافت کند و سپس به روش حبابی آنرا مرتب سازی کند؟
void main()
{
int a[100],i,j,sw=1,t;
for( i=0; i<100; i++)
cin>> a[i];
for( i=0; i<99 && sw ;i++)
{
sw=0;
for( j=0; j<(99-i); j++)
{
if( a[j] > a[j+1])
{
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
sw=1;
}
}
}
}
روش مرتب سازی انتخابی :
در این روش ابتدا کوچکدرین داده لیست پیدار میشود و جای آن با داده اول عوض میشود سپس در داده های باقیمانده کوچکتر داده پیدا شده جایش با داده دوم عوض میشود.
این عملیات را تکرار میکنیم تا در نهایت لیست مرتب شود.
مثال:
برنامه ای در زبان برنامه نویسی سی پلاس پلاس بنویسید که 100 عدد را دریافت کند و آنها را به روش انتخابی مرتب کند؟
void main()
{
int a[100],i,j,h;
for( i=0; i<100; i++)
cin>> a[i];
for( i=0; i<100; i++)
for( j=i+1; j<100; j++)
if(a[j] > a[i])
{
h=a[i];
a[i]=a[j];
a[j]=h;
}
}
روش مرتب سازی درجی:
در این روش همزمان با ورود داده ها جای آنها را پیدا میکنیم
مثال:
برنامه ای در زبان سی بنویسید که 100 عدد را از ورودی دریافت و آنها را به روش درجی مرتب کند؟
void main()
{
int a[100], i , j , k , h;
for( i=0; i<100; i++)
{
cin>> a[i];
for( j=0; j<i; j++)
if( a[i] >= a[j] )
{
h=a[i];
for( k=i; k>j; k--)
a[k]=a[k-1];
a[j] = h;
break;
}
}
}
درجه مرتبه زمانی تمام الگوریتمهای بالا 2 است یعنی دارای دو حلقه تو در تو است.
اما با این حیث در بدترین حالت الگوریتم مرتب سازی حبابی تا خط آخر انجام میگیرد.
بنابراین در شرایط مختلف اکثرا الگوریتم حبابی سریع تر از سایر الگوریتمهای دیگر به پایان می رسد.
از اینرو در همه جا بیشتر از الگوریتم حبابی استفاده میشود.
علت اینکه الگوریتم حبابی زودتر از الگوریتمهای ذیگر به پایان میرسد وجود عنصر کنترلی شرط مرتبسازی است.
در مثال برنامه مرتبسازی متغییر sw شرط کنترل مرتب سازی حبابی است.
اگر مقدار sw=0 باقی بماند حلقه For متوقف شده و برنامه ادامه پیدا نمیکند.
