Всем доброго времени суток. Нашел алгоритм быстрой сортировки в одной из книжек по Алгоритмам и структурам данных. Решил реализовать его на 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;
}