Блог

Гибридная сортировка:
индекс элемента массива A от int p до int r, мы сначала сортируем [] методом быстрой сортировки, pivot изначально помещается в конец массива, затем рекурсивно вызываем быструю сортировку, однако, поскольку количество элементов в массиве меньше 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 = %dn",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 amp;amp; 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 amp;amp; 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

}

 

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

 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) amp;amp; 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);
}