Блог

Я хотел бы изменить указанный алгоритм быстрой сортировки, чтобы выбрать выбор поворота как 1) Случайный элемент в массиве. 2) Медиана первого среднего и последнего элементов в массиве. ==== ОБНОВЛЕНИЕ ==== Также, как я могу реализовать механизм синхронизации для определения времени выполнения для каждого алгоритма?

 void QuickSort1(long *L, int first, int last)
{
   int SplitPoint;  /* Value to Split list around */

   if( first < last )
   {
      /* Use first element as pivot (for splitting) */
      SplitPoint = first;                 /* assign SplitPoint to 1st index */
      Split(L, first, last, amp;SplitPoint); /* Split List around SplitPoint */
      QuickSort1(L, first, SplitPoint-1);  /* Sort 1st section of list */
      QuickSort1(L, SplitPoint 1, last);   /* Sort 2nd section of list */
   }
}

void Split(long *L, int first, int last, int *SplitPoint)
/* Splits a list around SplitPoint such that all values to the left of
   SplitPoint are < than SplitPoint and all values to the right of
   SplitPoint are >= SplitPoint */
{
   int x;            /* Key */
   int unknown;      /* index of unknown value */

   x = L[*SplitPoint];   /* assign x to value at SplitPoint */
   Swap( amp;L[*SplitPoint], amp;L[first] ); 
   *SplitPoint = first; 

   /* Loop walks through unknown portion of list */
   for ( unknown = first 1; unknown <= last;   unknown)
   {
      /* If unknown value is < SplitPoint Value, then: */
#ifdef TAKE_COUNT
         comparison_count  ;
#endif
      if( L[unknown] < x ) {
            (*SplitPoint);                     /* SplitPoint is incremented */
         Swap( amp;L[*SplitPoint], amp;L[unknown] ); /* values are swapped*/
      }
   }
   /* Original value which was being split upon is swapped with the current
      SplitPoint to put it in correct position */
   Swap( amp;L[first], amp;L[*SplitPoint] );
}

int FindMedian(long *L, int A, int B, int C)
/* Receives array and three respective indices in the array. */
/* Returns the index of the median. */
{
   if (L[A] < L[B])
     if (L[B] < L[C])       /*  A < B < C  */
       return (B);
     else
       if (L[A] < L[C])         /*  A < C < B  */
     return (C);
       else
     return (A);            /*  C < A < B  */
   else
     if (L[A] < L[C])           /*  B < A < C  */
       return (A);
     else
       if (L[B] < L[C])     /*  B < C < A  */
     return (C);
       else
     return (B);            /*  C < B < A  */
}

void Swap(long *a, long *b)
/* This function uses call by reference to switch two elements.*/
{
   long temp;    /* temporary variable used to switch. */

   temp = *a;   /* temp = 1st # */
   *a = *b;     /* 1st # = 2nd # */
   *b = temp;   /* 2nd # = temp */
}
 

Как я могу изменить это для перечисленных вариантов поворота? Они также должны быть добавлены в качестве дополнительных опций меню для программы.

Секрет в том, что вы всегда выбираете первый элемент в массиве в качестве точки поворота. Если вы хотите использовать другой элемент, что является очень хорошей идеей, если входные данные уже отсортированы или (общий случай) в основном отсортированы с добавлением нескольких новых элементов, замените его первым элементом. Теперь pivot является первым элементом.

С учетом этого понимания задача должна стать очень простой. Чтобы выбрать случайный pivot, сгенерируйте случайное число от ) до N-1 и поменяйте местами с первым элементом. Чтобы взять медиану из трех, напишите довольно беспорядочный, но прямой набор if … операторы else.