Array Concepts and Operations
5.1 Concept of Array
An array is a collection of elements of the same data type stored at contiguous memory
locations.
It allows us to store multiple values using a single variable name.
• Homogeneous: All elements in an array must be of the same type (e.g., all integers,
all floats, or all characters).
• Contiguous Memory: Elements are stored right next to each other in the computer's
memory. This allows for efficient access.
• Fixed Size: In most programming languages (like C, C++, Java), once an array is
created, its size is fixed and cannot be changed during execution.
• Indexing: Individual elements are accessed using an index (or subscript), which is
typically an integer starting from 0.
Example: An array named scores of 5 integers.
1. The Array Concept
Mailbox/Index 0 (Day 1 (Day 2 (Day 3 (Day 4 (Day 5 (Day 6 (Day
(Address) 1) 2) 3) 4) 5) 6) 7)
Element/Value 22 24 21 25 23 20 26
• Array Name: temperatures
• Size: 7 elements
• Type: Integer (whole numbers)
• Index: The numbered position (starting from 0) used to access the element.
2. How it Works in Code (Conceptual)
In most programming languages (like Python, Java, or C++), this array would look and work
like this:
Action Code (Conceptual) Explanation
Declaration int temperatures[7]; Creates a space to hold 7 integer values.
Access/Read print(temperatures[3]); This retrieves the value at index 3, which is 25.
Changes the temperature for Day 1 (index 0) from 22
Modification temperatures[0] = 27;
to 27.
5.2 Types of Arrays
Arrays are primarily categorized by the number of indices (dimensions) needed to access an
element.
1. One-Dimensional Array (1D Array)
• Structure: A list or sequence of elements.
• Indexing: Requires one index to access an element.
• Example (C++ syntax): int numbers[10]; (An array named numbers that can hold 10
integers).
o Elements are numbers[0], numbers[1], ..., numbers[9].
2. Two-Dimensional Array (2D Array)
• Structure: A table or a grid, often representing a matrix. It has rows and columns.
• Indexing: Requires two indices to access an element: one for the row and one for
the column.
• Example (C++ syntax): int matrix[3][4]; (An array with 3 rows and 4 columns, a total
of 12 elements).
o Elements are matrix[0][0] to matrix[2][3].
3. Multidimensional Array
• Structure: Arrays with three or more dimensions (e.g., 3D, 4D). A 3D array can be
visualized as a stack of 2D arrays (like pages in a book).
• Indexing: Requires indices, where is the number of dimensions.
• Example (C++ syntax): int cube[2][3][4]; (A 3D array with 2 layers, 3 rows, and 4
columns).
5.3 Array Operations
1. Declaration
• Purpose: To inform the compiler about the array's name, data type, and size
(number of elements).
• Syntax: dataType arrayName[size];
• Example: float salaries[50];
Key Points:
• Size is Fixed: The number inside the brackets [] defines the fixed size that cannot be
changed later.
• Type Specificity: The array can only store elements of the declared data type (int,
String, char, etc.).
• Declaration of Multi-Dimensional Arrays
• A multi-dimensional array (like a 2D array or matrix) is declared by specifying the
size for each dimension.
Language Syntax Pattern Example
C/C++ dataType arrayName [rows][columns]; float matrix[3][4];
2. Initialization
• Purpose: To assign initial values to the array elements.
• Method 1: At Declaration:
o int primes[5] = {2, 3, 5, 7, 11};
o int roll_no[5]= {5,6,8}; // here two spaces are allocated with 0.
• Method 2: Without specifying size (compiler calculates size):
o char vowels[] = {'a', 'e', 'i', 'o', 'u'};
• 2D Array Initialization:
o int M[2][3] = { {1, 2, 3}, {4, 5, 6} };
Multi-Dimensional Array (2D - Array of Arrays)
For two-dimensional arrays, you initialize row by row, where each inner set of
curly braces {} represents a row.
• Example (3x2 Matrix):
C++
int matrix[3][2] = {
{1, 2}, // Row 0
{3, 4}, // Row 1
{5, 6} // Row 2
};
3. Accessing Array Elements
• Purpose: To read the value of an element or write a new value to it.
• Method: Use the array name followed by the index in square brackets.
• Example (1D):
o x = A[2]; (Reads the value at index 2 and stores it in ).
o A[4] = 99; (Assigns the value 99 to the element at index 4).
• Example (2D):
o sum = M[1][0] + M[1][1]; (Adds elements at row 1, column 0 and row 1,
column 1).
• Looping: Arrays are often processed using loops (e.g., for loops) to iterate through all
elements.
`
5.4 Memory Representation of Two-Dimensional Array
Although a 2D array is conceptually a grid, the computer memory is linear (1D). Therefore, a
2D array is stored sequentially. There are two primary schemes for mapping a 2D array into
1D memory:
Assume a array (R rows, C columns), where indices start at 0. is the element at row and
column .
1. Row Major Order (RMO)
• Principle: Elements of the same row are stored contiguously. The entire first row is
stored, followed by the entire second row, and so on.
• Storage Sequence: .
• Address Calculation (A[i][j]):
o Where is the address of , and is the size of each element in bytes.
o The term calculates the number of elements before .
2. Column Major Order (CMO)
• Principle: Elements of the same column are stored contiguously. The entire first
column is stored, followed by the entire second column, and so on.
• Storage Sequence: .
• Address Calculation (A[i][j]):
o The term calculates the number of elements before .
• Note: C, C++, and Java typically use Row Major Order. FORTRAN uses Column Major
Order.
5.5 Passing Arrays to Function
There are two primary methods for passing arrays to functions in languages like C/C++:
Passing the Whole Array (By Reference/Address)
Passing Array Elements (By Value)
1. Passing the Whole Array (By Reference/Address)
This is the standard and most efficient way to pass arrays. Instead of copying all
elements, the function receives the starting address (or base address) of the array in
memory.
Key Characteristics:
Mechanism: The array name, which acts as a pointer to the first element, is passed. This
is known as Pass by Reference (though technically it's "pass by value of the pointer").
Syntax: The function parameter is declared as an array or a pointer. The array size is
often passed as a separate integer argument.
Mutability: Since the function works directly with the original memory location, any
changes made to the array inside the function affect the original array in the calling
function.
Example (C-like Syntax):
// Function definition: accepts array address (arr) and size
void modifyArray(int arr[], int size) {
arr[0] = 99; // Modifies the original array
int main() {
int data[3] = {10, 20, 30};
modifyArray(data, 3); // Passing the array name 'data'
// data[0] is now 99
return 0;
2. Passing Array Elements (By Value)
This method involves explicitly passing each element of the array individually within a
loop.
Key Characteristics:
Mechanism: Each element's value is copied into a separate variable in the function. This
is standard Pass by Value.
Syntax: A loop (usually a for loop) in the calling function is used to access
arrayName[index] and pass it to a function that accepts a single scalar variable.
Mutability: The function receives only a copy. Changes made to the parameter inside the
function do not affect the original array element. This protects the data.
Example (C-like Syntax):
// Function definition: accepts a single integer by value
void checkValue(int element) {
element = element + 100; // This change only affects the copy
int main() {
int scores[3] = {80, 90, 70};
for (int i = 0; i < 3; i++) {
// Passing scores[i] as a single value
checkValue(scores[i]);
// The scores array remains {80, 90, 70}
return 0;
Summary Comparison
Feature Method 1: Passing Whole Array Method 2: Passing Elements
Data
Address/Pointer (Reference) Value (Copy of each element)
Transfer
Original
Mutable (Can be changed) Immutable (Protected)
Array
Low (Overhead of loop and
Efficiency High (One address passed)
multiple function calls)
Feature Method 1: Passing Whole Array Method 2: Passing Elements
Sorting, searching, and general Specific computations on
Use Case processing where modification is individual elements where data
needed. protection is critical.
5.6 Array Applications
Arrays are the backbone for solving many common programming problems.
Advantages of Arrays
1. Fast Access (Random Access): Arrays allow for direct access to any element using its
index. Since elements are stored contiguously, the memory address of any element
can be calculated immediately using the formula:
This provides an access time of (constant time).
2. Memory Locality: Storing elements contiguously means they are close in memory.
This improves cache performance because when one element is accessed, adjacent
elements are often brought into the CPU's high-speed cache, speeding up
subsequent accesses. This is especially beneficial for iterative processes like searching
or sorting.
3. Simple Implementation: Arrays are one of the simplest data structures to
understand and implement, relying on basic indexing logic and loops.
4. Efficient Storage: Arrays only store the data values, without the overhead of pointers
or complex links between elements (unlike linked lists), resulting in minimal memory
usage per element.
Disadvantages of Arrays
1. Fixed Size (Static): The size of a traditional array is defined at the time of declaration
and cannot be changed during program execution.
o If you underestimate the size, you run the risk of array overflow (not enough
space).
o If you overestimate the size, you waste memory.
2. Inefficient Insertion and Deletion: Inserting a new element or deleting an existing
element in the middle of a full array is inefficient. All subsequent elements must be
shifted to maintain the contiguous structure.
o Time Complexity: Insertion/Deletion takes (linear time) in the worst case.
3. Memory Waste (Fragmentation): Since an array requires a large contiguous block of
free memory, allocating space for a very large array can be difficult. If the required
contiguous block isn't available, the allocation fails, even if the total free memory
exists in fragmented smaller blocks.
4. Homogeneous Data Type: Arrays can only store elements of the same data type
(e.g., all integers or all characters). They cannot store mixed data types directly
(unlike structures or objects).
1. Basic Applications
A. Finding Maximum and Minimum
• Method: Initialize a max variable to the first element () and iterate from the second
element () onwards. If the current element is greater than max, update max. Use a
similar approach for finding the minimum.
• This program finds the largest and smallest elements in a 1D array.
• C
#include <stdio.h>
void findMaxMin(int arr[], int n) {
if (n <= 0) {
printf("Array is empty.\n");
return;
}
int max = arr[0];
int min = arr[0];
// Start loop from the second element (index 1)
for (int i = 1; i < n; i++) {
if (arr[i] > max) {
max = arr[i]; // Update maximum
}
if (arr[i] < min) {
min = arr[i]; // Update minimum
}
}
printf("Maximum element: %d\n", max);
printf("Minimum element: %d\n", min);
}
int main() {
int numbers[] = {5, 8, 2, 14, 1, 9};
int size = 6;
printf("Finding Max and Min in array: {5, 8, 2, 14, 1, 9}\n");
findMaxMin(numbers, size);
return 0;
}
B. Counting Occurrences
• Method: To count how many times a specific element appears, iterate through the
array. For every element that equals , increment a counter variable.
2. Linear Search
• Goal: Find the position (index) of a target element in an array .
• Process: Start from the first element () and sequentially check each element until the
target is found or the end of the array is reached.
• Complexity:
o Best Case: (target is the first element).
o Worst/Average Case: (target is at the end or not present), where is the array
size.
• Use Case: Works on both sorted and unsorted arrays.
This program searches for a target element and returns its index.
C
#include <stdio.h>
int linearSearch(int arr[], int n, int target) {
// Iterate through the array from the first element
for (int i = 0; i < n; i++) {
if (arr[i] == target) {
return i; // Target found at index i
}
}
return -1; // Target not found
}
int main() {
int data[] = {15, 30, 45, 60, 75};
int size = 5;
int search_value = 45;
printf("Searching for %d in {15, 30, 45, 60, 75}\n", search_value);
int index = linearSearch(data, size, search_value);
if (index != -1) {
printf("Element %d found at index %d.\n", search_value, index);
} else {
printf("Element %d not found in the array.\n", search_value);
}
return 0;
}
3. Sorting an Array
Sorting is the process of arranging elements in a specific order (e.g., ascending or
descending).
A. Simple Exchange Sort (Selection Sort)
• Idea: Repeatedly select the minimum element from the unsorted part of the array
and swap it with the element at the current position.
• Process:
1. Start with the first position ().
2. Find the smallest element in the subarray from to .
3. Swap this smallest element with .
4. Increment and repeat until the array is sorted.
B. Bubble Sort
• Idea: Larger (or smaller) elements "bubble up" to their correct position through
repeated swaps of adjacent elements.
• Process:
1. Repeatedly pass through the list, comparing adjacent elements.
2. If two adjacent elements are in the wrong order, swap them.
3. In each pass, at least one element (the largest) moves to its final sorted
position.
4. Repeat passes until no swaps are needed (the array is sorted).
• Complexity: (In all cases, including best case, unless optimized).
(Visual Aid Description: Bubble Sort Pass)
1. Show an array segment: [8 | 5 | 10]. Highlight the first pair: [8 | 5].
2. Show an arrow for the comparison: "Is 8 > 5? Yes, Swap."
3. Show the array segment after the swap: [5 | 8 | 10]. Highlight the next pair: [8 | 10].
4. Show the comparison: "Is 8 > 10? No."
5. Add a caption: "A single pass moves the largest unsorted element (10 in a larger
array) to its correct place."
6. This program sorts an array in ascending order using the Bubble Sort algorithm.
C
#include <stdio.h>
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
void bubbleSort(int arr[], int n) {
// Outer loop controls the number of passes
for (int i = 0; i < n - 1; i++) {
// Inner loop performs the comparisons and swaps
// (n-i-1) because the last i elements are already in place
for (int j = 0; j < n - i - 1; j++) {
// Compare adjacent elements and swap if out of order
if (arr[j] > arr[j + 1]) {
swap(&arr[j], &arr[j + 1]);
}
}
}
}
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int data[] = {64, 34, 25, 12, 22, 11, 90};
int size = 7;
printf("Original array: ");
printArray(data, size);
bubbleSort(data, size);
printf("Sorted array: ");
printArray(data, size);
return 0;
}
4. Merging Two Sorted Arrays
• Goal: Combine two already sorted arrays ( and ) into a third sorted array ().
• Efficiency: This is much faster than concatenating the arrays and then sorting .
• Algorithm (Efficient Merge):
1. Use three pointers: for array , for array , and for array .
2. While is within 's bounds AND is within 's bounds:
▪ If , copy to and increment and .
▪ Else, copy to and increment and .
3. After one array is exhausted, copy the remaining elements of the non-
exhausted array into .
(Visual Aid Description: Merging Two Sorted Arrays)
1. Show Array A (Sorted): [2 | 5 | 8 | 12] with pointer at 2.
2. Show Array B (Sorted): [3 | 7 | 10] with pointer at 3.
3. Show Array C (Result): [ | | | | | | ] with pointer at the start.
4. Show the steps:
o Compare 2 and 3. Copy 2 to C. ( moves to 5, moves to next slot). C: [2 | | | ...]
o Compare 5 and 3. Copy 3 to C. ( moves to 7, moves). C: [2 | 3 | | ...]
o ...and so on.
5. Certainly! Here are sample programs (in C language syntax, which is common for
teaching array concepts) for the major applications discussed in your notes.
6.
This program merges two sorted arrays ( and ) into a single, larger sorted array ()
efficiently.
C
#include <stdio.h>
#define SIZE_A 5
#define SIZE_B 4
#define SIZE_C (SIZE_A + SIZE_B)
void mergeSortedArrays(int A[], int B[], int C[], int nA, int nB) {
int i = 0, j = 0, k = 0; // Pointers for arrays A, B, and C
// 1. Compare and merge elements while both arrays have elements
while (i < nA && j < nB) {
if (A[i] <= B[j]) {
C[k++] = A[i++];
} else {
C[k++] = B[j++];
}
}
// 2. Copy remaining elements of A, if any
while (i < nA) {
C[k++] = A[i++];
}
// 3. Copy remaining elements of B, if any
while (j < nB) {
C[k++] = B[j++];
}
}
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int A[SIZE_A] = {2, 5, 8, 12, 15};
int B[SIZE_B] = {3, 7, 10, 20};
int C[SIZE_C];
printf("Array A: ");
printArray(A, SIZE_A);
printf("Array B: ");
printArray(B, SIZE_B);
mergeSortedArrays(A, B, C, SIZE_A, SIZE_B);
printf("\nMerged Array C: ");
printArray(C, SIZE_C);
return 0;
}
5. Matrix Operations (2D Arrays)
A matrix is naturally represented as a 2D array, often denoted (Rows Columns).
Operation Description Condition/Formula
Trace of a Matrix Sum of elements on the main diagonal. (Only for square matrices: ).
Requires same dimensions
Addition () Sum of corresponding elements.
(, ). .
Rows become columns and columns
Transpose () If is , is . .
become rows.
Multiplication () Dot product of rows of and columns of . Requires: . If is and is , is . .
Symmetric Matrix A square matrix equal to its transpose. is square and .
Upper Triangular All elements below the main diagonal
for all .
Matrix are zero.
Lower Triangular All elements above the main diagonal
for all .
Matrix are zero.
(Visual Aid Description: Matrix Transpose)
1. Show a Matrix A (2x3): . Highlight the element (value 2) and (value 4).
2. Show an arrow labelled Transpose leading to Matrix A^T (3x2): .
3. Highlight the element (value 2) and (value 4), showing the swap. Add a note: "Row 1
of A becomes Column 1 of ."