Quick sort некорректно сортирует. Где ошибка?

Question

[Freezar]

Пример из книги Томаса Кормена.

void swap(int& a, int& b)
{
	int tmp = a;
	a = b;
	b = tmp;
}

int partition(int arr[], int p, int r)
{
	int x = arr[r - 1];
	int i = p - 1;

	for (int j = p; j < r - 1; ++j) {
		if (arr[j] <= x) {
			++i;
			swap(arr[i], arr[j]);
		}
	}
	swap(arr[i + 1], arr[r - 1]);

	return i + 1;
}

void quickSort(int arr[], int p, int r)
{
	if (p < r) {
		int q = partition(arr, p, r);

		quickSort(arr, p, q - 1);
		quickSort(arr, q + 1, r);
	}
}

Answer 1

[jcmvbkbc]

Неправильно выставлены границы интервала в quickSort, должно быть так:

void quickSort(int arr[], int p, int r)
{
	if (p < r) {
		int q = partition(arr, p, r);

		quickSort(arr, p, q);
		quickSort(arr, q + 1, r);
	}
}

Тестовое приложеньице:

int main()
{
        for (int n = 2; n <= 10; ++n) {
                int arr[10];
                for (int i = 0; i < n; ++i)
                        arr[i] = i;
                printf("n = %d\n", n);
                do {
                        int sort[10];

                        memcpy(sort, arr, sizeof(arr));
                        quickSort(sort, 0, n);
                        for (int i = 1; i < n; ++i)
                                if (sort[i] < sort[i - 1])
                                        printf("!\n");
                } while (std::next_permutation(arr, arr + n));
        }
        return 0;
}

Comments

[Freezar]

Спасибо!