quick sort c++. С каунтерами сравнений и перестановок

Question

Всем доброго времени суток. Нашел алгоритм быстрой сортировки в одной из книжек по Алгоритмам и структурам данных. Решил реализовать его на C++. Но возникло пару проблем. Прошу помочь, т.к. тема для новичка не очень интуитивна.

Алгоритм работает не совсем верно, не очень понимаю в чем проблема.(Массив может быть отсортирован по итогам программы не верно. Одна или несколько пар значений могут находиться не на своих местах)
Хочу добавить переменные сравнения и перемещения.(Вопрос в том, как мне их правильно передать из функцию в функцию и где итерировать в цикле)

Массив заполняется случайными данными нужной(введенной с клавиатуры) величины.

Что бы была возможность отслеживать время выполнения пришлось вытащить все в отдельную подфункцию.

Функция quick_sort, где инициализация счетчиков и времени выполнения.

void quick_sort_main(int arr[], int left_tip, int right_tip) //Быстрая сортировка
{
    double t, time;
    t = clock();
    int count_of_comparisons = 0, count_of_permutations = 0;
    quick_sort(arr, left_tip, right_tip);
    cout << endl;
    cout << "Сортировка методом <<быстрой сортировки>> выполнена выполнена" << endl;
    cout << "Кол-во перестановок: " << count_of_permutations << endl;
    cout << "Кол-во сравнений: " << count_of_comparisons << endl;
    cout << "Отсортированный массив: " << endl;
    print_array(arr, right_tip);
    cout << endl;
    time = (clock() - t) * 1. / CLOCKS_PER_SEC;
    cout << "runtime = " << time << endl << endl << endl;
}

Сама функция, где и происходит сортировка

void quick_sort(int arr[], int left_tip, int right_tip)
{
    int i_left, j_right, x;
    i_left = left_tip;
    j_right = right_tip;
    x = arr[((left_tip + right_tip) / 2)];
    do
    {
        do
        {
            i_left++;
        } while (arr[i_left] < x);
        do
        {
            j_right--;
        } while (x < arr[j_right]);
        if (i_left <= j_right)
        {
            swap(arr[i_left], arr[j_right]);
            i_left++;
            j_right--;
        }
    } while (i_left <= j_right);
    if (left_tip < j_right)
    {
        quick_sort(arr, left_tip, j_right);
    }
    if (i_left < right_tip)
    {
        quick_sort(arr, i_left, right_tip);
    }
}

Вызов функции

int main()
{
    int massive_length;
    setlocale(LC_ALL, "Russian");
    cout << "Введите длину массива: ";
    cin >> massive_length;
    cout << endl;
    int* array = new int[massive_length];
    fill_massive(array, massive_length);
    cout << "Неотсортированный массив" << endl;
    print_array(array, massive_length);
    quick_sort_main(array, 0, massive_length);
    
    delete array;
}

Answer 1

В итоге удалось исправить проблему самостоятельно.

Ошибка в пункте один была вызвана неверным вызовом функции, немного переписал сортировку, уменьшил значение длины на 1 при вызове и все заработало(может это не то, но это помогло).

Пункт 2 реализовал через ссылки и указатели между функциями. Не уверен, что правильно вставил переменные.

void quick_sort_main(int arr[], int left_tip, int right_tip) //Быстрая сортировка
{
cout << "============================================" << endl;
double t, time;
t = clock();
int count_of_comparisons = 0, count_of_permutations = 0;
quick_sort(arr, left_tip, right_tip, &count_of_comparisons, &count_of_permutations);
cout << endl;
cout << "Сортировка методом <<быстрой сортировки>> выполнена выполнена" << endl;
cout << "Кол-во перестановок: " << count_of_permutations << endl;
cout << "Кол-во сравнений: " << count_of_comparisons << endl;
cout << "Отсортированный массив: " << endl;
//print_array(arr, right_tip);
cout << endl;
time = (clock() - t) * 1. / CLOCKS_PER_SEC;
cout << "runtime = " << time << endl << endl << endl;
}



void quick_sort(int arr[], int left_tip, int right_tip, int 
*p_count_of_comparisons, int *p_count_of_permutations)
{
int i_left, j_right, mid;
i_left = left_tip;
j_right = right_tip;
mid = arr[(left_tip + right_tip) / 2];
while (i_left <= j_right)
{
    while (arr[i_left] < mid)
    {
        i_left++;
        (*p_count_of_comparisons)++;
    }
    while (arr[j_right] > mid)
    {
        j_right--;
        (*p_count_of_comparisons)++;
    }
    if (i_left <= j_right)
    {
        swap(arr[i_left], arr[j_right]);
        i_left++;
        j_right--;
        (*p_count_of_permutations)++;
    }
}
if (left_tip < j_right)
{
    quick_sort(arr, left_tip, j_right, p_count_of_comparisons, 
p_count_of_permutations);
}
if (i_left < right_tip)
{
    quick_sort(arr, i_left, right_tip, p_count_of_comparisons, 
p_count_of_permutations);
}
}

main

int main()
{
    int array_length;
    setlocale(LC_ALL, "Russian");
    cout << "Введите длину массива: ";
    cin >> array_length;
    cout << endl;
    int* array = new int[array_length];
    fill_array(array, array_length);
    cout << "Неотсортированный массив" << endl;
    print_array(array, array_length);
    cout << endl << endl;
    int* copied_array = new int[array_length];
    copy_array(array, copied_array, array_length);
    quick_sort_main(copied_array, 0, (array_length-1));

    delete[] copied_array;
    delete[] array;
}

БЛОГ НА HUSL

quick sort c++. С каунтерами сравнений и перестановок

Ответы (1 шт):