1

I am trying to the run the following quick sort algorithm and get the following error when I debug it with gdb:

Program received signal SIGSEGV, Segmentation fault.

0x000055555555530a in partition (arr=<error reading variable: Cannot access memory at address 0x7fffff7fefe8>, low=<error reading variable: Cannot access memory at address 0x7fffff7fefe4>, high=<error reading variable: Cannot access memory at address 0x7fffff7fefe0>

Source code is:

/* This program in C demonstrates the quick sort algorithm in C
 * For partitioning I have used the Hoare's algorithm via using the
 * first element of the array as the pivot element
 */
#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>
#define true 1

void swap(int*, int*);
void quick_sort(int arr[], int, int);
int partition(int arr[], int, int);
void print_array(int arr[], int);

int main(int argc, char* argv[])
{
    int array[10] = {3, 4, 2, -1, 7, 100, 82, 5};
    int size = sizeof(array) / sizeof(array[0]);
    print_array(array, size);
    quick_sort(array, 0, size - 1);
    print_array(array, size);
    return 0;
}

void print_array(int arr[], int size)
{
    printf("The array for quick sort algorithm\n");
    for (int i = 0; i < size; i++) {
        printf("%d\t", arr[i]);
    }
}

void swap(int* a, int* b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

/* This function returns the pivot postion, initially the pivot is set to the first element */
int partition(int arr[], int low, int high)
{
    int pivot = arr[low];
    int i = low - 1;
    int j = high + 1;
    while (true) {  /* Till the loop is infinitely running */
        
        do {
            i++;
        }while (arr[i] <= pivot);

        do {
            j--;
        }while (arr[j] > pivot);

        if (i >= j)               /* Once there is crossover, return j */
            return j;  
        swap(&arr[i], &arr[j]);
    }
}

void quick_sort(int arr[], int low, int high)
{
    if (low < high) {  /* If there are atleast 2 elements in the array */
        int pivot_pos = partition(arr, low, high);
        quick_sort(arr, low, pivot_pos);
        quick_sort(arr, pivot_pos + 1, high);
    }
}

Here is the gdb layout as well which shows both source and asm.

enter image description here

6
  • have you tried to debug this? Use your debugger and/or add some printfs at relevant places, then you can see what's going on. Commented Nov 29, 2024 at 7:58
  • @Jabberwocky I have added the gdb layout as well now in my original post. Though I could not go further than doing a couple of pretty printings or getting to know the program counter or knowing the values of the registers. info proc mappings also I used but that just showed the memory of the whole program as a whole and I was looking where the exact memory in the layout is not being accessed. Getting all these together in a sequence for me is not coming up well together. Commented Nov 29, 2024 at 8:08
  • 2
    pay attention with the indexes...looks like you enter in a permanent loop. Commented Nov 29, 2024 at 9:26
  • 2
    I just tried this an the partition method processes items 0 to 9, but then gets into a loop processing items 0 to 4 repeatedly. So the debugger should show you where you are going wrong. Commented Nov 29, 2024 at 9:28
  • @OldBoy oh yeah. Thanks a lot. I am fixing the issue. Commented Nov 29, 2024 at 10:32

1 Answer 1

2

There are two problems:

First: In this line in partition():

        }while (arr[i] <= pivot);

If no element is larger than the pivot, then i will continue out of bounds.

If no boundary check is done on the pointers i and j, then strict comparison must be used to avoid this:

        }while (arr[i] < pivot);

Second: After partitioning, the pivot element is in the right place and must be excluded from the recursive calls, i.e. this line in quick_sort():

        quick_sort(arr, low, pivot_pos);

should be

        quick_sort(arr, low, pivot_pos - 1);
Sign up to request clarification or add additional context in comments.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.