What does segmentation fault (core dumped) mean? (quicksort code)

Question

I am writing a quicksort function and am getting a segmentation fault error. I'm not sure why this is. Any help is appreciated. Here's my code. I know the error means that I'm trying to access memory that doesn't exist but I'm not sure where exactly the mistake is.

#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]);
}
}

Possible duplicate of [What is a segmentation fault?](https://stackoverflow.com/questions/2346806/what-is-a-segmentation-fault) — abestrad, Feb 11 '19 at 21:47
It usually means that you are accessing memory you should not. Most favorite way to do that is errors with using pointers or accessing beyond arrays. Debug your code to find out more. — Yunnosch, Feb 11 '19 at 21:48
`int pivot = arr[last]; .. while(arr[first] < pivot){`: If `first` is ever equal to `last` you will access `arr` one element out of bounds. — yano, Feb 11 '19 at 21:50
You have an out-of-bounds read (a.k.a buffer overflow) a line 36. Here is a live test of your code (https://segfault.stensal.com/a/Zwh8jqzrZmEFnsxU). It shows the backtrace of the illegal memory access. Hope the error message is self-evident enough for you to fix it. If not, feel free to reply my comment. — stensal, Feb 12 '19 at 03:33

score 1 · Answer 1 · answered Feb 11 '19 at 21:48

1

This function return int but you don't return anything:

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

so it make the mid is undefined state and make arr[mid-1] or arr[mid] is out of range

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

Please return the value from function partition.

answered Feb 11 '19 at 21:48

Loc Tran

1,170
7
15

I think this does not actually answer the question. And pointing out the error is probably only a short-lived help for OP. – Yunnosch Feb 11 '19 at 21:50
The illegal memory access happens before `partition` returns. This is definitely a bug, but it's not the cause of the segfault. – stensal Feb 12 '19 at 03:36

score 0 · Accepted Answer · answered Feb 12 '19 at 05:20

The segmentation fault is in the following lines:

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

You are sending array elements to swap( as i and j) and using them as indices, obviously these lines will cause seg fault as these addresses may be out of bounds and system reserved.

As told by @Loc the 'partition' function should return the mid value's index, also you forgot to swap the pivot. There are some other minor corrections. I have included the corrected code:

#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]);
        }
}

What does segmentation fault (core dumped) mean? (quicksort code)

2 Answers2