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

تابع روش مرتب سازی گورزاد (Gnome Sort) که بدترین عملکرد آن O(n²)  است:

void gnomeSort(int arr[], int n)
{
    int i = 0, temp;
       
    while( i < n )
    {
                  
    if ( i == 0 || arr [i - 1] <= arr[i] )
        i++;
                  
        else
        {
            temp = arr[i];
            arr[i] = arr[i - 1];
            arr[--i] = temp;
        }
                  
    }
                 
}

//end

تابع مرتب سازی شل یا پوسته ای (Shell Sort) در C++

تابع مرتب سازی شل یا پوسته ای (Shell Sort) که بدترین عملکرد آن O(nlog²n)  است:

void shellsort(int A[],int max)
{
     int stop,swap,limit,temp;
   int x=(int)(max/2)-1;
   while(x>0)
   {
        stop=0;
      limit=max-x;
      while(stop==0)
      {
           swap=0;
         for(int k=0;k<limit;k++)
         {
              if(A[k]>A[k+x])
            {
                 temp=A[k];
               A[k]=A[k+x];
               A[k+x]=temp;
               swap=k;
            }
         }
         limit=swap-x;
         if(swap==0)
              stop=1;
      }
      x=(int)(x/2);
   }
}

//end

تابع الگوریتم مرتب سازی شانه ای (Comb Sort) در C++

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

void combsort(int *arr, int n)
{
    float shrink_factor = 1.247330950103979;
    int gap = n, swapped = 1, swap, i;
 
    while ((gap > 1) || swapped)
    {
        if (gap > 1)
            gap = gap / shrink_factor;
 
        swapped = 0;
        i = 0;
 
        while ((gap + i) < n)
        {
            if (arr[i] - arr[i + gap] > 0)
            {
                swap = arr[i];
                arr[i] = arr[i + gap];
                arr[i + gap] = swap;
                swapped = 1;
            }
            ++i;
        }
    }
}

//end

تابع روش مرتب کردن کوکتل (Cocktail Sort) در C++

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

void cocktail_sort (int Arr[], int n)
{
    int left = 0, right = n;
    bool finished;
    do
    {
        finished = true;
        --right;
        for (int i = left; i < right; i++)
            if (Arr[i] > Arr[i+1]) {
                swap(Arr[i], Arr[i+1]);
                finished = false;
            }
        if (finished) return;
        finished = true;
        for (int i = right; i > left; i--)
            if (Arr[i] < Arr[i-1]) {
                swap(Arr[i], Arr[i-1]);
                finished = false;
            }
        ++left;
    } while (!finished);
}


//end

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

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

void fnSortHeap(int arr[], int ubound)
{
    int i,o;
    int lChild, rChild, mChild, root, temp;
    root = (ubound-1)/2;
    for(o=root;o>=0;o--)
    {
        for(i=root;i>=0;i--)
        {
            lChild = (2*i)+1;
            rChild = (2*i)+2;
            if ((lChild <= ubound) && (rChild <= ubound))
            {
                if(arr[rChild] >= arr[lChild])
                    mChild = rChild;
                else
                    mChild = lChild;
            }
            else
            {
                if(rChild > ubound)
                    mChild = lChild;
                else
                    mChild = rChild;
            }
            if (arr[i] < arr[mChild])
            {
                temp = arr[i];
                arr[i] = arr[mChild];
                arr[mChild] = temp;
            }

        }

    }

    temp = arr[0];
    arr[0] = arr[ubound];
    arr[ubound] = temp;
    return;
}


//end

تابع مرتب سازی شمارشی (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