مرتب سازی

فرض کنید که به شما آرایه ای بدهند و از شما بخواهند که بزرگترین عنصر این آرایه را در خروجی نمایش دهید. 

برای این کار برنامه ای خواهید نوشت که تنها عنصر ماکزیمم را به شما بدهد. 

حال فرض کنید که از شما بپرسند عنصر 5 ام این آرایه به ترتیب بزرگ به کوچک چیست؟ آن وقت چکار خواهید کرد؟

برای حل این قبیل مسائل باید کل آرایه را مرتب کنیم!

الگوریتمهای مختلفی تا امروز برای مرتب سازی آرایه ها ارائه شده است. اما از ساده ترین آنها می توان به سه نوع مرتب سازی زیر اشاره نمود:

1- مرتب سازی انتخابی یا selection sort

2- مرتب سازی درجی یا insertion sort

3- مرتب سازی حبابی یا bubble sort

در ادامه الگوریتم مرتب سازی هر کدام از این روشها توضیح داده خواهند شد. 

حلقه ی تو در تو تمرینهای پیچیده تر

ادامه ی تمرینها تا حدودی پیچیده تر است. اما لازم است آنها را به صورت کامل یاد بگیرید! 

7- برنامه ای بنویسید که شکل زیر را نمایش دهد: 

*********

 *******

   *****

    ***

      *

برای تحلیل این سوال باید توجه کنیم که 5 خط داریم و در خط صفرم، صفر فاصله و 9 ستاره، در خط یکم، یک فاصله و 7 ستاره، در خط دوم، دو فاصله و 5 ستاره، در خط سوم، سه فاصله و 3 ستاره و در خط چهارم ، چهار فاصله و یک ستاره داریم. 

پس واضح است که حلقه ی بیرونی که تعداد خطوط را نشان میدهد 5 بار تکرار میشود. اما حلقه های درونی( برای فاصله ها و ستاره ها) را چه جور تفسیر کنیم؟

حلقه ی درونی اول که برای رسم فاصله هاست، به تعداد i بار تکرار خواهد شد. ( کافی است به توضیحات بالا کمی توجه کنیم) 

حلقه ی درونی دوم که برای رسم ستاره هاست را می توان به صورت روبه رو با استفاده از یک متغیر کمکی نوشت. به این صورت که متغیر a اول 9 باشد و هر بار 2 تا از آن کم شده و در حلقه ی درونی دوم هر بار a تا ستاره رسم بشود. 

برنامه ی آن به صورت زیر خواهد بود: 

#include <conio.h>
#include <iostream.h>

int main()
{   int a=9;
    for(int i=0;i<5;i++)    //dar kol 5 khat darim
    {
        for(int j=0;j<i;j++)    //rasme fasele ha
        {
            cout<<' ';
        }
        
        for(int j=0;j<a;j++)    //rasme a ta setare
        {
            cout<<'*';
            
        }
        a=a-2;                  // az a 2 ta kam mikonim baraye khate badi
        cout<<endl;
    }
        getch();
        return 0;
}

حلقه های تو در تو

 فرض کنید می خواهیم برنامه ای بنویسیم که یک کاراکتر * را در خروجی نمایش دهد. برای این کار به صورت زیر عمل میکنیم:

main()
{
    cout<<"*";
    cout<<endl;
    getch();
}

خب در این برنامه دستور cout تنها یک بار اجرا می شوند. حال فرض کنیم بخواهیم برنامه­ی بالا را به این صورت تغییر دهیم که یک عدد n را از ورودی گرفته و به تعداد آن یعنی n بار کاراکتر * را در خروجی پشت سر هم در یک خط نمایش دهیم.

برنامه بالا به صورت زیر تغییر خواهد یافت:

main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
       cout<<"*";
    }
    cout<<endl;
    getch();
}

تنها تفاوت این برنامه با برنامه ی قبلی در این است که کل کارهای برنامه ی اول را در یک حلقه قرار دادیم که این حلقه به تعداد n اجرا خواهد شد. پس از نمایش n کاراکتر * در خروجی، به ابتدای خط بعدی ( با استفاده از دستور cout<<endl ) می رویم.

خب، حالا فرض کنید میخواهیم دو عدد n و m را از ورودی گرفته و این بار n ستاره را در یک خط نمایش داده و همان خط را m بار تکرار کنیم. یعنی می خواهیم m خط را که در هر خط n ستاره وجود دارد، رسم کنیم.

خب با توجه به برنامه ی قبلی به این نتیجه می رسیم که باید برنامه ی بالا( که کشیدن یک خط از n ستاره است) را m بار تکرار کنیم. تا m خط که هر خط متشکل از n ستاره است را رسم کنیم.

 

برنامه ی بالا به صورت زیر تغییر خواهد کرد:

 main()
{
    int n,m;
    cin>>n>>m;
    for(int j=1;j<=m;j++)
    {
        for(int i=1;i<=n;i++)
        {
           cout<<"*";
        }
        cout<<endl;
    }
    getch();
}

در واقع ما در این برنامه از حلقه ی تو در تو استفاده کرده ایم!

 

توجه کنید که همیشه حلقه ی تو در تو از دو حلقه ی for تشکیل نشده است و می توان به جای for از while  هم استفاده کرد!

 

main()
{
    int n,m,j=0;
    cin>>n>>m;
    while(j<m)
    {
        for(int i=1;i<=n;i++)
        {
           cout<<"*";
        }
        cout<<endl;
        j++;
    }
    getch();
}

در برنامه ی بالا حلقه ی بیرونی را از for به while تغییر داده ایم!

امیدوارم تا اینجای کار به این نتیجه رسیده باشید که در مواقع ضروری از حلقه ی تو در تو استفاده خواهیم کرد و برنامه ی بالا را می توان بدون حلقه ی تو در تو هم نوشت!

 

برای مثال چند نمونه از حلقه های تو در تو را با هم حل خواهیم کرد.

 

 برنامه ای با استفاده از حلقه ی تو در تو بنویسید که شکل زیر را نمایش بدهد:

برنامه به صورت زیر نوشته می شود:

main()
{
    for(int i=1;i<=10;i++)
    {
        for(int j=1;j<=i;j++)
        {
            cout<<'*';
        }
        cout<<endl;
    }
    getch();
}

برنامه ای بنویسید که شکل زیر را نمایش دهد:

برنامه به صورت زیر نوشته می شود:

main()
{
    for(int i=1;i<=10;i++)
    {
        for(int j=1;j<=11-i;j++)
        {
            cout<<'*';
        }
        cout<<endl;
    }
    getch();
}

برنامه ای بنویسید که شکل زیر را نمایش دهد:

برنامه به صورت زیر نوشته می­شود:

main()
{
    for(int i=1;i<=10;i++)
    {
        for(int j=1;j<=i-1;j++)
        {
            cout<<" ";
        }
        for(int j=1;j<=11-i;j++)
        {
           cout<<"*";
        }
        cout<<endl;
    }
    getch();
}
 

این برنامه را به صورت زیر هم میتوان نوشت( چرا؟)

main()
{
    for(int i=1;i<=10;i++)
    {
        for(int j=1;j<=i-1;j++)
        {
            cout<<' ';
        }

        for(int j=i;j<=11;j++)
        {
            cout<<'*';
        }
        cout<<endl;
    }
    getch();
}

 

برنامه ای بنویسید که شکل زیر را نمایش دهد:

برنامه به صورت زیر نوشته خواهد شد:

main()
{
    for(int i=1;i<=10;i++)
    {
        for(int j=1;j<=10-i;j++)
        {
            cout<<' ';
        }
        for(int j=1;j<=i;j++)
        {
            cout<<'*';
        }
        cout<<endl;
    }
    getch();
}

برنامه ی بالا را می توان به صورت زیر هم نوشت. ( چرا؟)

main()
{
    for(int i=1;i<=10;i++)
    {
        for(int j=i;j<=10;j++)
        {
            cout<<' ';
        }
        for(int j=1;j<=i;j++)
        {
            cout<<'*';
        }
        cout<<endl;
    }
    getch();
}

 برنامه ای بنویسید که شکل زیر را نمایش دهد:

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

برنامه ی آن به صورت زیر نوشته می شود:

main()
{
    for(int i=1;i<=19;i++)    
    {
        if(i<=10)    //rasme 10 khate aval
        {
            for(int j=1;j<=10-i;j++)
            {
                cout<<' ';
            }
            for(int j=1;j<=i;j++)
            {
                cout<<'*';
            }
        }
        else    //rasme 9 khate ba'di
        {
            for(int j=1;j<=i-10;j++)
            {
                cout<<' ';
            }
            for(int j=1;j<=20-i;j++)
            {
                cout<<'*';
            }
        }
        cout<<endl;
    }
    getch();
}

 برنامه ای بنویسید که شکل زیر را نمایش دهد:

جواب سوال به صورت زیر خواهد بود:

int main()
{
    for(int i=1;i<=19;i++)    
    {
        if(i<=10)        //rasme 10 khate aval
        {
            for(int j=1;j<=i;j++)
            {
                cout<<'*';
            }
        }
        else        //rasme 9 khate ba'di
        {
            for(int j=1;j<=20-i;j++)
            {
                cout<<'*';
            }
        }
        cout<<endl;
    }
    getch();
}