تابع مرتب سازی شمارشی (Counting Sort) در C++

تابع مرتب سازی شمارشی (Counting Sort) که متوسط عملکرد آن O(n + k)  است:

void countingSort(vector<int>& arr)
{
    int Min, Max;
    Min = Max  = arr[0];
    for(int i = 1; i < arr.size(); i ++)
    {
        if(arr[i] < Min)
            Min = arr[i];
 
        if(arr[i] > Max)
            Max = arr[i];
    }
    int Range = Max - Min + 1;
 
    vector<int> Count(Range,0);
 
    for(int i = 0; i < arr.size(); i ++)
        Count[arr[i] - Min] ++;
 
    int Index = 0;
    for(int i = Min; i <= Max; i ++)
        for(int j = 0; j < Count[i - Min]; j ++)
            arr[Index ++] = i;
}


//end

تابع مرتب سازی سطلی یا صندوقی(Bucket Sort) در C++

تابع مرتب سازی سطلی یا صندوقی(Bucket Sort) که متوسط عملکرد آن (O(n  است:

void bucketSort(int a[],int n, int max)
{
    int* buckets = new int[max];
    int SIZE = n;
    for(int j = 0 ; j <= max ; j++)
        buckets[j] = 0;
    for(int i = 0 ; i < SIZE ; i++)
        ++buckets[a[i]];
    for(i = 0 , j = 0 ; j <= max ; ++j)
        for(int k = buckets[j] ; k > 0 ; k--)
            a[i++] = j;
}

//end

الگوریتم مرتب سازی ادغامی(Merge Sort) در C++

مرتب سازی ادغامی، حل مسئله را به چند قسمت تبدیل کرده و آن ها را جدا حل میکند. به همین سبب از چندین تابع برخوردار است و متوسط عملکرد آن از رابطه O(n log n)  بدست می آید.

void mergeSort(int numbers[], int temp[], int array_size)
{
  m_sort(numbers, temp, 0, array_size - 1);
}


void m_sort(int numbers[], int temp[], int left, int right)
{
  int mid;

  if (right > left)
  {
    mid = (right + left) / 2;
    m_sort(numbers, temp, left, mid);
    m_sort(numbers, temp, (mid+1), right);

    merge(numbers, temp, left, (mid+1), right);
  }
}

void merge(int numbers[], int temp[], int left, int mid, int right)
{
  int i, left_end, num_elements, tmp_pos;

  left_end = (mid - 1);
  tmp_pos = left;
  num_elements = (right - left + 1);

  while ((left <= left_end) && (mid <= right))
  {
    if (numbers[left] <= numbers[mid])
    {
      temp[tmp_pos] = numbers[left];
      tmp_pos += 1;
      left += 1;
    }
    else
    {
      temp[tmp_pos] = numbers[mid];
      tmp_pos += 1;
      mid += 1;
    }
  }

  while (left <= left_end)
  {
    temp[tmp_pos] = numbers[left];
    left += 1;
    tmp_pos += 1;
  }
  while (mid <= right)
  {
    temp[tmp_pos] = numbers[mid];
    mid += 1;
    tmp_pos += 1;
  }

  //modified
  for (i=0; i < num_elements; i++)
  {
    numbers[right] = temp[right];
    right -= 1;
  }
}


//end

تابع مرتب سازی درجی(Insertion Sort) در C++

تابع مرتب سازی درجی(Insertion Sort) که متوسط عملکرد آن О(n²) است:

void insertionsort ( int arr[] ,  int n)
{
    int  i , j , x;
    for (i=2 ; i<=n ; i++)
    {
         x = arr [i];
         j=  i-1;
         while( j>0  &&  arr [j] > x)
         {
                arr[j+1] = arr [j];
                j--;
          }
      arr[j+1]=x;
    }
}

//end

تابع مرتب سازی سریع(Quick Sort) در C++

تابع مرتب سازی سریع(Quick Sort) که متوسط عملکرد آن O(n log n) است:

void quickSort(int x[], int left, int right)
{

        int i = left, j = right;

        int tmp;

        int pivot = x[(left + right) / 2];


        while (i <= j)
        {

                while (x[i] < pivot)

                        i++;

                while (x[j] > pivot)

                        j--;

                if (i <= j)
                {

                        tmp = x[i];

                        x[i] = x[j];

                        x[j] = tmp;

                        i++;

                        j--;

                }

        }


        if (left < j)

                quickSort(x, left, j);

        if (i < right)

                quickSort(x, i, right);

}


//end

تابع مرتب سازی انتخابی(Selection Sort) در C++

تابع مرتب سازی انتخابی(Selection Sort) که متوسط عملکرد آن О(n²)  است:

void selectionSort(int arr[], int len)
{
    int i, j, minIndex, tmp;
    for (i = 0; i < len - 1; i++)
   {
       minIndex = i;
        for (j = i + 1; j < len; j++)
            if (arr[j] < arr[minIndex])
                minIndex = j;
      if (minIndex != i)
      {
            tmp = arr[i];
         arr[i] = arr[minIndex];
            arr[minIndex] = tmp;

      }

   }

}

//end

جلسه بیستم: مرتب سازی آرایه ها (Sort)

مرتب سازی آرایه ها (Sort):

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

برای مرتب سازی آرایه یک بعدی، روش های مختلفی همچون روش مرتب سازی حبابی (Bubble Sort)، انتخابی (Selection Sort)، سریع (Quick Sort)، درجی (Insertion Sort)، ادغامی (Merge Sort) و ... وجود دارد که در تمامی روش های فوق تفاوت در روش مقایسه و جابجایی است، که باعث شده الگوریتم های متفاوتی تولید شوند.
در این بین الگوریتم مرتب سازی حبابی بسیار ساده و قابل فهم است.

در پست های آینده، توابع اکثر روش های مرتب سازی گذاشته خواهد شد.

جلسه نوزدهم: آرایه یک بعدی به عنوان آرگومان تابع

آرایه یک بعدی به عنوان آرگومان تابع:

در زبان c++ همانگونه که میتوانیم انواع متغیر ها را به عنوان آرگومان به یک تابع ارسال کنیم، آرایه ها نیز میتوانند به عنوان آرگومان به توابع ارسال شوند. برای ارسال آرایه به تابع، باید نام آرایه به عنوان آرگومان ذکر شود. اگر آرایه به عنوان آرگومان تابع باشد، پارامتر معادل آن میتواند بصورت زیر تعریف شود:
1. آرایه با طول مشخص
2. آرایه با طول نامشخص که در این صورت بهتر است طول آرایه به آرگومان دیگری منتقل شود.
3. اشاره گر که میتوان اشاره گری به یک آرایه تعریف نمود.(در جلسات آینده با اشاره گر ها کاملا آشنا خواهید شد.)

شکل کلی ارسال آرایه به توابع:

void f1(int x[]);
void f2(int x[], int len);

void main()
{
    int x[10];
    f1(x);
    f2(x,10);
}
void f1(int x[10])
{
    ...
}
void f2(int x[], int len)
{
    ...
}

//end

جلسه هجدهم: مقدار دهی اولیه به آرایه یک بعدی

مقدار دهی اولیه به آرایه تک بعدی:

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

مثال:

int x[3] = {10};
int x[3] = {10, 20};
int x[3] = {10, 20, 30};

//end

خالی گذاشتن بُعد آرایه هنگام تعریف:

در زبان c++ در آرایه های یک بعدی فقط به شرطی میتوان بعد آرایه را خالی گذاشت که هنگام تعریف آن مقدار دهی نماییم، در غیر این صورت خطا خواهیم داشت.

مثال درست:

int x[] = {10, 20, 30};

//end

جلسه هفدهم: تعریف آرایه های یک بعدی

آرایه های یک بعدی:
تاکنون داده های ورودی و بقیه داده های مورد نیاز را در متغیر ها و ثابت ها ذخیره میکردیم. اما اگر تعداد ورودی ها زیاد باشد، نیاز داریم تعداد زیادی متغیر را تشکیل دهیم که این کار باعث میشود روند عملیات برنامه نویسی بسیار پیچیده شود. بنابراین برای جلوگیری از این مشکلات میتوانیم از امکان تعریف آرایه ها در زبان ++C بهره مند شویم.
آرایه ها خانه های پشت سر هم در حافظه هستند که همگی از یک نوع و با یک نام و با شماره های خانه متفاوت(اندیس آرایه) هستند.

روش تعریف آرایه یک بعدی:

;[طول آرایه]نام آرایه     نوع آرایه

روش تعریف یک آرایه یک بعدی که به آن لیست (List) هم میگویند به صورت فوق است. در این روش دقت میکنیم که نوع آرایه می تواند از انواع داده ها(Data Types) قابل استفاده در زبان ++C باشد و نام انتخابی برای آرایه چون یک شناسه است، باید از قوائد تولید شناسه در زبان ++C تبعیت کند.

نکته: محل هر عضو از آرایه توسط شماره(اندیس) که در [] می گذاریم، مشخص میشود.

نکته: اندیس شروع آرایه در زبان ++C صفر میباشد یعنی شماره گذاری خانه های آرایه از 0 شروع میشود و خانه ی اول آرایه اندیس 0 دارد.

نکته: در زبان ++C اسم آرایه آدرس خانه ی اول آرایه است.