Tracing execution of a sorting program.  Consider the following code:


     #include<stdio.h>
     void swap ( int *, int *);
     void sort(int *, int);
     int
     main ()
     {
        int array[7] = {3, 1, 23, 7, 13, 5, 19}, k;
        sort(array,7);
        for ( k = 0; k < 7; k++)
           printf("%10d",*(array+k));
        printf("\n");
        return 0;
     }
     void
     swap ( int *a, int *b ) {
        int temp;
        temp = *a; *a = *b; *b = temp;
     }
     void
     sort(int *a, int n)
     {
         int             j, pass;
         int             switched = 1;
     
         for (pass = 0; pass < n  && switched == 1; pass++) {
             /* Outer loop controls number of passes */
     
             switched = 0;           /* None have occurred */
     
             for (j = 0; j < n - pass ; j++)
                 if ( *(a+j) > *(a+j+1)) {
                     /* elements out of order an interchange is req'd */
                     switched = 1;
		     swap(a+j,a+j+1);
                 }                   /* end if */
         }                           /* end for */
     }                               /* end bubble */

mscs% !g
gcc -Wall -g sort.c
mscs% a.out
-536871980         1         3         5         7        13        19

Not quite what was expected. We can look at the code in gdb:

mscs% gdb a.out
GDB is free software and you are welcome to distribute copies of it
under certain conditions; type "show copying" to see the conditions.
There is absolutely no warranty for GDB; type "show warranty" for details.
GDB 4.14 (sparc-sun-solaris2), Copyright 1995 Free Software Foundation, Inc...
(gdb) l 25
(gdb) l 25
20      sort(int *a, int n)
21      {
22          int             j, pass;
23          int             switched = 1;
24
25          for (pass = 0; pass < n  && switched == 1; pass++) {
26              /* Outer loop controls number of passes */
27
28              switched = 0;           /* None have occurred */
29
(gdb)
30              for (j = 0; j < n - pass ; j++)
31                  if ( *(a+j) > *(a+j+1)) {
32                      /* elements out of order an interchange is req'd */
33                      switched = 1;
34                      swap(a+j,a+j+1);
35                  }                   /* end if */
36          }                           /* end for */
37      }                               /* end bubble */
(gdb) break 28
Breakpoint 1 at 0x10970: file sort.c, line 28.
(gdb)run
Breakpoint 1, sort (a=0xdffffb28, n=7) at sort.c:28
28              switched = 0;           /* None have occurred */
(gdb) p (int [7]) *a
$1 = {3, 1, 23, 7, 13, 5, 19}    *** As expected ***
(gdb) c
Continuing.

Breakpoint 1, sort (a=0xdffffb28, n=7) at sort.c:28
28              switched = 0;           /* None have occurred */
(gdb) p pass
$2 = 1
(gdb) p (int [7]) *a
$3 = {1, 3, 7, 13, 5, 19, -536871996}    *** NOT as expected ***
(gdb) p a[7]     ****** NOTE: only a[0..6]  are defined ***
$5 = 23    ***** The missing value ****
    **** it should be apparent that somewhere the bounds of a are
	 being violated. *****
(gdb) break 31 if j+1 > 6
Breakpoint 1 at 0x1099c: file sort.c, line 31.
(gdb) run
Starting program: /users/cscfac/keast/classes/1400/95/week10/a.out

Breakpoint 1, sort (a=0xdffffb28, n=7) at sort.c:31
31                  if ( *(a+j) > *(a+j+1)) {
(gdb) p j
$1 = 6
(gdb) p j+1
$2 = 7   **** problem ****  **** j < n - pass - 1 ****

  Incidentally, pass ought to go only to < n-1.