Considere escrever a implementação de um algoritmo não tão óbvio em C. Por exemplo, que seja rápida descrição recursiva, que eu encontrei no livro "Programação C: Uma Abordagem Moderna, 2ª Edição" de K. N. King, que está disponível emaqui. A parte mais interessante consiste em duas definições a seguir:

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 loops podem ser otimizados removendolow < high testes:

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

Qual é a maneira recomendada de garantir que todo acesso ou gravação na matriz (alocado empilha) é realmente válido (ou seja, não está provocando comportamento indefinido)? O que eu já tentei é:

debugar manualmente comgdb em alguns dados reaispassar o código fonte para ferramentas de análise estática comosplit oucppcheckvalgrind com--tool=exp-sgcheck interruptor

Por exemplo, tendo cinco elementos de matriz{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;
}

O resultado é (certamente depende da implementação):

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 você vêlow A variável saiu do limite:

(gdb) p low
$5 = 5

2. Ferramentas de análise estática

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

Finished checking --- no warnings

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

3. Valgrind com--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)

A localizaçãoat 0x4005A0: split (qsort.c:46) está correspondendo ao mesmo local que encontrei porgdb manualmente.