Блог

У меня есть следующий алгоритм быстрой сортировки:

 int quicksort(int data[], size_t n, int amp;counter)
// Library facilities used: cstdlib
{
    
    size_t pivot_index; // Array index for the pivot element
    size_t n1;          // Number of elements before the pivot element
    size_t n2;          // Number of elements after the pivot element

    if (n > 1)
    {
        // Partition the array, and set the pivot index.
        partition(data, n, pivot_index, counter);
        

        // Compute the sizes of the subarrays.
        n1 = pivot_index;
        n2 = n - n1 - 1;

        // Recursive calls will now sort the subarrays.
        quicksort(data, n1, counter);
        quicksort((data   pivot_index   1), n2, counter);
    }

    return counter; 
}
void partition(int data[], size_t n, size_tamp; pivot_index, int amp;counter){
    
    int pivot = data[0]; 
    size_t too_big_index = 1;
    size_t too_small_index = n - 1;

    while (too_big_index <= too_small_index)
    {
        
        while (  counter amp;amp; (too_big_index < n) amp;amp; (data[too_big_index] <= pivot)) too_big_index  ;
     
        while (  counter amp;amp; data[too_small_index] > pivot  ) too_small_index--;
       
        counter  ;
        if (too_big_index < too_small_index) swap(data[too_big_index], data[too_small_index]);
    };

    pivot_index = too_small_index;
    data[0] = data[pivot_index];
    data[pivot_index] = pivot;

    
}

  

Я добавил три приращения счетчика в функцию разбиения, однако счетчик выдает значение 32019997 при использовании отсортированного массива из 8000 элементов я использую сводку самого левого элемента (я знаю, что это дает мне ужасный наихудший случай с точки зрения отсортированного массива)если я не ошибаюсь, разве наихудший случай не должен быть n ^ 2, т.е. 64000000? Поэтому я предполагаю, что способ подсчета сравнений неверен, но я не уверен, как.