Блог

Я пытаюсь реализовать гибрид сортировки слияния и вставки. Когда размер подмассива становится ниже порогового значения, он должен переключиться на сортировку вставки. Однако я пробовал использовать множество массивов разной длины и разной пороговой величины, и в большинстве случаев нет никакой заметной разницы, кроме 2-3 меньших сравнений. Мне сказали, что переключение на сортировку вставки для массива меньшего размера очень помогло бы.

Я делаю это неправильно?

 #include <iostream>


int comparisons = 0;
int swaps = 0;

void mergesort(int x[], int l, int r);
void insertionSort(int x[],int start, int end);

int main() {
  int x[] = {9,5,1,4,3,10,29,69,5,9,11,19,21,69,0,2,3,4,5,11,111,96,25,32,21,2,12,3,52,55,23,32,15,15,14,13,9,5,1,4,3,10,29,69,5,9,11,19,21,69,0,2,3,4,5,11,111,96,25,32,21,2,12,3,52,55,23,32,15,15,14,13,};

  // insertionSort(x,10);
  int sizeX= sizeof(x)/sizeof(x[0]) ;
  mergesort(x, 0, sizeX-1);

  for(int i =0;i<sizeX;i  ){
    std::cout << x[i] << " ";
  }
  // std::cout << "nSWAPS: " << swaps;
  std::cout << "nCOMPARISONS: " << comparisons;
}


void insertionSort(int arr[], int start,int end)
{
    int i, key, j;
    for (i = start  1 ; i < end; i  )
    {
        key = arr[i];
        j = i - 1;
 
        /* Move elements of arr[0..i-1], that are
        greater than key, to one position ahead
        of their current position */
        while (j >= 0 amp;amp; arr[j] > key)
        {
            comparisons  ;

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

void insertionSort2(int x[],int start, int end){
  for(int i =start; i < end;i  ){
    for (int j= i; j!= 0;j--){
      comparisons  ;

      if(x[j] < x[j-1]){
        int temp = x[j-1];
        x[j-1] = x[j];
        x[j] = temp;
        swaps  ;
      }
      else{
        break;
      }
    }
  }
}


void mergesort(int x[], int l, int r) {
  if (l >= r)
    return;

  int mid = (l   r) / 2;

  if(r - l  < 3){
    insertionSort(x, l,r 1);
  }else{
    mergesort(x, l, mid);
    mergesort(x, mid   1, r);

    int i = l; 
    int j = mid   1; 
    int k = 0; 

    int tmp[r - l   1];

    while (i <= mid amp;amp; j <= r) {
      comparisons  ;
      if (x[i] >= x[j]) {
        tmp[k] = x[j];
        j  ;
      } else {
        tmp[k] = x[i];
        i  ;
      }
      swaps  ;
      k  ;
    }

    while (i <= mid) {
      tmp[k] = x[i];
      i  ;
      k  ;
    }

    while (j <= r) {
      tmp[k] = x[j];
      j  ;
      k  ;
    }

    for (i = 0; i < k; i  ) x[l   i] = tmp[i];
  }
}