#include<iostream>
using namespace std;
int* ar; // ** Указатель на int
int swaps = 0, compares = 0;
void funcprint(int arr[], int size)
{
for (int i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
void quickSort(int a[], long N) {
cout << "N=" << N << " ";
if (N < 2) {
cout << '\n';
return;
}
for (int k = 0; k < N; k++)
cout << a[k] << " ";
cout << "; ";
long i = 0, j = N - 1;
int p = a[N >> 1];
while (i < j) {
while (a[i] < p) { compares++; i++; }
while (a[j] > p) { compares++; j--; }
if (i < j) {
swaps++;
swap(a[i++], a[j--]);
}
}
cout << "p=" << p
<< " j=" << j
<< " i=" << i << " 1: ";
for (int k = 0; k <= j; k++)
cout << a[k] << " ";
cout << "; 2: ";
for (int k = i; k < N; k++)
cout << a[k] << " ";
cout << "; ";
funcprint(ar, 9); // Выводить массив с первого элемента в текущем узле рекурсии
quickSort(a, j);
quickSort(a + i, N - i);
}
int main() {
int a[10] = { 5,2,1,9,1,4,6,2,10 };
ar = a; // ** Установить указатель на первый элемент массива
int N = 9;
quickSort(a, N);
funcprint(a, N);
cout << "compares=" << compares << endl;
cout << "swaps=" << swaps << endl;
}
1 ответ
В соответствии с algorithm quicksort Хоара из википедии, который, похоже, вы пытаетесь реализовать, функция, написанная на С++ с тем же прототипом, что и ваша, может выглядеть вот так:
void quickSort (int a[], long N) {
if (N < 2)
return;
long i = 0, j = N - 1;
int p = a[N >> 1];
while (i < j) {
while (a[i] < p) i++;
while (a[j] > p) j--;
if (i < j)
swap(a[i++], a[j--]);
}
quickSort(a, j);
quickSort(a + i, N - i);
}
Обратите внимание на if (N < 2) return;
в ее начале. Это позволяет избежать проверок перед рекурсивными вызовами, которые вы делаете в своем коде.
Замечу также, что перестановка элементов в соответствии с текстом алгоритма из википедии должна записываться именно так: if (i < j) swap(a[i++], a[j--]);
а не как у вас:
if (i <= j)
swap(a[i], a[j]);
Update for debugging print
int* ar; // ** Указатель на int
void quickSort(int a[], long N) {
cout << "N=" << N << " ";
if (N < 2) {
cout << '\n';
return;
}
for (int k = 0; k < N; k++)
cout << a[k] << " ";
cout << "; ";
long i = 0, j = N - 1;
int p = a[N >> 1];
while (i < j) {
while (a[i] < p) i++;
while (a[j] > p) j--;
if (i < j)
swap(a[i++], a[j--]);
}
cout << "p=" << p
<< " j=" << j
<< " i=" << i << " 1: ";
for (int k = 0; k <= j; k++)
cout << a[k] << " ";
cout << "; 2: ";
for (int k = i; k < N; k++)
cout << a[k] << " ";
cout << "; ";
funcprint(ar, 9); // Выводить массив с первого элемента в текущем узле рекурсии
quickSort(a, j);
quickSort(a + i, N - i);
}
int main() {
int a[10] = { 5,2,1,9,1,4,6,2,10 };
ar = a; // ** Установить указатель на первый элемент массива
int N = 9;
quickSort(a, N);
funcprint(a, N);
}
Я исправил N из вашего кода на 9 (может и еще какие-то мелкие правки внес)
Результат запуска
avp@avp-desktop:~/avp/hashcode$ g++ ttt.cpp -g
avp@avp-desktop:~/avp/hashcode$ ./a.out
N=9 5 2 1 9 1 4 6 2 10 ; p=1 j=1 i=2 1: 1 1 ; 2: 2 9 5 4 6 2 10 ; 1 1 2 9 5 4 6 2 10
N=1
N=7 2 9 5 4 6 2 10 ; p=4 j=2 i=3 1: 2 2 4 ; 2: 5 6 9 10 ; 1 1 2 2 4 5 6 9 10
N=2 2 2 ; p=2 j=0 i=1 1: 2 ; 2: 2 ; 1 1 2 2 4 5 6 9 10
N=0
N=1
N=4 5 6 9 10 ; p=9 j=2 i=2 1: 5 6 9 ; 2: 9 10 ; 1 1 2 2 4 5 6 9 10
N=2 5 6 ; p=6 j=1 i=1 1: 5 6 ; 2: 6 ; 1 1 2 2 4 5 6 9 10
N=1
N=1
N=2 9 10 ; p=10 j=1 i=1 1: 9 10 ; 2: 10 ; 1 1 2 2 4 5 6 9 10
N=1
N=1
1 1 2 2 4 5 6 9 10
avp@avp-desktop:~/avp/hashcode$
Кстати, интересно что уже после третьего вызова массив оказывается отсортированным, но алгоритму требуется сделать еще 10 вызовов, чтобы установить этот факт.
-
Комментарии не предназначены для расширенной дискуссии; разговор перемещён в чат. – Grundy♦ 26 фев в 15:53
for (int x : a) { std::cout << x << " "; } std::cout << "\n";}
– KoVadim 23 фев в 10:11