我正在使用选择枢轴的不同方法进行快速排序,我没有在代码中看到任何问题,这些功能在分离测试时可以正常工作,但是当我将它们放在一起时,大多数情况下它们都无法工作。

我尝试将文件移动到另一个路径,并更改我访问数组的方式。

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将超出范围(负数)怎么办,也可以在此处更改条件。

根据我的意见,上述区域正在引起问题。

调试愉快!

07-27 13:43