Ошибка сегментации при реализации быстрой сортировки в C - PullRequest
Новая
       2

Ошибка сегментации при реализации быстрой сортировки в C

0 голосов
/ 26 октября 2019

Я пытаюсь выполнить код быстрой сортировки, упомянутый в книге Структуры данных с использованием C от Reema Thareja.

Проблема в том, что я не могу получить отсортированный массив в качестве вывода. Вместо этого, когда я добавляю элементы в массив, экран вывода исчезает, и при повторном запуске кода я получаю следующее:

Output

Я использую версию Turbo C ++:3.2 Компилятор 

#include <stdio.h>
#include <conio.h>
void quicksort(int arr[],int l,int r);
void main()
{
    int arr[10],l,r,i,n;
    printf("Enter Array size: ");
    scanf("%d",&n);
    printf("Enter Elements: ");
    for(i=0;i<n;i++)
    {
        scanf("%d",&arr[i]);
    }
    quicksort(arr,0,n-1);
    printf("The Sorted Array is: ");
    for (i = 0; i < n; i++)
    {
        printf("%d",arr[i]);
    }
    getch();
}
int partition(int arr[],int l,int r)
{
    int left,right,temp,loc,flag;
    loc=left=l;
    right=r;
    flag=0;
    while(flag!=1)
    {
        while((arr[loc]<=arr[right]) && loc!=right)
        {
            right--;
        }
        if(loc==right)
        {
            flag=1;
        }
        else if(arr[loc]>arr[right])
        {
            temp=arr[loc];
            arr[loc]=arr[right];
            arr[right]=temp;
            loc=right;
        }
        if(flag!=1)
        {
            while((arr[loc]>=arr[left])&& (loc!=left))
            {
                left++;
            }
            if(loc==left)
            {
                flag=1;
            }
            else if(arr[loc]<arr[left])
            {
                temp=arr[loc];
                arr[loc]=arr[left];
                arr[left]=temp;
                loc=left;
            }
        }
    }
    return loc;
}
void quicksort(int arr[],int l,int r)
{
    int loc;
    if(l!=r)
    {
        loc=partition(arr,l,r);
        quicksort(arr,l,loc-1);
        quicksort(arr,loc+1,r);
    }
}

1 Ответ

2 голосов
/ 26 октября 2019

Рассмотрим эту функцию: 

void quicksort(int arr[], int l, int r)
{
    int loc;
    if(l!=r)
    {
        loc=partition(arr,l,r);
        quicksort(arr,l,loc-1);
        quicksort(arr,loc+1,r);
    }
}

Здесь наш базовый случай равен l==r. Но если мы добавим оператор печати (и некоторый интервал) 

void quicksort(int arr[], int l, int r)
{
    if (l != r)
    {
        printf("left: %d, right: %d\n", l, r);
        fflush(stdout);
      //^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

        int loc = partition(arr, l, r);
        quicksort(arr, l, loc - 1);
        quicksort(arr, loc + 1, r);
    }
}

и вызовем его с 

int arr[] = {4, 8, 1, 4, 5, 1, 8, 5, 7};
int arr_len = 9;
quicksort(arr, 0, arr_len - 1);

, мы получим следующий вывод: 

left: 0, right: 8
left: 0, right: 1
left: 0, right: -1
exited, segmentation fault

К сожалению: left было 0 и right было -1, и мы вызвали partition(arr, 0, -1);, который немедленно делает доступ к памяти вне пределов с помощью оператора arr[right] => arr[-1].

if (l < r) былВероятно, цель здесь: 

void quicksort(int arr[], int l, int r)
{
    if (l < r)
    {
        int loc = partition(arr, l, r);
        quicksort(arr, l, loc - 1);
        quicksort(arr, loc + 1, r);
    }
}

, которая позволяет нам правильно установить базовый вариант для рекурсии.

Помимо этой ошибки, я рекомендую использовать пробел между операторами, выбирать значимые имена иизбегая ненужных переменных. Примером этого является начало функции partition. Как написано, это: 

int partition(int arr[],int l,int r)
{
    int left,right,temp,loc,flag;
    loc=left=l;
    right=r;
    flag=0;
// ...

Но l и r просто переназначаются на left и right и затем остаются неиспользованными для оставшейся части функции. Запись в следующем виде: 

int partition(int arr[], int left, int right)
{
    int temp;
    int loc = left;
    int flag = 0;
// ...

более понятна, но даже здесь мы должны переместить tmp (используется для перестановок) в отдельную функцию или, по крайней мере, поместить ее в блок, где она используется, чтобы избежать устареванияценность ошибок. Мы должны #include <stdbool.h>, потому что это то, чем на самом деле является int flag (или использовать ранние возвраты, чтобы полностью исключить переменную) и улучшить имя переменной loc (на самом деле это точка, на которую мы делим целые числа): 

int partition(int arr[], int left, int right)
{
    int pivot = left;
    bool flag = false; // or remove this completely in favor of `return`
// ...

Это намного чище.

Кроме того, void main должно быть int main и использовать явное return 0. Я рекомендую использовать современный компилятор и среду разработки и включить все предупреждения: 

gcc quicksort.c -Wall -Wextra -Werror -O2 -std=c99 -pedantic

Это выявляет неиспользуемые переменные в main, среди прочего, и обычно уменьшает болевые точки.

ТакжеЯ рекомендую прочитать , как отлаживать небольшие программы , которые дадут вам инструменты (как концептуальные, так и программные), необходимые для изучения, и расскажут о программах для локализации ошибок.

...