آموزش برنامه نویسی به زبان ++C

این وبلاگ جهت آموزش برنامه نویسی به زبان ++C برای دانش آموزان دبیرستان فرزانگان ایجاد شده است.
پنجشنبه, ۱۶ آذر ۱۳۹۱، ۰۶:۱۷ ب.ظ

مرتب سازی

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

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


حال فرض کنید که از شما بپرسند عنصر 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

در این روش مرتب سازی خانه ی دوم آرایه را انتخاب می کنیم و این خانه را با خانه ی قبلی خود مقایسه می کنیم و اگر بزرگتر بود پشت سر خانه ی قبلی خود، قرار میگیرد. 
در مقایسه های بعدی هر خانه را( key) با خانه های قبل از خودش یکی یکی مقایسه می کنیم و تا زمانی پیش می رویم که به یک خانه برسیم که از کلید یا key بزرگتر باشد. پس دیگر نباید پیش برویم و باید کلید را در محلی که به آن رسیده ایم قرار بدهیم. 

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

همچنین می توان از مثال های زیر نیز استفاده کرد: 




برنامه ی این روش مرتب سازی در ادامه آمده است. 

#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();
    
}







نوشته شده توسط سارا نازاری
ساخت وبلاگ در بلاگ بیان، رسانه متخصصان و اهل قلم

آموزش برنامه نویسی به زبان ++C

این وبلاگ جهت آموزش برنامه نویسی به زبان ++C برای دانش آموزان دبیرستان فرزانگان ایجاد شده است.

مرتب سازی

پنجشنبه, ۱۶ آذر ۱۳۹۱، ۰۶:۱۷ ب.ظ

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

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


حال فرض کنید که از شما بپرسند عنصر 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

در این روش مرتب سازی خانه ی دوم آرایه را انتخاب می کنیم و این خانه را با خانه ی قبلی خود مقایسه می کنیم و اگر بزرگتر بود پشت سر خانه ی قبلی خود، قرار میگیرد. 
در مقایسه های بعدی هر خانه را( key) با خانه های قبل از خودش یکی یکی مقایسه می کنیم و تا زمانی پیش می رویم که به یک خانه برسیم که از کلید یا key بزرگتر باشد. پس دیگر نباید پیش برویم و باید کلید را در محلی که به آن رسیده ایم قرار بدهیم. 

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

همچنین می توان از مثال های زیر نیز استفاده کرد: 




برنامه ی این روش مرتب سازی در ادامه آمده است. 

#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();
    
}





موافقین ۱ مخالفین ۰ ۹۱/۰۹/۱۶
سارا نازاری

نظرات  (۴۴)

mishe insertion sortam bezarin?
پاسخ:
باشه حتما!
تو اکثر آرایه ها یه فور این شکلی دارید:
این همون گرفتن آرایه از ورودیه یا باهاش متفاوته؟ من گیج شدم خیلی غریبه:-"
  for(int i=0;i<n;i++)
    {
        a[i]=rand()%50;
    }
پاسخ:
are

monteha meghdaresho ba random por mikone khodesh
niazi be az vorudi gereftan nist ke cin koim o in harfa .... 
سلام خانم فردا امتحان خیلی سخته ؟
میتونیم به راحتی نمره کامل بیاریم ؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟
پاسخ:
age khunde bashi hatman!
insertion sort ro nemishe b jaye key, mese selection sort ba ye tempi chizi benevisim?
پاسخ:
یعنی چی؟ همین جوریه دیگه نوشتنش ... 
insertion sort akharesh doroste?a[j+1]=key;

پاسخ:
are

خانم امتحان از کل مباحث

آرایه ها هم میاد ؟؟؟؟

پاسخ:
بله دیگه، در امتحان های پایان ترم همه‌ی مباحث مورد پرسش قرار می‌گیرد.
۱۸ دی ۹۱ ، ۱۹:۳۸ یکی از بجه های فرز 4
مرسی خانم واقعا مفید بود :)
سلام . میشه درباره انواع جستجو ها تو آرایه ها یکم توضیح بدید؟
سلام اگر max و min چند عدد را تشکیل بدیم و بعد بخوایم طوری مرتبش کنیم که تشکیل یه عدد بزرگ یا بر عکس بده برنامش چه جوری نوشته میشه
دستتون درد نکنه خیلی زحمت کشیدید

سلام خانم می خواستم بپرسم روز اول مهر امتحان داریم ؟

 

پاسخ:
rooze aval na!

سلام خانم  بالاخره f4روز اول مهر امتحان داره یا نه؟

 

khanoom nazari ma farda Mtehan darim
yani rooz e aval e mehr bayad Mtehean bedim??

khanoom Nazari soale 3pd soale manam hast mishe lotfan javab bediiiiin?

sسلام این برنامه   مرتب سازی حبابی برای جلوگیری از صرف وقت چه شرطی میتوانیم قراربدیم که اگ مرتب بوود مقایسه تکرار نشود فقط1بار مقایسه شود
خانووووم من اصلا نمیفهمم تو insertion sort اون کلید چی کار میکنه اون وسط....:( مگه نمیشه اگه خونه بعدی از خونه قبلی بزرگتر بود  یه متغیر مساوی صفر بذاریم بعد عدد 2تا خونه رو جابجا کنیم؟؟؟؟؟؟؟؟؟؟؟

واقعا ممنون عالی بود

پاسخ:
خواهش میکنم. 
مرسی عالی بود فقط یکم زیادی پیچیدش کردید
۱۴ آذر ۹۲ ، ۱۸:۰۸ شیما بارکزهی
با سلام
میشه برام توضیح بدین اصلا ما چرا نیاز به دوتا فور داریم؟
 فور اول چکار میکنه؟ و فور دوم چکار میکنه
؟

پاسخ:
حلقه درونی هربار یک مینیمم یا ماکزیمم رو پیدا میکنه و حلقه ی بیرونی و بزرگه حلقه درونی رو به تعداد طول آرایه اجرا میکنه تا همه ماکزیمم یا مینیمم ها پیدا بشه. 
۲۰ آذر ۹۲ ، ۲۲:۱۵ شیما بارکزهی
سلام
ممنون از توضیحتون ولی
اگر در حلقه فور اول طول ارایه رو i بگیریم : i میشود از 0 تا n
و حلقه ی فور دوم اگر باشد تعداد مقایسه های ما: i  میشود از 0 تا n-i-1

سلام خانم ببخشید امتحان ترم فرزانگان 4(فردا)کتبیه یا عملی؟؟؟:-|
kosarفرداامتحان کتبیه.
ممنون!
دست شما درد نکنه
خانوم عزیز
خدا به داد منی بیچاره برسه دارم میزنم تو سرم با این کدا :نگران
با سلام
جسارتا در مرتب سازی درجی جای دستورات if و else را اشتباه نوشته اید.
لطفا بررسی کنید.
با تشکر
این دستور چکار میکنه
 a[i]=rand()%50;
    }
پاسخ:
عدد تصادفی از 0 تا 49 تولید می کنه
ما فردا امتحان داریم خانم نازاری ترم اول مارو رها کردید !!! فرززانگان 6 ام!!!
پاسخ:
امیدوارم امتحانتو خوب بدی. :) 
سلام خانم مر30 خیلییییییییی خیلی خوب آموزش میدیدن 
من همچین وبی ندیدم    بی زجمت فیلم آموزش هم بزارید ممنون میشم . 
در رابطه با طراحی سایت هم راهنمایی کنید. 

تشریف بیارید باعث افتخار.
ronaldo-ps.blogfa.com
پاسخ:
ممنون. به زودی طراحی وبسایت هم اضافه میشه. 
عالی بوددددددددد
ممنونم بانو!
فقط فهم کد مرتب سازی درجی واسم یکم سخته فک کنم مجبور شم خودم یک جور دیگه بنویسمش.
وبلاگتون عااااااااالیه!
انشاالله همیشه موفق باشید 3>
it good for me thanks for this information
واسه یه قسمت از پروژه ای که می خوام بنویسم نیاز به یه الگوریتم مرتب سازی ساده و در عین حال با مرتبه زمانی کم بودم که وارد این سایت شدم، کمی که کامنت ها رو خوندم متوجه شدم که این سایت توسط یه دبیر (استاد) واسه دانش آموزاش گذاشته شده، اولا باید بگم واقعا امیدوار شدم که هنوز تو ایران همچین افراد دلسوزی هستند و شرمنده شدم چون من دانشجوی رشته فناوری اطلاعات دانشگاه صنعتی ارومیه هستم و باور کنید هیچ کدوم از اساتید ما نتونسته بودند مرتب سازی ها رو به این قشنگی توضیح بدن. دستتون درد نکنه تنها خواهشم اینه که یا در شغلی که هستید همین طوری ادامه بدید. مرسی به شرفتون.
۲۶ دی ۹۳ ، ۲۲:۱۰ میتی ***********
سلام
وبلاگ عالی سارا جون ولی اگه درباره ی تابع وارایه دو بعدی و...... سوالای بیشتری بذاری عالیه
خیلی ممنونم

ممنونم

شما واقعا معلمی خوب اگر معلمی باید بدونین تابع rand()
در کتابخانه هاایی که نوشتین وجود ندارد و در کتابخانه که در زیر اشاره میکنم هست لطف کنین ایرادو بگیرین که کدهاتون مشکل نداشته باشد.
cstdlib
biiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii nahayat sepas gozarammmmmmmmmmmm
تشکر خوب بود استفاده کردیم
با سلام.در صورت امکان برنامه مرتب سازی انتخابی به کمک کلاس ها را به ایمیلم ارسال کنید.
با سلام.
temp  یعنی چی؟
۰۷ اسفند ۹۴ ، ۱۲:۲۶ ترنم باران

سلام میشه توضیح بدید حذف و اضافه در آرایه مرتب چه جوریه؟؟


manzor az 
rand () %50
chie?
باسلام از قسمت تعریف ارایه
a [n خطا میگیره و میگه باید به صورت مجزا ثبت بشه راهنمایی میکنید
مرتب سازی حبابی
سلام جواب این برنامه رو میخوام آرایه aرا با nعضو خوانده سپس آرایهbرا باnعضو خوانده آن هارا به طور جداگانه مرتب نموده  سپس آنهارا بصورت مرتب درآرایهcقرار دهید
با سلام
مرتب سازی برای آرایه های رشته ای به چه صورتی است؟

ارسال نظر

ارسال نظر آزاد است، اما اگر قبلا در بیان ثبت نام کرده اید می توانید ابتدا وارد شوید.
شما میتوانید از این تگهای html استفاده کنید:
<b> یا <strong>، <em> یا <i>، <u>، <strike> یا <s>، <sup>، <sub>، <blockquote>، <code>، <pre>، <hr>، <br>، <p>، <a href="" title="">، <span style="">، <div align="">
تجدید کد امنیتی