0
Follow
0
View

# What's wrong with this quicksort?(*´I '*)

csxpeter0 注册会员
2023-02-27 22:36

There are two problems that cause errors in your code:

1. In the partition function, you use a pointer p and assign a dynamically allocated memory address to it on the final return. But when allocating memory, you use new int(sizeof(num)/sizeof(num[0])), which allocates memory size 4 instead of the array size 2 you want. So on return, you only returned the first two elements of the num array, causing the array to not segment properly. You can solve this problem by simply returning the space allocated by a new int[2].

## 2. When you use srand, you should only use it once at the beginning of the program. When you call it recursively, you call srand every time, resulting in a less random number. To avoid this, you can use the srand function at the beginning of the program and then use L+ rand() %(R-L+1) to generate a random number when you call rand to generate a random number. This avoids generating the same random number repeatedly.

Here is the modified code, you can refer to:

``````#include
#include
#include
using namespace std;

void swap(int arr[], int a, int b);
int* partition(int arr[], int L, int R);
void quickSort(int arr[], int L, int R)
{
if(L < R)
{
float a = (float)rand() / RAND_MAX;
swap(arr, L + (int)(a*(R-L+1)), R);
int* q = partition(arr, L, R);
quickSort(arr, L, q[0]-1);
quickSort(arr, q[1]+1, R);
delete[] q;
}
}

int* partition(int arr[], int L, int R)
{
int less = L - 1;
int more = R;
while(L < more)
{
if(arr[L] < arr[R])
{
swap(arr, ++less, L++);
}
else if(arr[L] > arr[R])
{
swap(arr, --more, L);
}
else
{
L++;
}
}
swap(arr, more, R);
int* p = new int[2];
p[0] = less + 1;
p[1] = more;
return p;
}

void swap(int arr[], int a, int b)
{
int tmp = arr[a];
arr[a] = arr[b];
arr[b] = tmp;
}

int main()
{
int arr[] = {3, 2, 5, 8, 1, 2, 3, 1, 4, 3, 7, 1};
int num = sizeof(arr) / sizeof(int);
srand(time(NULL));
quickSort(arr, 0, num - 1);
for(int i = 0; i < num; i++)
{
cout << arr[i] << " ";
}
cout << endl;
return 0;
}

``````
frrsterdl1 注册会员
2023-02-27 22:36

I feel that the pointer p is pointing to NULL, but I don't know how to change

dengrenjun 注册会员

Publish Time
2023-02-27 22:36
Update Time
2023-02-27 22:36