我正在使用选择枢轴的不同方法进行快速排序,我没有在代码中看到任何问题,这些功能在分离测试时可以正常工作,但是当我将它们放在一起时,大多数情况下它们都无法工作。
我尝试将文件移动到另一个路径,并更改我访问数组的方式。
void quick_sort(uint32_t arr[], int first, int last, int pivot_opt)
{
int i, j;
uint32_t pivot = pivot_select(arr, last, pivot_opt);
i = first;
j = last;
do
{
comparations_count++;
while (arr[i] < pivot) i++; // Counting elements smaller than pivot
comparations_count++;
while (arr[j] > pivot) j--; // Counting elements greater than pivot
comparations_count++;
if (i <= j)
{
exchanges_count++;
swap(&arr[i++], &arr[j--]); // Placing smaller elements in the left, and greater elements in the right without touching the pivot
}
comparations_count++;
} while (i <= j);
comparations_count++;
if (first < j)
quick_sort(arr, first, j, pivot_opt); // Sorting smaller elements of array
comparations_count++;
if (i < last)
quick_sort(arr, i, last, pivot_opt); // Sorting greater elements of array
}
uint32_t pivot_select(uint32_t arr[], int last, int pivot_opt)
{
uint32_t pivot = 0;
int random_index = 0;
switch (pivot_opt)
{
case 0:
pivot = arr[last]; // Choosing the pivot as the last element in the array
break;
case 1:
random_index = rand()%(last); // Choosing the pivot as a random element of array
pivot = arr[random_index];
break;
case 2:
pivot = median(arr, last); // Choosing the pivot as avg of three random indexes of the array
break;
default:
break;
}
return pivot;
}
uint32_t median(uint32_t arr[], int n)
{
if (n <= 3)
{
return arr[0]; // If the array have 3 or less elements, choose as pivot first element
}
else
{
int index[3] = {0}; // Index of 3 elements of original array
int last_index = 0; // Last chosen index, to verify if index was selected
int i = 0;
while(i < 3) // Selecting 3 random index
{
int current_index = (rand()%(n));
if (current_index == last_index)
i--;
else
{
index[i++] = current_index;
last_index = current_index;
}
}
uint32_t array[3] = {arr[index[0]], arr[index[1]], arr[index[2]]}; // Creating array with the elements on random indexes
insertion_sort(array, 3); // Sorting the array
return array[1]; // Returning the pivot as the middle element of array
}
}
我在中位数函数上遇到此错误
Program received signal SIGSEGV, Segmentation fault.
0x0000555555555546 in median (arr=<error reading variable: Cannot access memory at address 0x7fffff7fefd8>, n=<error reading variable: Cannot access memory at address 0x7fffff7fefd4>) at /media/storage/Codes/Data Structure/Recursive_Sorting/main.c:107
107 {
我把所有正在使用的库都放了,所以我不会错过任何一个。
测试代码:
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <sys/time.h>
#include <time.h>
#define size 1000
uint32_t comparations_count;
uint32_t exchanges_count;
int main(int argc, char** argv)
{
uint32_t array[size];
fill(array, size);
permute_array(array, size);
comparations_count = 0;
exchanges_count = 0;
quick_sort(array, 0, size-1, 2);
return 0;
}
void fill(uint32_t arr[], uint32_t n)
{
for (size_t i = 0; i < n; i++) // Filling the array in ascending order
arr[i] = i;
}
void swap(uint32_t *a, uint32_t *b)
{
// Swapping two elements
uint32_t t = *a;
*a = *b;
*b = t;
}
void permute_array(int a[], size_t n)
{
// Adapted from:
// https://www.geeksforgeeks.org/shuffle-a-given-array-using-fisher-yates-shuffle-algorithm/
srand(time(NULL)); // Init random seed
for (size_t i = n - 1; i > 0; i--) // Permute array
{
size_t j = rand() % (i+1); // Pick a random index from 0 to i
swap(&a[i], &a[j]); // Swap arr[i] with the element at random index
}
}
void insertion_sort(uint32_t arr[], size_t n)
{
uint32_t current_index = 0;
uint32_t current_value = 0;
for (size_t i = 1; i < n; i++) {
current_index = i;
current_value = arr[i];
while (current_index > 0) {
if (current_value < arr[current_index - 1]) {
swap(&arr[current_index], &arr[current_index-1]);
current_index--;
}else { break; }
}
}
}
最佳答案
让我们从这个开始:
while (arr[i] < pivot) i++;
如果所有元素都小于轴,该怎么办,将条件更改为
while(arr[i] < pivot && i <= j) i++;
考虑一下这一点:
while (arr[j] > pivot) j--;
如果所有元素都大于支点,那么j将超出范围(负数)怎么办,也可以在此处更改条件。
根据我的意见,上述区域正在引起问题。
调试愉快!