مرتب سازی آرایه ها

 

با استفاده از آرایه ها میتوان تعداد زیادی داده را در کامپیوتر ذخیره کرد تا در هر زمان که به آنها احتیاج داشتیم به راحتی قابل دسترس باشند.

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

ولی یه لحظه فکر کنید اگه نمره ها داخل آرایه به صورت صعودی مرتب بود یعنی کمترین نمره در اولین خانه(با اندیس 0) و بیشترین نمره در خانه آخر ( با اندیس 999)بود خیلی راحت بدون انجام مقایسه با چاپ خانه آخر بیشنرین نمره رو چاپ میکردیم.

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

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

الان بیاید ببینیم چه روش هایی وجود داره که یک آرایه نامرتب رو مرتب کرد!

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

1- selection sort

2-insertion sort

3-bubble sort

اول از همه فرض کنید یه آرایه به اسم A داربم به صورت زیر:

 

A=7      13      1      58      37

 

فرض کنید A را به صورت صعودی قراره مرتب کنیم

 

1- selection sort

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

 

مبنا در این روش انتخاب یکی از خانه های آرایه و پیدا کردن  مقدار اصلی این جایگاه است و بعد از این که مقدار اصلی آنرا قرار دادیم میتوانیم سراغ خانه بعدی برویم و دنبال مقدار اصلی آن خانه باشیم! مثلا وقتی آرایه را به صورت صعودی داریم مرتب میکنیم و اولین خانه رو انتخاب میکنیم بعد از یک دور مقایسه مقدار اصلی آن که میشود کوچکترین مقدار را خواهد داشت!

 

در اینجا ابتدا اولین خانه رو انتخاب میکنیم ( خانه انتخابی با رنگ زرد در تصویر مشخص شده )

خانه صفرم را با خانه 1 ام  مقایسه میکنیم چون  7 از 13 بزرگتر نیست پس هیچ تغییری نداریم

خب الان میریم سراغ مقایسه خانه 0 ام با 2 ام  چون 7 از 1 بزرگتر هست  محتوای خانه ها را جا به جا میکنبم

تا اینجا خانه اول رو با 2 تا از خانه های بعد از خودش مقایسه کردیم  پس تا آخر آرایه باید ادامه دهیم

حالا خانه 0 ام را با خهانه 3 ام مقایسه میکنیم چون 1 از 58 بزرگتر نیست پس جابجایی نداریم

و در نهایت خانه 0 ام را با خانه 4 ام مقایسه میکنیم و چون 1 از 37 بزرگتر نیست جابجایی نداریم

الان خانه صفرم را با تمام خانه های بعد از خودش مقایسه کردیم و بعد از پایان این مقایسه ها مطمون ایم که کمترین مقدار الان در  همین خانه 0 ام قرار داره

الان میتونیم  خانه  بعدی( یعنی خانه یکم) را انتخاب کنیم و آنرا با 3 خانه بعد از خودش مقایسه کنیم و الی آخر

 

 

برنامه مرتب سازی selection sort

 

برای مرتب سازی آرایه مفروض A با مقادیر مشخص شده در بالا برنامه زیر را داریم:

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

using namespace std;

int main()
{    int a[5]={7,13,1,58,37};

    int i,t,j;
    for( i=0;i<5;i++){

         for(j=i+1;j<5;j++){
         if(a[i]>a[j])
         {
                      t=a[i];
                      a[i]=a[j];
                      a[j]=t;

                      }}}

                      for( i=0;i<5;i++)
                      cout<<a[i]<<"\t";
                      cout<<endl;


   getch();
}

همین برنامه رو میتوان برای یک آرایه با اندازه و مقادیر دلخواه نوشت. فرض کنید یک آرایه با سایز دلخواه داریم که با اعداد تصادفی مقدار دهی شده است سپس آنرا با الگوریتم selection به صورت صعودی مرتب میکنیم:

#include <conio.h>
#include <iostream>
#include <time.h>
using namespace std;

int main()
{
 srand(time(0));
cout<<"andaze array >>> ";
         int n,i,j,t;
         cin>>n;
         int arr[n];

        for( i=0;i<n;i++)
        arr[i]=rand()%100+1;

         for( i=0;i<n;i++)
                      cout<<arr[i]<<"\t";
                      cout<<endl<<endl;

    for( i=0;i<n;i++){

         for(j=i+1;j<n;j++){
         if(arr[i]>arr[j])
         {
                      t=arr[i];
                      arr[i]=arr[j];
                      arr[j]=t;

                      }}}

                      cout<<" array moratab "<<endl;
                      for( i=0;i<n;i++)
                      cout<<arr[i]<<"\t";
                      cout<<endl;

   getch();
}

 

2-insertion sort

 

در این روش که به آن روش درجی نیز میگویندفرض میشود که آرایه به 2 بخش مرتب و نامرتب تقسیم شده است که در ابتدا بخش مرتب فقط شامل خانه 0 ام است و بخش نامرتب شامل بقیه خانه های آرایه و روش کار در یک جمله خلاصه میشود:( در هر مرحله یک عنصر از بخش نامرتب بردار ، جایش را در مجموعه مرتب پبدا کن). 

 

   فرض کنید آرایه A  با مقادیر A=7      13      1      58      37 را قرار است با روش درجی به صورت صعودی مرتب کنیم.

در شکل زیر مراحل مرتب سازی در پایان هر مرحله را مشاهده میکنید.





توضیحات: در ابتدا بخش مرتب شامل عدد 7 است و بخش نامرتب شامل اعداد 37و58و1و13.

در مرحله اول خانه شماره 1 ام را به عنوان key در انتخاب کرده اگر از خانه 0 ام کوچکتر بود قبل از آن قرار میگیرد و اگر از آن بزرگتر بود تغییری نداریم.

(الان key عدد 13 است و چون از 7 بزرگتر است تغییری نداریم.)
( پس بخش مرتب شامل اعدا 13و7 است و بخش نامرتب شامل اعداد 37و58و1.)

در مرحله بعد خانه شماره 2 را به عنوان key انتخاب کرده با 2 خانه قبل از خودش یعنی خانه 1 ام و 0 ام مقایسه میکنیم و در هر جا که مقدار یکی از خانه ها از keyکوچکتر بود مقایسه را متوقف کرده و مقدار key را در آن خانه قرار میدهیم.

(الان key عدد 1 است . اول 1 را با 13 مقایسه میکنیم چون 13 از 1 بیشتر است سراغ خانه بعدی یعنی عدد 7 میرویم و در اینجا چون 7 از 1 بزرگتر است و تمام اعداد بخش مرتب را با key مقایسه کردیم .پس 1 قبل از 7 قرا میگیرد.)

پس در  هر مرحله عدد key را با خانه های قبل از خود مقایسه کرده و اگر مقدار خانه ای از key کمتر بود مقایسه را متوقف میکنیم و مقدار key  را در همان خانه قرا میدهیم .


  برای مرتب سازی آرایه مفروض A با مقادیر مشخص شده در بالا برنامه زیر را داریم:

#include <conio.h>
#include <iostream>
using namespace std;

int main()
{ int i,key,j;
   int a[5]={7,13,1,58,37};


     for( i=1;i<5;i++)  //مراحل مرتب سازی
        {
        key=a[i];
         for(j=i;j>0;j--)
         {
         if(key>=a[j-1])
               {break;}         

        a[j]=a[j-1];}           

           a[j]=key;}


         cout<<"namyesh array moratab"<<endl;
          for( i=0;i<5;ه++)
                      cout<<a[i]<<"\t";
         getch();}

  مراحل مرتب سازی آرایه A به تفکیک:

  A=7   13   1   58   37

------------------------------------
i=1    key=13

j=1 -->  7   13   1   58  37
 
A=7   13   1   58   37
------------------------------------

i=2    key=1

j=2 -->  7   13   13   58  37

j=1 -->  7   7   13   58  37

A=1   7   13   58   37
------------------------------------

i=3    key=58

j=3 -->  1   7    13   58  37

A=1   7   13   58   37
------------------------------------

i=4    key=37

j=4 -->  1   7    13   58  58

j=3 -->  1   7    13   58  58

A=1   7   13   37   58

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

#include <conio.h>
#include <iostream>
#include <time.h>
using namespace std;

int main()
{    srand(time(0));
         cout<<"andaze array >>> ";
         int n,i,j,key;
         cin>>n;
         int arr[n];

        for( i=0;i<n;i++)   //مقدار دهی تصادفی
        arr[i]=rand()%100+1;

         for( i=0;i<n;i++)       //نمایش آرایه اولیه
                      cout<<arr[i]<<"\t";
                      cout<<endl<<endl;


            for( i=1;i<n;i++)   //مراحل مرتب سازی
        {
        key=arr[i];
         for(j=i;j>0;j--)
         {
         if(key>=arr[j-1])
               {break;}         

        arr[j]=arr[j-1];}           

           arr[j]=key;}          



         cout<<endl<<"-----------moratab----------"<<endl;  // نمایش آرایه مرتب شده به صورت صعودی
          for( i=0;i<5;i++)
                      cout<<arr[i]<<"\t";
getch();}