مرتب سازی سریع یا Quick Sort

برنامه: مرتب سازی یک آرایه با الگوریتم quick Sort 

الگوریتم:

برای این کار از دو تابع استفاده می کنیم

1 - تابع پارتیشن

int Partition(int arr[],int Lobj,int Robj)

* که یک آرایه ( arr[] ) و سمت چپ ترین اندیس آرایه ( Lobj ) و سمت راست ترین اندیس آرایه ( Robj ).

تابع پارتیشن در هر مرحله اجرا ،سمت چپ ترین عنصر را(Lobj) به عنوان عنصر محوری (Pivot)انتخاب می کند و  تمام عناصر بزرگتر از آن را با عناصر کوچکتر از آن تعویض می کند. آرایه ورودی پس از پایان این تابع به گونه ایست که در هر مرحله عنصر محور را در مکان اصلی اش قرار می دهد.

\\.......................................................//

2- تابع کویک سورت

void quicksort(int arr[],int Lobj,int Robj)

 

تابع کویک سورت هر بار آرایه را به دو قسمت تقسیم می کند

قسمت اول شامل خانه های سمت چپ ترین خانه (Lobj) تا عنصر محوری  (Pivot)

قسمت دوم شامل خانه های عنصر محوری  (Pivot)  تا سمت راست ترین خانه  (Robj)

 

 برنامه مرتب سازی سریع به زبان++C

  #include
#include

#define size 21
//.................................................................
int Partition(int arr[],int Lobj,int Robj)
{
    int pivot = Lobj;
    int temp;
    while(Lobj < Robj)
    {
        while(arr[Lobj] <= arr[pivot])
        Lobj++;  

        while(arr[Robj] > arr[pivot])
        Robj--;

        if(Lobj < Robj)
       {
           temp = arr[Lobj];
           arr[Lobj] = arr[Robj];
           arr[Robj] = temp;
        }
     }
if( arr[Robj] < arr[pivot])
{
    temp = arr[pivot];
    arr[pivot] = arr[Robj];
    arr[Robj] = temp;
}
    return Robj;
}
//.................................................................
void quicksort(int arr[],int Lobj,int Robj)
{
    if(Lobj < Robj)
    {  
       int pivot = Partition(arr,Lobj,Robj);
       quicksort(arr,Lobj,pivot-1);
       quicksort(arr,pivot+1,Robj);
    }
}
//.................................................................
main()
{

    int test[size]={15,20,10,19,11,18,12,17,13,16,14,5,9,0,8,1,7,2,6,3,4};

    quicksort(test,0,size-1);

    for(int i=0;i<size;i++)
    cout<<"\ntest["<<i<<"] = "<<test[i];

    getch();
return 0;
}

 

   برنامه مرتب سازی سریع به زبان #C 

 using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;

namespace WindowsFormsApplication1
{
public partial class Form1 : Form
{
public Form1()
{
InitializeComponent();
}
int Partition(int[] arr, int Lobj, int Robj)
{
    int pivot = Lobj;
    int temp;
    while(Lobj < Robj)
    { 
       while(arr[Lobj] <= arr[pivot])
            Lobj++;

       while(arr[Robj] > arr[pivot])
           Robj--;

       if(Lobj < Robj)
       {
           temp = arr[Lobj];
           arr[Lobj] = arr[Robj];
           arr[Robj] = temp;
       }
    }
if( arr[Robj] < arr[pivot])
{
    temp = arr[pivot];
    arr[pivot] = arr[Robj];
    arr[Robj] = temp;
} return Robj;
}
//.................................................................
void quicksort(int[] arr,int Lobj,int Robj)
{
    if(Lobj < Robj)
    {  
        int pivot = Partition(arr,Lobj,Robj);
        quicksort(arr,Lobj,pivot-1);
        quicksort(arr,pivot+1,Robj);
    }

}

//.......................................................................

private void button1_Click(object sender, EventArgs e)
{
lbl1.Text = "Sorting ...";
int[] test = { 15, 20, 10, 19, 11, 18, 12, 17, 13, 16, 14, 5, 9, 0, 8, 1, 7, 2, 6, 3, 4 };
quicksort(test, 0, test.Length - 1);
lbl1.Text = "";
for (int i = 0; i < test.Length; i++)
lbl1.Text = lbl1.Text + test[i]+",";
}
}
}

مرتب سازی ادغامی merge sort

برنامه: آرایه ای از اعداد را به روش ادغام، یا همان  marge sort مرتب می کند

الگوریتم : 

از دو تابع استفاده می کنیم

1 - تابع  Marge Sort یا  MS().

void ms(int arr[],int lx,int rx)

این تابع از عنصر lx تا عنصر rx آرایه ی arr[] را پردازش می کند.

 

2 - تابع sort یا sortm

void sort(int arr[],int lx,int mid1,int mid2 , int rx)

این تابع  قسمت اول آرایه ی arr یعنی lx تا mid1  و قسمت دوم یعنی mid2 تا rx  را مرتب کرده  و در آرایه  temp نتیجه را که مرتب شده ی دو قسمت فوق می باشد را ذخیره ، سپس توسط دستور زیر ، عناصر مرتب شده را در آرایه ی اصلی کپی می کند.(که mid2=mid1+1)

for(int i=0,k=lobj;i <j;i++,k++) arr[k]=temp[i];

که lobj همان lx و robj همان rx می باشد.

 

* تابع  run در کد جاوااسکریپت ،رشته ی ورودی را به یک آرایه از اعداد تبدیل می کند.

فرمت ورودی اعدا باید به صورت زیر باشد.

example : 5,2,6,4,2,3,9,8,5,

که پس از هر عددی یک "," باید وارد شود و بدون هیچ گونه فاصله ای.

 برنامه مرتب سازی ادغامی با زبان ++C

#include
#include

#define size 10

void sort(int arr[],int lx,int mid1,int mid2 , int rx)
{
   int j=0; 
   int temp[size];
   int lobj=lx,robj=rx;

   //sorting arr[lx]..arr[mid] with arr[mid2]...arr[rx] and save it in temp[]
   while( (lx <= mid1) && (mid2 <= rx) )
   {
         if (arr[lx] < arr[mid2])
        {
                temp[j++]=arr[lx++];
        }
        else{
              temp[j++]=arr[mid2++];
              }
    }
   while( mid2 <= rx)
   {
          temp[j++]=arr[mid2++];
   }
   while( lx <= mid1)
   {
            temp[j++]=arr[lx++];
   }
   //copy temp[] into the original array ( arr[] )
   for(int i=0,k=lobj;i <j;i++,k++)       arr[k]=temp[i];
  }

void ms(int arr[],int lx,int rx)
{

   if(rx > lx)
   {

          int mid1 = (lx + rx)/2;
           int mid2 = mid1+1;

          ms(arr,lx,mid1);
         ms(arr,mid2,rx);
         sort(arr,lx,mid1,mid2,rx);
   }

}

int main()
{
   int test[size] = {5,9,1,8,2,7,3,6,4,0};

   cout<<"\n Array is ";
   for(int i=0; i          cout<<" "<<test[i];

   ms(test,0,size-1);

    cout<<"\nsorted array is : ";
   for(int i=0; i          cout<<" "<<test[i];
getch();
return 0;
}

 

  برنامه مرتب سازی ادغامی با زبان #C 

 using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;

namespace WindowsFormsApplication1
{
public partial class Form1 : Form
{
public Form1()
{
InitializeComponent();
}

void sort(int[] arr,int lx,int mid1,int mid2 , int rx)
{
   int j=0; 
   int[] temp = new int[arr.Length];
   int lobj=lx,robj=rx;

   //sorting arr[lx]..arr[mid] with arr[mid2]...arr[rx] and save it in temp[]
   while( (lx <= mid1) && (mid2 <= rx) )
   {
          if (arr[lx] < arr[mid2])
         {
               temp[j]=arr[lx];
                j = j + 1;
                lx = lx + 1;
         }
         else{
                temp[j]=arr[mid2];
                j = j + 1;
                 mid2 = mid2 + 1;
          }
   }
   while( mid2 <= rx)
   {
          temp[j]=arr[mid2];
           j = j + 1;
           mid2 = mid2 + 1;
   }
   while( lx <= mid1)
   {
           temp[j]=arr[lx];
           j = j + 1;
           lx = lx + 1;
   }
   //copy temp[] into the original array ( arr[] )
   for(int i=0,k=lobj;i <j;i++,k++)           arr[k]=temp[i];
}


void ms(int[] arr, int lx, int rx)
{

   if(rx > lx)
   {

             int mid1 = (lx + rx)/2;
             int mid2 = mid1+1;

              ms(arr,lx,mid1);
              ms(arr,mid2,rx);
              sort(arr,lx,mid1,mid2,rx);
 }

}
private void button1_Click(object sender, EventArgs e)
{

   lbl1.Text = "Sorting ...";
   int[] test = { 0,5,2,3,1,3, 9, 0, 8, 1, 7, 2, 6, 3, 4 };
   ms(test, 0, test.Length - 1);
   lbl1.Text = "";
   for (int i = 0; i < test.Length; i++)
             lbl1.Text = lbl1.Text + test[i] + ",";
}
}
}

جست و جوی خطی

برنامه: بررسی وجود داشتن یا نداشتن عدد ورودی در آرایه

 

الگوریتم:

در این روش تک تک خانه های آرایه را مورد بررسی قرار می دهیم که آیا عدد مورد نظر (obj) در آن وجود دارد یا خیر.

 

int linear_search(int arr[],int arrsize, int obj)
{
         for(int i=0;i<arrsize;i++)
         {
                 if(arr[i] == obj)  
                 {
                         return i;
                 }
         }
          return (-1);
}

توسط دستورات بالا جست و جو انجام می شود که در صورت یافتن، مکان قرار گیری عنصر در آرایه( i )، و اگر هم عنصر مورد نظر یافت نشد مقدا 1- را بر می گرداند

 

*در دو برنامه سی شارپ و جاوااسکریپت ، تابع ، ابتدا آرایه ی ورودی را به یک آرایه از اعداد تبدیل می کند سپس توسط دستورات فوق ، عمل جست و جو را انجام می دهد.

آرایه ورودی باید بدون هیچ گونه فاصله ای به  این صورت وارد شود که بعد از هر عدد یک علامت کاما (  , ) قرار بگیرد.

مانند:

1,5,6,88,52,101,23,25,12,1,47,7,8,

 

 برنامه ی جست و جوی خطی به زبان ++C

 //Writed By barnamenevisi-ccj.mihanblog.com

#include
#include

#define size 10


int linear_search(int arr[],int arrsize, int obj)
{
    for(int i=0;i<arrsize;i++)
   {
      if(arr[i] == obj)  
      {
           return i;
       }
   }
   return (-1);
}
main()
{
int test[size]={2,6,4,8,3,5,9,7,1,0};
int object;
int result;

 cout<<"\n\nEnter Number to search it : ";
cin>>object;

result = linear_search(test,size,object);
if ( result == -1)
{
cout<<"\nNot Find :( .";
}
else{
cout<<"\nItem Founded in element "<<result+1<<" .";
}

getch();
return 0;
}

 

   برنامه ی جست و جوی خطی به زبان #C 

 using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;

namespace WindowsFormsApplication1
{
public partial class Form1 : Form
{
public Form1()
{
InitializeComponent();
}
//...................................................................................
int linear_search(string test,string objsearch)
{
   int i = 0;
   int test2size = 0;
   int obj = Int32.Parse(objsearch);

   for (i = 0; i < txt1.TextLength; i++)
         if (test[i] == ',')
                test2size++;

   int[] test2 = new int[test2size];
   test2size = 0;

   for (i = 0; i < txt1.TextLength; i++)
   {

        if (test[i] != ',')
             test2[test2size] = test2[test2size] * 10 + Int32.Parse(test[i].ToString());
       else test2size++;

   }


    for(i=0;i<test2size;i++)
   {
          if(test2[i] == obj)  
          {
                  return i;
          }
   }
   return (-1);
}

//..............................................................
public void button1_Click(object sender, EventArgs e)
{

int result = linear_search(txt1.Text , txt2.Text);

 

if (result == -1)
MessageBox.Show("Not Found");
else MessageBox.Show("Item Founded in element " + (result+1));

}
}
}

جست و جوی دودویی

برنامه: پیدا کردن یک عدد در آرایه به روش دودویی یا Binary Search  

الگوریتم:

ابتدا آرایه ی ورودی را توسط یکی از روش های مرتب سازی (به عنوان مثال مرتب سازی حبابی یا Buble Sort)  که قبلا نوشته ایم ،مرتب کرده سپس با دستورات زید به جست و جو می پردازیم

 

int binary_search(int arr[],int arrsize,int obj)
{
     int first = 0;
     int last = arrsize;
     int middle = (first + last) / 2;

      while(last >= first)
      {
             if(arr[middle] == obj)
             {
                               return middle;
             }
              else if(arr[middle] > obj)
                     {
                            last = middle-1;
                            middle = (first + last) / 2;
                       }else
                              {
                                       first = middle+1;
                                       middle = (first + last) / 2;
                               }
           }
return -1;
}

ورودی ها عبارتند از: 

1 - یک آرایه (مرتب شده به صورت صعودی). (اگر آرایه نزولی مرتب شده باید جای ">"  ,  "<" را عوض کنیم)

2 - اندازه ی آرایه

3 - و عددی که باید دنباله آن بگردیم.

 

که در صورت پیدا کردن عدد در آرایه عنصر، اندیس آن و در غیر اینصورت عدد منفی یک ( 1- ) را بر می گرداند.

 

* نکات مربوط به کد سی شارپ و جاوااسکریپت

تکست باکس اول  آرایه ی ورودی را با این فرمت که پس از هر عدد یک " , " باشد(بدون هیچ فاصله ای) را گرفته و در تکست باکس دوم عددی را که باید به دنبال آن بگریم  از ورودی می گیریم.

 برنامه ی جست و جوی دودویی به زبان ++C

 //Writed By barnamenevisi-ccj.mihanblog.com

#include
#include

#define size 10
//--------------------------Buble Sort-------------------------------
void bubleSort(int num[],int numSize)
{
   int temp=0;
   for(int i=numSize;i>0;i--)
   {
           for(int j=0;j<i;j++)
                 if(num[j] > num[j+1])
                 {
                            temp = num[j];
                            num[j] = num[j+1];
                            num[j+1] = temp;
                  }
   }

}
//-----------------------Binary Search-------------------------------------
int binary_search(int arr[],int arrsize,int obj)
{
   int first = 0;
   int last = arrsize;
   int middle = (first + last) / 2;

   while(last >= first)
   {
           if(arr[middle] == obj)
           {
                     return middle;
            }
            else if(arr[middle] > obj)
                   {
                           last = middle-1;
                           middle = (first + last) / 2;
                   }else
                          {
                                first = middle+1;
                                middle = (first + last) / 2;
                           }
   }
return -1;
}
//--------------------------Main ------------------------------------
main()
{

   int test[size]={10,19,12,18,15,17,11,14,13,16};
   int searchobj=0;
   int flag;

   //sort array
   bubleSort(test,size-1);

   cout<<"Enter number to search : ";
   cin>>searchobj;

   flag = binary_search(test,size-1,searchobj);

   if(flag != -1)
                    cout<<"\nfind item in element "<<flag+1<<" .";
   else         cout<<"\nnot found.";

getch();
return 0;
}

 

   برنامه ی جست و جوی دودویی به زبان #C 

 using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;

namespace WindowsFormsApplication1
{
public partial class Form1 : Form
{
public Form1()
{
InitializeComponent();
}
//-----------------------Binary Search-------------------------------------
int binary_search(int[] arr, int arrsize, int obj)
{
   int first = 0;
   int last = arrsize;
   int middle = (first + last) / 2;

   while(last >= first)
   {
            if(arr[middle] == obj)
            {
                     return middle;
             }
            else if(arr[middle] > obj)
                   { 
                             last = middle-1;
                             middle = (first + last) / 2;
                   }else{
                                 first = middle+1;
                                 middle = (first + last) / 2;
                            }
    }
return -1;
}
//.............................Buble Sort........................................
int[] bubleSort(string test)
{
   int i = 0;
   int test2size = 0;

   for (i = 0; i < txt1.TextLength; i++)
         if (test[i] == ',')
               test2size++;

    int[] test2 = new int[test2size];
   test2size = 0;

    for (i = 0; i < txt1.TextLength; i++)
   {

        if (test[i] != ',')
                 test2[test2size] = test2[test2size] * 10 + Int32.Parse(test[i].ToString());
        else test2size++;

   }
   //sorting by buble sort algorithm
   int temp = 0;
   for (i = test2size - 1; i > 0; i--)
   {
             for (int j = 0; j < i; j++)
                      if (test2[j] > test2[j + 1])
                      {
                                 temp = test2[j];
                                 test2[j] = test2[j + 1];
                                 test2[j + 1] = temp;
                       }
   }

return test2;

}
private void button1_Click(object sender, EventArgs e)
{
   int flag;
   int[] test = bubleSort(txt1.Text);

   flag = binary_search(test, test.Length, Int32.Parse(txt2.Text));
   if (flag != -1)
   {
                 MessageBox.Show("Find item on element " + (flag + 1) + " .");
   }
   else MessageBox.Show("Not Found.");

}
}
}

محاسبه لگاریتم و تابع نمایی یا Ln

برنامه : محاسبه ی log و Ln اعداد.  

الگوریتم:

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

 

و درنهایت

 

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

.با نوشتن کد زیر در تابع Ln کار محاسبه ی دنباله رو انجام میدیم

 

2*( (1 / temp )* (power(t,2*n+1)) )    که  temp =(2*n+1) ,t =(z-1)/(z+1)

دستور بالا تک جمله های دنباله ی بالا را به ترتیب از n=0 تا .... محاسبه و آنها را در متغیر result جمع می کند.

به این ترتیب Ln عدد محاسبه می شود و در نهایت در تابع Log با استفاده از فرمول ، لگاریتم را محاسبه می کنیم.

 

* حاصل جملات دنباله ی فوق به ازی n های بزرگتر ، کوچکتر می شود لذا با توجه به  شرط حلقه ی While ،زمانی از حلقه ی While خارج می شیم که اختلاف جمله ی فعلی از جمله ی قبلی به حداقل که رسیده باشه.در اینجه یک ضربدر ده به توان منفی 11.(هرچه این مقدار کوچکتر باشد حاصل دقیق تر هست.)

 

برنامه ی محاسبه لگاریتم و تابع نمایی به زبان ++c

double power(double x, int p);//x^p

double ln(double z)
{
   double t =(z-1)/(z+1);
   double result=0,oldResult=1;
   int n=0;
   double temp=0;
   while((oldResult < result?result - oldResult:oldResult -   result) > 0.00000000001)
   {
           oldResult = result;

           temp =(2*n+1);
           result =result + 2*( (1 / temp )* (power(t,2*n+1)) );

           n=n+1;
   }
return result;

}

 

double log(double x,double a)
{
       return ln(x)/ln(a);

}

 

  برنامه ی محاسبه لگاریتم و تابع نمایی به زبان #c

double power(double x, int p);//x^p

double ln(double z)
{
   double t = (z - 1) / (z + 1);
   double result = 0, oldResult = 1;
   int n = 0;
   double temp = 0;

   while ((oldResult < result ? result - oldResult : oldResult - result) > 0.000000000000001)
   {
             oldResult = result;
             temp = (2 * n + 1);

             result = result + 2 * ((1 / temp) * (power(t, 2 * n + 1)));

             n = n + 1;
   }
return result;

}

 

double log(double x, double a)
{
     return ln(x) / ln(a);
}

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

برنامه: نمایش درخت دودویی با استفاده از آرایه توضیحات :

یک درخت دودویی رو به دو صورت میشه نمایش داد
1 - نمایش با آرایه
2 - نمایش با لیست پیوندی

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

* اگر عنصری در خانه ی i ام ارایه باشد آنگاه
           پدر ان در خانه ی جزوصحیح i/2 قرار دارد.
           فرزند چپ آن در خانه ی 2*i قرار دارد.
           فرزند راست آن در خانه ی 1+2*i قرار دارد.

*برای نمایش درختی با عمق k به ارایه ای با 2^k-1 خانه نیاز داریم.


درخت ورودی را به صورت زیر از ورودی میگیریم.((فرزند راست ، فرزند چپ)پدر)

(F(B(A,D(C,E)),G(,I(H))))

الگوریتم:

تابع set آرایه ی []s که حاوی رشته ی فوق هست را به همراه ارایه ی []t که قرار هست درخت طبق قوانین بالا در ان ذخیره شود و متغیری که اندازه ی ارایه []s را در خود دارد را از ورودی گرفته و با چند دستور if عملیات را انجام می دهد.

 برنامه ی نمایش درخت با ارایه به زبان ++c

 void set(char s[],char[] t,int sSize)
{
    int i=0;
    int j=0;
    int depth=1,oldDepth=1;
    
    while(i < sSize)
    {
    if( s[i]=='(' )
    {
                 if(j==0) j=1;
                 else  j=2*j;
                 i=i+1;
    }
    else if( s[i]==',' )
    {
        j=j+1;
        i=i+1;
    }
    else if( s[i]==')' )
    {
        j=j/2;
        i=i+1;
    }
    else {
         
         t[j]=s[i];
         i=i+1;
         }
    }//end while
}//end function

مرتب سازی جابجایی

برنامه:آرایه ای به طول size رو با روش جابجایی یا  exchangeSort به طور صعودی مرتب می کند

void exchangeSort(int s[],int size)
{
   int i,j;
   int temp;
   for(int i=0;i<size-1;i++)
        for(j=i+1;j<size;j++)
            if(s[i] > s[j])
            {
                    cout<<"\n Exchane "<<s[i]<<" by "<<s[j];
                    temp=s[i];
                    s[i]=s[j];
                    s[j]=temp;

            }
}

 

در واقع در هر مرحله اجرای حلقه ی دوم،  کوچکترین عنصر ارایه در خانه ی آی ام (به ترتیب خانه اول،دوم،و ...) قرار داده میشه.

پروژه ساخت کامپایلر برای درس برنامه سازی سیستم

پروژه ساخت کامپایلر برای درس برنامه سازی سیستم

 

برای دانلود بر روی تصویر زیر کلیک کنید .

مرتب سازی درجی

برنامه:آرایه ای به طول size رو با روش درجی یا insertionSort به طور صعودی مرتب می کند

void insertionSort(int s[],int size)
{
   int i,j;
   int temp=s[1];
   for(i=1;i<size;i++)
   {
        j=i-1;;
        temp=s[i];
        while(j>=0 && s[j]>temp)
        {
                 cout<<"\n Moving s["<<j<<"] to s["<<j+1<<"]";
                 s[j+1]=s[j];
                 j--;

       }
       s[j+1]=temp;
    }

}

 

 

مرتب سازی انتخابی

برنامه:آرایه ای به طول size رو با روش انتخابی یا selectionSort به طور صعودی مرتب می کند

void selectionSort(int s[],int size)
{
   int i,j,smallest;
   int temp;

   for(int i=0;i<size-1;i++)
   {
        smallest=i;
        for(j=i+1;j<size;j++)
             if(s[j] < s[smallest])
                      smallest=j;

       cout<<"\n Exchane "<<s[i]<<" by "<<s[smallest];
       temp=s[i];
       s[i]=s[smallest];
       s[smallest]=temp;

   }
}