Что означает ошибка сегментации (дамп памяти)?(код быстрой сортировки) - PullRequest
Новая
       28

Что означает ошибка сегментации (дамп памяти)?(код быстрой сортировки)

0 голосов
/ 12 февраля 2019

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

#include <stdio.h>

void swap(int arr[], int i, int j){
  int tmp;
  tmp = arr[i];
  arr[i] = arr[j];
  arr[j] = tmp;
}


int partition(int arr[], int first, int last){
  int pivot = arr[last];
  while(first <= last){
while(arr[first] < pivot){
  first++;
}
while(arr[last] > pivot){
  last--;
}
if(first <= last){
  swap(arr, arr[first], arr[last]);
  first++;
  last--;
}
}
}

void quickSortR(int arr[], int first, int last){
  if(last <= first) return;
  int mid = partition(arr, first, last);
  quickSortR(arr, first, mid-1);
  quickSortR(arr, mid+1, last);
}

void main() {
int arr[14] = {488888, 3, 5, 0, 23, 12124, 6, 7, 2, 1121, 0, 92, 5, 8};
quickSortR(arr, 0, 13);
for (int i = 0; i<14; i++) {
printf("arr[%d] = %d\n", i, arr[i]);
}
}

Ответы [ 2 ]

0 голосов
/ 12 февраля 2019

Ошибка сегментации находится в следующих строках: 

  tmp = arr[i];
  arr[i] = arr[j];
  arr[j] = tmp;

Вы отправляете элементы массива для свопинга (как i и j) и используете их в качестве индексов, очевидно, что эти строки вызовут ошибку сегмента как эти адресаможет быть вне границ и зарезервировано системой.

Как говорит @Loc, функция 'partition' должна возвращать индекс среднего значения, также вы забыли поменять шарнир.Есть некоторые другие незначительные исправления.Я включил исправленный код: 

#include <stdio.h>

void swap(int arr[], int i, int j){
        int tmp;
        tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
}


int partition(int arr[], int first, int last){
        int pivot = arr[last];
        int p=last;
        last--;
        while(first <= last){
                while(arr[first] < pivot){
                        first++;
                }
                while(arr[last] > pivot){
                        last--;
                }
                if(first <= last){
                        swap(arr, first, last);
                        first++;
                        last--;
                }
        }
        swap(arr, first, p);
        return first;
}

void quickSortR(int arr[], int first, int last){
        if(last <= first) return;
        int mid = partition(arr, first, last);
        quickSortR(arr, first, mid-1);
        quickSortR(arr, mid+1, last);
}

void main() {
        int arr[14] = {488888, 3, 5, 0, 23, 12124, 6, 7, 2, 1121, 0, 92, 5, 8};
        int i;
        quickSortR(arr, 0, 13);
        for (i = 0; i<14; i++) {
                printf("arr[%d] = %d\n", i, arr[i]);
        }
}
0 голосов
/ 12 февраля 2019

Эта функция возвращает int, но вы ничего не возвращаете: 

int partition(int arr[], int first, int last){

, поэтому mid находится в неопределенном состоянии, а arr [mid-1] или arr [mid] выходит за пределы диапазона 

int mid = partition(arr, first, last);

Пожалуйста, верните значение из функции раздел .

...