Unit 4: Arrays in C

1. Introduction to Arrays

An array is a fixed-size collection of elements of the same data type stored in contiguous memory locations. Arrays allow programmers to store multiple values under a single variable name, accessing them via an index.

Key Characteristics:

• Homogeneous: All elements must be of the same type (e.g., all int or all float).
• Contiguous Memory: Elements are stored side-by-side in memory.
• Fixed Size: The size of the array must be known at compile time (in standard C89/90) and cannot change during execution.
• 0-based Indexing: The first element is at index 0, the second at index 1, and the last at index size - 1.

2. One-Dimensional (1D) Arrays

A one-dimensional array is a linear list of elements.

Declaring Arrays

Syntax:

DataType ArrayName[ArraySize];

int numbers[5]; // Declares an array capable of holding 5 integers

Initializing Arrays

Arrays can be initialized at the time of declaration.

1. Full Initialization:
   
   C

       int arr[5] = {10, 20, 30, 40, 50};
       

2. Partial Initialization:
   
   C

       int arr[5] = {10, 20}; 
       // Remaining elements are automatically initialized to 0.
       // Result: {10, 20, 0, 0, 0}
       

3. Omission of Size:
   
   C

       int arr[] = {1, 2, 3}; 
       // Compiler automatically sets size to 3 based on element count.
       

Accessing and Processing 1D Arrays

We access elements using the subscript operator []. Iteration usually requires a for loop.

Code Example: Input and Output of 1D Array

#include <stdio.h>

int main() {
    int arr[5], i;

    // Input
    printf("Enter 5 integers:\n");
    for(i = 0; i < 5; i++) {
        scanf("%d", &arr[i]);
    }

    // Output
    printf("Array elements are: ");
    for(i = 0; i < 5; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

3. Two-Dimensional (2D) Arrays

A 2D array is essentially an "array of arrays." It is best visualized as a table or matrix consisting of rows and columns.

Declaration

Syntax:

DataType ArrayName[Rows][Columns];

int matrix[3][4]; // 3 rows and 4 columns

Initialization

int matrix[2][3] = {
    {1, 2, 3},  // Row 0
    {4, 5, 6}   // Row 1
};

Memory Representation

Although visualized as a grid, C stores 2D arrays in Row-Major Order (row by row) in a continuous block of memory.

Processing 2D Arrays

Processing requires nested loops: the outer loop iterates through rows, and the inner loop iterates through columns.

Code Example: Printing a Matrix

#include <stdio.h>

int main() {
    int mat[2][3] = {{1, 2, 3}, {4, 5, 6}};
    int i, j;

    printf("2D Array Content:\n");
    for(i = 0; i < 2; i++) {       // Loop for Rows
        for(j = 0; j < 3; j++) {   // Loop for Columns
            printf("%d\t", mat[i][j]);
        }
        printf("\n"); // Newline after every row
    }
    return 0;
}

4. Passing Arrays to Functions

When passing an array to a function, C does not copy the entire array. Instead, it passes the base address (pointer to the first element). Therefore, changes made to the array inside the function affect the original array (Pass by Reference behavior).

Passing 1D Arrays

Syntax:

void myFunction(int arr[], int size);
// OR
void myFunction(int *arr, int size);

Passing 2D Arrays

When passing multi-dimensional arrays, the first dimension (rows) is optional, but all subsequent dimensions (columns) must be specified so the compiler can calculate memory offsets.
Syntax:

void myFunction(int arr[][4], int rows);

Code Example: Function modifying an array

void doubleValues(int arr[], int size) {
    for(int i = 0; i < size; i++) {
        arr[i] = arr[i] * 2; // Modifies actual memory
    }
}

5. Array Operations: Insertion and Deletion

Since arrays have a fixed size, inserting or deleting elements involves shifting existing elements to accommodate the change.

Insertion

To insert an element at index pos:

1. Shift all elements from pos to the end one step to the right.
2. Place the new value at pos.
3. Increase the logical size of the array.

Code Snippet:

// size = current number of elements, capacity = max size
if (size < capacity) {
    for (i = size; i > pos; i--) {
        arr[i] = arr[i - 1]; // Shift right
    }
    arr[pos] = newValue;
    size++;
}

Deletion

To delete an element at index pos:

1. Shift all elements from pos + 1 to the end one step to the left.
2. Decrease the logical size of the array.

Code Snippet:

for (i = pos; i < size - 1; i++) {
    arr[i] = arr[i + 1]; // Shift left overwriting pos
}
size--;

6. Searching Algorithms

Searching involves finding the location of a specific element (target) within the array.

A. Linear Search

• Method: Iterate through the array sequentially from the first element to the last. Compare each element with the target.
• Requirement: Array does not need to be sorted.
• Time Complexity: (Worst case).

Code:

int linearSearch(int arr[], int size, int target) {
    for (int i = 0; i < size; i++) {
        if (arr[i] == target) {
            return i; // Return index if found
        }
    }
    return -1; // Return -1 if not found
}

B. Binary Search

• Method: Repeatedly divides the search interval in half.
  1. Compare target with the middle element.
  2. If match, return index.
  3. If target < middle, search the left half.
  4. If target > middle, search the right half.
• Requirement: Array must be sorted.
• Time Complexity: .

Code:

int binarySearch(int arr[], int size, int target) {
    int low = 0, high = size - 1;
    
    while (low <= high) {
        int mid = (low + high) / 2;
        
        if (arr[mid] == target)
            return mid;
        else if (arr[mid] < target)
            low = mid + 1; // Ignore left half
        else
            high = mid - 1; // Ignore right half
    }
    return -1;
}

7. Sorting: Bubble Sort

Sorting rearranges elements in a specific order (ascending or descending).

Bubble Sort Algorithm

Repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted.

• After the first pass, the largest element "bubbles up" to the last position.
• Time Complexity: .

Logic:

1. Outer loop runs n-1 times.
2. Inner loop compares arr[j] with arr[j+1].
3. Swap if arr[j] > arr[j+1].

Code:

void bubbleSort(int arr[], int n) {
    int i, j, temp;
    for (i = 0; i < n - 1; i++) {
        // Last i elements are already in place
        for (j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // Swap
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

8. Array Applications

Arrays are fundamental to computer science and are used in various scenarios:

1. Mathematical Matrix Operations: Addition, multiplication, and transposition of matrices using 2D arrays.
2. String Handling: In C, strings are simply 1D arrays of characters terminated by a null character (\0).
3. Data Structure Implementation: Arrays are the building blocks for implementing other data structures like Stacks, Queues, Hash Tables, and Heaps.
4. Database Records: Storing records of data where indices map to specific IDs.
5. Lookup Tables: Storing pre-calculated values for quick access (e.g., sine/cosine tables in embedded systems).
6. Sorting and Searching: As detailed above, arrays provide the standard structure for algorithm analysis.