sanManjiro
@sanManjiro

Как подсчитать кол-во обменных операций в быстрой сортировке?

У меня есть уже готовый код, где я подсчитываю кол-во операций в быстрой сортировке, переменная которая хранит в себе кол-во подсчета называется int numberExchangeOperations = 0;, я не уверен что я правильно подсчитываю все операции, поэтому не могли бы вы взглянуть на мой код и посмотреть что тут может быть не так?
void swap(int* array, int* b, int* numberExchangeOperations) {
	(*numberExchangeOperations) += 3;
	int temp = *array;
	*array = *b;
	*b = temp;
}
int partition(int array[], int low, int high, int* numberExchangeOperations) {
	(*numberExchangeOperations) += 2;
	int pivot = array[high];
	int i = (low - 1);

	for (int j = low; j <= high - 1; j++) {
		if (array[j] <= pivot) {
			(*numberExchangeOperations)++;
			i++;
			swap(&array[i], &array[j], numberExchangeOperations);
		}
	}
	swap(&array[i + 1], &array[high], numberExchangeOperations);
	return (i + 1);
}
void quick_sort(int array[], int low, int high, int* numberExchangeOperations) {
	if (low < high) {
		(*numberExchangeOperations) += 3;
		int pivot = partition(array, low, high, numberExchangeOperations);

		quick_sort(array, low, pivot - 1, numberExchangeOperations);
		quick_sort(array, pivot + 1, high, numberExchangeOperations);
	}
}
void quick_sort_main(int A[], int left_tip, int right_tip, int n) {
	int numberExchangeOperations = 0;
	unsigned int start_time = clock(); // начальное время
	quick_sort(A, left_tip, right_tip, &numberExchangeOperations);
	unsigned int end_time = clock(); // начальное время

	ofstream out;

	// COMMENT_OFSTREAM: Запись затраченного времени и кол-ва операций
	out.open("D:\\times.txt", ios::app);
	if (out.is_open()) {
		out << "Метод быстрой сортировки: " << endl;
		out << "   " << "-затраченое время: " << end_time << endl;
		out << "   " << "-кол-во обменных операций: " << numberExchangeOperations << endl;
	}
	else {
		cout << "Файл не может быть открыт!" << endl;
	}
	out.close();

	// COMMENT_OFSTREAM: Запись результата в файл.
	out.open("D:\\quicksort-method.txt", ios::out);
	if (out.is_open())
	{
		for (int i = 0; i < n; i++) {
			out << A[i] << " ";
		}
	}
	else {
		cout << "Файл не может быть открыт!" << endl;
	}
	out.close();
}

int main(void) {
...
	int countNum;	// ?: кол-во чисел
	int* array{ read_file() };				// ?: запись в ссылочный массив - ссылку на массив наших элементов из "input.txt"
	int N_method_shell = sizeof(array) / sizeof(array[0]);
	quick_sort_main(array, 0, N_method_shell, countNum); // ?: метод быстрой сортировки
...
}
  • Вопрос задан
  • 48 просмотров
Пригласить эксперта
Ответы на вопрос 1
wataru
@wataru Куратор тега C++
Разработчик на С++, экс-олимпиадник.
Да, не правильно. Вы от балды в случайных местах увеличиваете счетчик, на какие-то случайные числа (то 2, то 1, то 3?). Когда как вам надо же считать количество операций обмена.

Кстати, по английски этот обмен - "swap".
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы