このクイックソートアルゴリズムのピボット選択を変更するにはどうすればよいですか？

Question

リストのクイックソートアルゴリズムを変更してピボット選択肢を1）配列内のランダム要素として選択します。 2）配列中の最初と最後の要素の中央値。 ==== UPDATE ==== また、アルゴリズムごとにランタイムの時間を計るタイミングメカニズムを実装するにはどうすればよいですか？

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, &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(&L[*SplitPoint], &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(&L[*SplitPoint], &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(&L[first], &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 */ 
} 

リストされているピボットの選択肢について、これをどのように変更できますか。また、プログラムの追加メニューオプションとして追加する必要があります。

Answer 1

秘密は、常にピボットポイントとして配列の最初の要素を選択することです。入力がすでにソートされているか、あるいはほとんどの場合、少数の新しい要素が追加されてソートされている場合は、最初の要素と交換することをお勧めします。今ピボットは最初の要素です。

この洞察で、タスクは非常に簡単になります。ランダムピボットを選択するには、〜の乱数を生成してN-1にし、最初の要素と入れ替えます。 3の中央値をとるには、if ... elseステートメントの目障りではあるが単純なセットを書いてください。