Объединить вставку сортировки с функцией быстрой сортировки

Question

Гибридная сортировка:
Индекс элемента массива A от int p до int r, мы первоначально сортируем A [] методом быстрой сортировки, стержень первоначально помещается в конец массива,затем рекурсивно вызвать быструю сортировку, однако, поскольку количество элементов в массиве меньше t, тогда мы прекращаем вызывать быструю сортировку и сортируем оставшуюся часть элемента путем сортировки вставкой, гибридная функция должна возвращать только время вызова сортировки вставкой.Основная функция выводит время вызова вставки сортировки.

Я пишу этот код несколько раз, но всегда такой беспорядок в отношениях функций, огромное количество информации об ошибках, которую я не могу диагностировать.и я не знаю, почему на практике это более быстрая реализация, чем в сочетании с randomized_quick_sort.Спасибо

#include<stdio.h>
#include<stdlib.h>
// hybrid quick sort
int hybridsort(int A[], int p, int q, int t);

int  main() {
  int n = 9, t = 3;
  int A[9] = {1, 8, 6, 3, 2, 7, 4, 9, 10};

  for(int i = 0; i < 9; i++)printf(" %d", A[i]);
  printf("\n");

  int res = hybridsort(A, 0, n - 1, t);// rest
  printf("No. of calls = %d\n",res);

  for(int i = 0; i< 9; i++)printf("%d", A[i]);
  printf("\n");

  return 0;
}
int hybridsort(int A[], int p, int r, int t){
  int n, count;
  count = 0;
  int i, j, key;
  n = p - r + 1;
  // if No.elements < t, # of insertion sort gets called
  if(n >= t && p > r ){
      quicksort(A, p, r);
    }
    else{
      // insertionsort
      count = count + 1;
      for(j = 1; j < 6; j++){
      key = A[j];
      i = j - 1;
      while(i > -1 && A[i] > key){
      A[i + 1] = A[i];
      i = i - 1;
    }
    A[i + 1] = key;
   }

 }
}

return count;
}
void quicksort(int A[], int p, int r){
  int q ;
  if(p < r){

    q = partition(A, p,r);
    quicksort(A, p, q - 1);
    quicksort(A, q + 1, r);
  }
}

int partition(int A[], int p, int r){
  int x, i, j, tmp;
  x = A[r];//pivot
  i = p - 1;
  for(j = p; j < r; j++){
    if(A[j] <= x){
      i += 1;
      tmp = A[i];
      A[i] = A[j];
      A[j] = tmp;
    }

  }
  tmp = A[i + 1];
  A[i + 1] = A[r];
  A[r] = tmp;
  return i + 1 ;// pivot index position after sorting

}

Answer 1

Пример гибридной быстрой + вставка сортировки. Основная программа вызывает QuickSort (), которая вызывает InsertionSort для размеров подмассива <= 32. </p>

void InsertionSort(int a[], size_t lo, size_t hi)
{
size_t i = lo+1;
size_t j;
int t;
    while(i <= hi){
        t = a[i];
        j = i;
        while((j > lo) && a[j-1] > t){
            a[j] = a[j-1];
            j -= 1;
        }
    a[j] = t;
    i += 1;
    }
}

void QuickSort(int a[], size_t lo, size_t hi)
{
    if(lo >= hi)
        return;
    if((hi-lo) < 32){
        InsertionSort(a, lo, hi);
        return;
    }
    int pivot = a[lo + (hi - lo) / 2];
    int t;
    size_t i = lo - 1;
    size_t j = hi + 1;
    while(1)
    {
        while (a[++i] < pivot);
        while (a[--j] > pivot);
        if (i >= j)
            break;
        t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
    QuickSort(a, lo, j);
    QuickSort(a, j + 1, hi);
}