C Programming: Arrays, Sorting, and Pointers

Posted on Feb 1, 2025 in Computers

In C, characters are declared to be of the type char. Each char variable is stored in 8 bits (This is different from Java, in which the char type requires 16 bits so that it can store a Unicode).

Variable-Length and 2D Arrays: Latin Square Example

Let’s examine an example using both variable-length arrays and 2D arrays. The example tests whether a matrix is a Latin square. An n by n matrix is a Latin square if each row is a permutation of numbers 1, 2, . . . , n and each column is a permutation of the same numbers 1, 2, . . . , n. Some examples are:

Merge Sort Algorithm

Let’s explore examples where recursive solutions are more natural. One such example is the merge sort algorithm. The underlying algorithm design paradigm is called divide-and-conquer, and it consists of three steps:

  • Divide: Divide the n-element array to be sorted into two subarrays of n/2 elements each.
  • Conquer: Sort the two subarrays recursively using the same algorithm: merge sort.
  • Combine: Merge the two sorted subarrays to produce the sorted answer.

Quicksort Algorithm

  1. Pick an element, called a pivot, from the array.
  2. Partitioning: reorder the array so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
  3. Recursively apply the above steps to the sub-array of elements with smaller values and separately to the sub-array of elements with greater values.

Planning a Permutation Algorithm

The algorithm will be recursive.

  • Algorithm will keep the first k elements fixed and permute the rest.
  • Algorithm parameters: Permute(A, k, n)
  • Initial call to the algorithm: Permute(A, 0, n)
  • Base case: k == n-1

Local Static Variables

Using the keyword static with local variables:

  • Have static storage duration, but local scope.
  • Example: int counter() { static int cnt = 0; return cnt++; }
  • What does the function return if we call it a few times?


Program Layout

Typical program layout:

  • #include directives
  • #define directives
  • Type definitions
  • Global variable definitions
  • Function prototypes (except main)
  • main
  • Other function definitions

Common Bugs with Pointers

  1. Dereferencing an un-initialized pointer
    • Result: undefined behavior
    • Example: int *p; *p = 5;
  2. Dangling pointer
    • Accessing an object that does not exist any more on stack or heap
    • Example: int* f() { int i=4; return &i; } ... int *p; p = f(); ++(*p);

Pointer Arithmetic Example

Consider the following code:


1: int a[10] = {9};
2: int *p = &a[1];
3: (*(p+3))++;
4: printf("%d %d\n", a[1], a[4]);

What is the output of this program? In line 1, we initialize a so that it has values: 9, 0, 0, 0, 0, 0, 0, 0, 0, and 0. We then make p point to a[1]. Therefore, p+3 points to a[1+3] which is a[4]. Thus line 3 increments a[4] by 1. Hence the output is: 0 1

Drawing a figure can be a very helpful tool when working with pointers. The following simplified figure shows the status after the program finishes executing: