Considere la posibilidad de escribir la implementación de un algoritmo no tan obvio en C. Por ejemplo, que sea un resumen rápido recursivo, que he encontrado en el libro "Programación en C: un enfoque moderno, segunda edición" de K. N. King, que está disponible enaquí. La parte más interesante consiste en dos definiciones siguientes:

void quicksort(int a[], int low, int high)
{
    int middle;

    if (low >= high)
        return;

    middle = split(a, low, high);
    quicksort(a, low, middle - 1);
    quicksort(a, middle + 1, high);
}

int split(int a[], int low, int high)
{
    int part_element = a[low];

    for (;;) {
       while (low < high && part_element <= a[high])
           high--;
       if (low >= high)
           break;
       a[low++] = a[high];

       while (low < high && a[low] <= part_element)
           low++;
       if (low >= high)
           break;
       a[high--] = a[low];
    }

    a[high] = part_element;
    return high;
}

Amboswhile los bucles se pueden optimizar eliminandolow < high pruebas:

for (;;) {
    while (part_element < a[high])
        high--;
    if (low >= high)
        break;
    a[low++] = a[high];
    a[high] = part_element;

    while (a[low] <= part_element)
        low++;
    if (low >= high)
        break;
    a[high--] = a[low];
    a[low] = part_element;
}

¿Cuál es la forma recomendada para asegurarse de que cada acceso o escritura en la matriz (asignada enapilar) es realmente válido (es decir, no provoca un comportamiento indefinido)? Lo que ya intenté es:

depuración manual congdb en algunos datos realespasar el código fuente a herramientas de análisis estático comosplit ocppcheckvalgrind con--tool=exp-sgcheck cambiar

Por ejemplo, tener una matriz de cinco elementos{8, 1, 2, 3, 4}:

#define N 5

int main(void)
{
    int a[N] = {8, 1, 2, 3, 4}, i;

    quicksort(a, 0, N - 1);

    printf("After sort:");
    for (i = 0; i < N; i++)
        printf(" %d", a[i]);
    putchar('\n');

    return 0;
}

El resultado es (sin duda depende de la implementación):

After sort: 1 1 2 4 8

1. GDB

(gdb) p low
$1 = 3
(gdb) p high
$2 = 4
(gdb) p a[low]
$3 = 1
(gdb) p part_element
$4 = 8
(gdb) s
47              low++;
(gdb) s
46          while (a[low] <= part_element)
(gdb) s
47              low++;
(gdb) s
46          while (a[low] <= part_element)
(gdb) p low
$5 = 5
(gdb) p high
$6 = 4
(gdb) bt full
#0  split (a=0x7fffffffe140, low=5, high=4) at qsort.c:46
        part_element = 8
#1  0x00000000004005df in quicksort (a=0x7fffffffe140, low=0, high=4) at qsort.c:30
        middle = <value optimized out>
#2  0x0000000000400656 in main () at qsort.c:14
        a = {4, 1, 2, 1, 8}
        i = <value optimized out>

Como veslow la variable salió del límite:

(gdb) p low
$5 = 5

2. Herramientas de análisis estático.

$ splint -retvalint -exportlocal qsort.c 
Splint 3.1.2 --- 07 Feb 2011

Finished checking --- no warnings

$ cppcheck qsort.c 
Checking qsort.c...

3. Valgrind con--tool=exp-sgcheck

$ valgrind --tool=exp-sgcheck ./a.out 
==5480== exp-sgcheck, a stack and global array overrun detector
==5480== NOTE: This is an Experimental-Class Valgrind Tool
==5480== Copyright (C) 2003-2012, and GNU GPL'd, by OpenWorks Ltd et al.
==5480== Using Valgrind-3.8.1 and LibVEX; rerun with -h for copyright info
==5480== Command: ./a.out
==5480== 
==5480== Invalid read of size 4
==5480==    at 0x4005A0: split (qsort.c:46)
==5480==    by 0x4005DE: quicksort (qsort.c:30)
==5480==    by 0x400655: main (qsort.c:14)
==5480==  Address 0x7ff000114 expected vs actual:
==5480==  Expected: stack array "a" of size 20 in frame 2 back from here
==5480==  Actual:   unknown
==5480==  Actual:   is 0 after Expected
==5480== 
After sort: 1 1 2 4 8
==5480== 
==5480== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)

La locaciónat 0x4005A0: split (qsort.c:46) coincide con el mismo lugar que encontré porgdb a mano.