0

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

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

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

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

Функция 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;
} 
2
  • Добавьте информацию о проблеме. Алгоритм работает не совсем верно - а что именно не так? Что ожидаете и что получаете? 15 фев 2021 в 10:36
  • @ЮрийКозлов Прошу прощения. Алгоритм сортирует данные, но делает это не всегда верно или не всегда до конца. Соответственно может массив может быть отсортирован, за исключением пары(в значении "Два однородных предмета, вместе употребляемые и составляющие целое.") элементов. А бывает когда этих пар более, чем 1.
    – slime love
    15 фев 2021 в 10:42

1 ответ 1

0

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

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

  2. Пункт 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;
} 

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.