Cannot access memory at address error in gdb

Question

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.

Answer 1

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);