Example

int marks[3] = {70, 80, 90}; creates three int elements. Their names are marks[0], marks[1] and marks[2]. The number in brackets in a declaration gives the element count, not the last index. All elements belong to the same array and occupy contiguous storage.

Advantages

1. One declaration can hold several related values.
2. A loop can read, display or process the elements.
3. A valid indexed element can be accessed directly without searching earlier elements.
4. Arrays provide a convenient representation for lists, tables and matrices.

Limitations

1. The length of an existing array object does not grow automatically.
2. The element type is fixed by its declaration.
3. C does not automatically check each index at runtime.
4. Insertion or deletion in the middle of a logical list may require shifting elements.

Uses and complexity

Arrays are useful for marks, measurements and sorted lists. A direct valid element access takes O(1) time in the usual random-access model. Processing all n elements takes O(n). Storing n elements requires O(n) space, while a fixed number of counters adds O(1) auxiliary space. A single indexed access does not sort or search the whole array.

Important point

An array of length 3 has no element at index 3. Access outside its bounds has undefined behaviour; it is not guaranteed to display zero or a predictable extra value.

Diagram or flowchart

Related exam questions

Related questions in the arrays category from the supplied papers. The marks below are the printed allocations, including any combined subquestion.

• March/April 2023 · Q11(b) · 5 marks

  Write an algorithm to sum all elements in an array and find its time complexity.

  Paper P02 · page 2
• June 2022 · Q3(a) · 7 marks

  What is an array? Describe declaration and initialisation of one- and two-dimensional arrays.

  Paper P03 · page 1

View this category in the exam question bank →

Syntax and examples

int marks[4];
int scores[4] = {60, 70, 80, 90};
int values[] = {2, 4, 6};
int zeroes[4] = {0};

Meaning

marks has space for four integers. An ordinary automatic marks array without an initialiser does not have useful guaranteed starting values. scores receives all four listed values. The length of values is inferred as three from its initialisers. In zeroes, the first element is explicitly zero and the remaining elements are also zero-initialised.

Partial initialisation

int a[5] = {2, 4}; stores 2 and 4 in the first two positions and zero in the rest. Do not confuse this with int a[5]; at block scope, which does not initialise the ordinary automatic elements. Objects with static storage duration have their own default initialisation rules.

Assignment after declaration

Assign individual elements using a valid index, such as a[2] = 9;. Ordinary C arrays cannot be assigned as a whole using a = b. To copy elements between separate arrays, use a suitable loop or an appropriate library operation with correct bounds.

Size and complexity

Where the actual array declaration is visible, sizeof a / sizeof a[0] gives its element count for this ordinary array. It does not work as an array-length calculation on an adjusted array parameter. Initialising or copying n elements involves O(n) element work; one element assignment is O(1).

C program and output

/* CodeBhavya | PPS AR25 | Learning example */
#include <stdio.h>

int main(void)
{
    int a[5] = {2, 4};
    for (int i = 0; i < 5; ++i) { printf("%d\n", a[i]); }
    return 0;
}

2
4
0
0
0

Related exam questions

Related questions in the arrays category from the supplied papers. The marks below are the printed allocations, including any combined subquestion.

• March/April 2023 · Q11(b) · 5 marks

  Write an algorithm to sum all elements in an array and find its time complexity.

  Paper P02 · page 2
• June 2022 · Q3(a) · 7 marks

  What is an array? Describe declaration and initialisation of one- and two-dimensional arrays.

  Paper P03 · page 1

View this category in the exam question bank →

Indexing example

For int a[4] = {10, 20, 30, 40};, a[0] is 10, a[2] is 30 and a[3] is 40. An index can be a variable or expression, such as a[i] or a[i + 1], when its resulting value is valid.

Correct loop

for (int i = 0; i < n; ++i) {
    printf("%d\n", a[i]);
}

Off-by-one mistake

Using i <= n instead of i < n reaches a[n] when n is the array’s logical length and capacity. That extra iteration is invalid for an array with exactly n elements. A one-based position shown to a student is different from a zero-based index: position 1 corresponds to index 0.

Bounds checks

1. Check that the input count does not exceed the actual capacity.
2. Check that an index is non-negative before using it.
3. Check that the index is less than the number of elements allowed for the operation.
4. For a[i + 1], make sure the next element exists too.

Important points

C does not promise a runtime error message for an invalid subscript. Reading or writing outside bounds has undefined behaviour and can corrupt unrelated data. A pointer may be formed one past an array in certain permitted operations, but it must not be dereferenced there. In this unit, simply restrict element access to valid indices.

Complexity

A valid direct access uses O(1) time in the usual array model. Checking a fixed set of bounds also uses O(1); it does not require traversing the array.

Related exam questions

Related questions in the arrays category from the supplied papers. The marks below are the printed allocations, including any combined subquestion.

• March/April 2023 · Q11(b) · 5 marks

  Write an algorithm to sum all elements in an array and find its time complexity.

  Paper P02 · page 2
• June 2022 · Q3(a) · 7 marks

  What is an array? Describe declaration and initialisation of one- and two-dimensional arrays.

  Paper P03 · page 1

View this category in the exam question bank →

Algorithm

1. Read the count n. Accept only 1 through 20.
2. For i from 0 to n - 1, read a[i] and check the input.
3. Use another loop over the same indices to display the elements.

Input and output expressions

scanf("%d", &a[i]) supplies the address of the selected int element so that scanf can store its value. printf("%d", a[i]) supplies the stored value for output. The address is needed for this input conversion; it is not the value to display.

Example trace

For count 3 and elements 8, -2 and 5, the first loop fills a[0], a[1] and a[2]. The second loop displays 8 -2 5 in the same order. No sorting takes place. A space is printed before every value after the first, followed by one newline at the end.

Input limits

This complete example accepts values between -10000 and 10000. Input tokens must fit int. It rejects a bad count, a failed conversion or a value outside the chosen range. The fixed capacity is 20, while n describes how many positions currently contain the list.

Time and space complexity

Reading n values requires n input operations and displaying them requires n output operations. The total work is proportional to 2n, giving O(n) time. The list storage is O(n) in a general-size version; counters add O(1) auxiliary space. This sample reserves a fixed array of 20 elements.

C program and output

/* CodeBhavya | PPS AR25 | Learning example */
#include <stdio.h>

int main(void)
{
    int n, a[20];
    if (scanf("%d", &n) != 1 || n < 1 || n > 20) {
        puts("Unsupported input"); return 1;
    }
    for (int i = 0; i < n; ++i) {
        if (scanf("%d", &a[i]) != 1 || a[i] < -10000 || a[i] > 10000) {
            puts("Unsupported input"); return 1;
        }
    }
    for (int i = 0; i < n; ++i) {
        if (i > 0) { putchar(' '); }
        printf("%d", a[i]);
    }
    putchar('\n');
    return 0;
}

3
8 -2 5

8 -2 5

Related exam questions

Related questions in the arrays category from the supplied papers. The marks below are the printed allocations, including any combined subquestion.

• March/April 2023 · Q11(b) · 5 marks

  Write an algorithm to sum all elements in an array and find its time complexity.

  Paper P02 · page 2
• June 2022 · Q3(a) · 7 marks

  What is an array? Describe declaration and initialisation of one- and two-dimensional arrays.

  Paper P03 · page 1

View this category in the exam question bank →

Algorithm for a sum

1. Read a valid count and its elements.
2. Set sum to zero.
3. For each index i from 0 through n - 1, add a[i] to sum.
4. Display sum.

Worked trace

For the list 4, -1 and 7, sum starts at 0. After index 0 it is 4. After index 1 it is 3. After index 2 it is 10. The loop finishes after every valid element has contributed exactly once.

Why the bounds matter

Starting at index 1 would omit the first element. Using i <= n would attempt an extra access. The loop condition i < n covers exactly n elements when i starts at zero and increases by one. The list need not be sorted for a sum.

Type choice

The sample uses long long for sum and %lld to print it. With at most 20 inputs of magnitude at most 10000, the total fits that type’s guaranteed range. A general implementation must choose a type and supported bounds suitable for its largest possible total.

Time and space complexity

The loop performs one addition for every element, so n elements give O(n) time. Input reading is also O(n), leaving the total linear. Apart from the array, only a count, counter and accumulator are needed: O(1) auxiliary space. Traversal is not a separate copy of the array.

C program and output

/* CodeBhavya | PPS AR25 | Learning example */
#include <stdio.h>

int main(void)
{
    int n, a[20];
    if (scanf("%d", &n) != 1 || n < 1 || n > 20) {
        puts("Unsupported input"); return 1;
    }
    for (int i = 0; i < n; ++i) {
        if (scanf("%d", &a[i]) != 1 || a[i] < -10000 || a[i] > 10000) {
            puts("Unsupported input"); return 1;
        }
    }
    long long sum = 0;
    for (int i = 0; i < n; ++i) { sum += a[i]; }
    printf("Sum = %lld\n", sum);
    return 0;
}

3
4 -1 7

Sum = 10

Related exam questions

Related questions in the arrays category from the supplied papers. The marks below are the printed allocations, including any combined subquestion.

• March/April 2023 · Q11(b) · 5 marks

  Write an algorithm to sum all elements in an array and find its time complexity.

  Paper P02 · page 2
• June 2022 · Q3(a) · 7 marks

  What is an array? Describe declaration and initialisation of one- and two-dimensional arrays.

  Paper P03 · page 1

View this category in the exam question bank →

Algorithm

1. Read a non-empty array.
2. Set minimum and maximum to a[0] and sum to a[0].
3. Scan indices 1 through n - 1. Update each extreme when needed and add the current value to sum.
4. Calculate average as (double)sum / n and display the results.

Worked trace

For 4, -2 and 7, both extremes start at 4 and sum starts at 4. Reading -2 changes minimum to -2 and sum to 2. Reading 7 changes maximum to 7 and sum to 9. Average is 9.0 / 3 = 3.0.

Important cases

A single-element list has the same minimum, maximum and average value. Repeated equal values need no special replacement. The list can contain negative values and need not be sorted. An empty list is rejected because this method needs a first element and the average must not divide by zero.

Preserving fractions

Casting sum to double before division allows a fractional average. Casting after integer division would not restore a discarded fraction. long long stores the bounded sample’s total safely, and the result is displayed with two decimal places.

Complexity

One scan examines each value once. A fixed number of comparisons and an addition are performed per element, giving O(n) time. minimum, maximum, sum and average occupy fixed extra storage, so auxiliary space is O(1), excluding the input array.

C program and output

/* CodeBhavya | PPS AR25 | Learning example */
#include <stdio.h>

int main(void)
{
    int n, a[20];
    if (scanf("%d", &n) != 1 || n < 1 || n > 20) {
        puts("Unsupported input"); return 1;
    }
    for (int i = 0; i < n; ++i) {
        if (scanf("%d", &a[i]) != 1 || a[i] < -10000 || a[i] > 10000) {
            puts("Unsupported input"); return 1;
        }
    }
    int minimum = a[0], maximum = a[0];
    long long sum = a[0];
    for (int i = 1; i < n; ++i) {
        if (a[i] < minimum) { minimum = a[i]; }
        if (a[i] > maximum) { maximum = a[i]; }
        sum += a[i];
    }
    printf("Minimum = %d, maximum = %d, average = %.2f\n",
           minimum, maximum, (double)sum / n);
    return 0;
}

3
4 -2 7

Minimum = -2, maximum = 7, average = 3.00

Related exam questions

Related questions in the arrays category from the supplied papers. The marks below are the printed allocations, including any combined subquestion.

• March/April 2023 · Q11(b) · 5 marks

  Write an algorithm to sum all elements in an array and find its time complexity.

  Paper P02 · page 2
• June 2022 · Q3(a) · 7 marks

  What is an array? Describe declaration and initialisation of one- and two-dimensional arrays.

  Paper P03 · page 1

View this category in the exam question bank →

Value argument

In show(a[1]), a[1] selects one element and its value is passed to the parameter. For an int parameter, that parameter is a separate object. Assigning to it does not assign to the original array element. This follows C’s pass-by-value rule.

Example trace

The sample starts with a[1] equal to 20. change(a[1]) gives the function’s parameter n the value 20. The function assigns n = 99 and prints it. When it returns, a[1] still contains 20. The two printed values demonstrate that only a value was supplied.

Address argument

A call such as change_at(&a[1]) could pass the address to an int * parameter. Assigning through that valid pointer could change the selected element. The pointer value is still passed by value; the object reached through it is shared. Detailed pointer operations belong to Unit V.

Important rules

1. Use a valid subscript before making the call.
2. Keep the parameter type suitable for the selected element.
3. Do not confuse passing one element, such as a[i], with passing the array expression a.
4. A function prototype helps the compiler check the intended argument types.

Complexity

Selecting and passing one fixed-width element takes constant work in the usual model. The function’s own processing determines any additional complexity. The example uses O(1) time and O(1) extra space.

C program and output

/* CodeBhavya | PPS AR25 | Learning example */
#include <stdio.h>
void change(int n)
{
    n = 99;
    printf("Parameter = %d\n", n);
}

int main(void)
{
    int a[3] = {10, 20, 30};
    change(a[1]);
    printf("Element = %d\n", a[1]);
    return 0;
}

Parameter = 99
Element = 20

Related exam questions

Related questions in the array function arguments category from the supplied papers. The marks below are the printed allocations, including any combined subquestion.

• July 2021 · Q7 · 15 marks

  Illustrate passing arrays to functions with a relevant example program.

  Paper P04 · page 1
• January/February 2024 · Q9(b) · 5 marks

  Explain passing an entire array as an argument to a function, with an example.

  Paper P10 · page 2

View this category in the exam question bank →

Function interface

long long total(const int a[], int n);

Meaning

In a parameter declaration, const int a[] is adjusted to const int *a. The function receives a pointer value identifying the first element. The array contents are not automatically copied. n states how many elements the function is allowed to read. const prevents modification through this parameter’s element access.

Example trace

main holds 4, 5 and 6 and calls total(a, 3). The function visits a[0], a[1] and a[2], adding them to its local accumulator. It returns 15. main prints the result. The array remains unchanged because this function only reads it.

Important points

1. Pass a valid length that fits the actual object.
2. Do not use sizeof a / sizeof a[0] inside this adjusted parameter to discover the caller’s array length.
3. A non-const int parameter written as int a[] can be used to modify the caller’s elements.
4. C still passes a value: the pointer is copied, while the elements remain in the original array.

Complexity

The function reads n elements once, giving O(n) time. It does not build a second array; only a sum and counter are added, giving O(1) auxiliary space. Copying a pointer argument does not mean copying n elements.

C program and output

/* CodeBhavya | PPS AR25 | Learning example */
#include <stdio.h>
long long total(const int a[], int n)
{
    long long sum = 0;
    for (int i = 0; i < n; ++i) { sum += a[i]; }
    return sum;
}

int main(void)
{
    int a[3] = {4, 5, 6};
    printf("Total = %lld\n", total(a, 3));
    return 0;
}

Total = 15

Related exam questions

Related questions in the array function arguments category from the supplied papers. The marks below are the printed allocations, including any combined subquestion.

• July 2021 · Q7 · 15 marks

  Illustrate passing arrays to functions with a relevant example program.

  Paper P04 · page 1
• January/February 2024 · Q9(b) · 5 marks

  Explain passing an entire array as an argument to a function, with an example.

  Paper P10 · page 2

View this category in the exam question bank →

Algorithm

1. Start at index 0.
2. Compare a[i] with key. Return i if equal.
3. Otherwise move to the next element.
4. If every element has been checked, return -1.

Worked trace

For 8, 3 and 5 with key 3, index 0 does not match. Index 1 matches, so the function returns 1. The displayed result is an index, not a one-based position. If the key were 7, all three comparisons would fail and -1 would be returned.

Duplicates and boundaries

Returning immediately at a match produces the first matching index. A one-element list is checked once. A generic linear-search function can also handle a length of zero by skipping its loop, although this interactive sample requires at least one input element.

Time complexity

The best case is a match at index 0, requiring one comparison: O(1). In the worst case, the key is absent or appears only at the last element, requiring n comparisons: O(n). Under a usual equally-likely-position model, successful average search also grows linearly. The input-reading part of the complete program is O(n) regardless of where a match occurs.

Space complexity

The non-recursive search stores only an index and fixed parameters, so auxiliary space is O(1). It neither sorts nor copies the input array.

Diagram or flowchart

C program and output

/* CodeBhavya | PPS AR25 | Learning example */
#include <stdio.h>
int linear_search(const int a[], int n, int key)
{
    for (int i = 0; i < n; ++i) {
        if (a[i] == key) { return i; }
    }
    return -1;
}

int main(void)
{
    int n, a[20];
    if (scanf("%d", &n) != 1 || n < 1 || n > 20) {
        puts("Unsupported input"); return 1;
    }
    for (int i = 0; i < n; ++i) {
        if (scanf("%d", &a[i]) != 1 || a[i] < -10000 || a[i] > 10000) {
            puts("Unsupported input"); return 1;
        }
    }
    int key;
    if (scanf("%d", &key) != 1) { puts("Unsupported input"); return 1; }
    printf("Index = %d\n", linear_search(a, n, key));
    return 0;
}

3
8 3 5
3

Index = 1

Related exam questions

Related questions in the linear search category from the supplied papers. The marks below are the printed allocations, including any combined subquestion.

• March/April 2023 · Q10(b) · 5 marks

  Describe linear search with an example and give its time complexity in all cases.

  Paper P02 · page 2
• March/April 2023 · Q10(a) · 8 marks

  Write the linear-search algorithm and explain with an example.

  Paper P05 · page 2

View this category in the exam question bank →

Algorithm

1. Set low = 0 and high = n - 1.
2. While low <= high, calculate mid = low + (high - low) / 2.
3. Return mid when a[mid] equals the key.
4. If the key is larger, set low = mid + 1; otherwise set high = mid - 1.
5. Return -1 if the interval becomes empty.

Worked trace

For 2, 4, 6, 8 and 10 with key 8, mid is initially 2 and a[2] is 6. Since 8 is larger, low becomes 3. The next midpoint is 3, whose value is 8, so index 3 is returned.

Sorted input and duplicates

The sample checks ascending order before calling the search function. Equal adjacent values are allowed. With duplicates, this version returns a matching index, which is not necessarily the first or last occurrence. Searching an unsorted array this way can miss a present key.

Time complexity

Each unsuccessful step roughly halves the candidate count: n, n/2, n/4 and so on. After about log2 n steps, at most one candidate remains. Thus worst-case search time is O(log n), while a first-midpoint match is O(1). Reading and checking the complete input is O(n), so the full interactive program has O(n) total work before and including one search.

Space complexity

This iterative function stores low, high and mid without recursive calls or another array, giving O(1) auxiliary space. The midpoint form avoids adding low and high directly.

Diagram or flowchart

C program and output

/* CodeBhavya | PPS AR25 | Learning example */
#include <stdio.h>
int binary_search(const int a[], int n, int key)
{
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (a[mid] == key) { return mid; }
        if (a[mid] < key) { low = mid + 1; }
        else { high = mid - 1; }
    }
    return -1;
}

int main(void)
{
    int n, a[20];
    if (scanf("%d", &n) != 1 || n < 1 || n > 20) {
        puts("Unsupported input"); return 1;
    }
    for (int i = 0; i < n; ++i) {
        if (scanf("%d", &a[i]) != 1 || a[i] < -10000 || a[i] > 10000) {
            puts("Unsupported input"); return 1;
        }
    }
    for (int i = 1; i < n; ++i) {
        if (a[i] < a[i - 1]) { puts("Array must be sorted"); return 1; }
    }
    int key;
    if (scanf("%d", &key) != 1) { puts("Unsupported input"); return 1; }
    printf("Index = %d\n", binary_search(a, n, key));
    return 0;
}

5
2 4 6 8 10
8

Index = 3

Related exam questions

Related questions in the binary search category from the supplied papers. The marks below are the printed allocations, including any combined subquestion.

• March/April 2023 · Q11(a) · 5 marks

  Discuss binary search with an example.

  Paper P02 · page 2
• March/April 2023 · Q1(i) · 1 marks

  Write the time complexity of binary search.

  Paper P05 · page 1

View this category in the exam question bank →

Linear search

It can start immediately on an unsorted array. It compares the key with each element until it finds a match or reaches the end. A first-element match is O(1), while the worst case is O(n). A simple first-match version returns the first occurrence when duplicates exist.

Binary search

It requires sorted input. It compares the key with a midpoint and retains only the possible half. A midpoint match is O(1), and the worst case is O(log n) for indexed arrays. A basic version does not guarantee the first duplicate. The iterative version needs O(1) auxiliary space.

Choosing a method

For a small unsorted list and one search, linear search is simple and avoids a preliminary sort. If an array is already sorted or will support many searches, binary search can reduce work per query. Sorting and later maintaining sorted order have costs of their own.

Example

For five unsorted marks, scanning directly may be the appropriate task. For thousands of already sorted roll numbers, repeatedly halving the interval is useful. The correct choice depends on input order, the number of searches and the representation.

Important distinction

The complexity of the search function differs from the total cost of reading, sorting or validating its input. A binary-search sample that checks every adjacent pair first spends O(n) on that validation, even though the actual search remains O(log n).

Comparison table

Related exam questions

Related questions in the linear search category from the supplied papers. The marks below are the printed allocations, including any combined subquestion.

• March/April 2023 · Q10(b) · 5 marks

  Describe linear search with an example and give its time complexity in all cases.

  Paper P02 · page 2
• March/April 2023 · Q10(a) · 8 marks

  Write the linear-search algorithm and explain with an example.

  Paper P05 · page 2

View this category in the exam question bank →

Algorithm

1. For each pass, scan adjacent pairs in the unsorted part.
2. Swap a[j] and a[j + 1] when the left value is larger.
3. Exclude the newly fixed rightmost value from the next pass.
4. Stop early if a full pass makes no swaps.

Worked trace

For 5, 1 and 4, compare 5 with 1 and swap, giving 1, 5, 4. Compare 5 with 4 and swap, giving 1, 4, 5. The largest value 5 is now fixed. The next pass compares 1 with 4 and makes no swap, so the algorithm stops.

Why it works

Each adjacent comparison moves the larger of the pair one position right. Across a pass, the largest remaining value keeps moving until it reaches the final unsorted position. Repeating this step fixes one more position each time.

Time complexity

In reverse order, the comparisons can total (n - 1) + (n - 2) + ... + 1 = n(n - 1)/2, giving O(n²) time. With the swapped flag, already sorted input needs only one pass of n - 1 comparisons, giving O(n) best-case time. Average performance is also quadratic under usual input models.

Space and stability

Only a few counters, a flag and a temporary value are added, so auxiliary space is O(1). This version swaps only when the left value is strictly larger. Equal values do not cross through a swap, so it is stable. The input array itself is rearranged.

Diagram or flowchart

C program and output

/* CodeBhavya | PPS AR25 | Learning example */
#include <stdio.h>
void sort(int a[], int n)
{
    for (int pass = 0; pass < n - 1; ++pass) {
        int swapped = 0;
        for (int j = 0; j < n - 1 - pass; ++j) {
            if (a[j] > a[j + 1]) {
                int temporary = a[j]; a[j] = a[j + 1]; a[j + 1] = temporary;
                swapped = 1;
            }
        }
        if (!swapped) { break; }
    }
}

int main(void)
{
    int n, a[20];
    if (scanf("%d", &n) != 1 || n < 1 || n > 20) {
        puts("Unsupported input"); return 1;
    }
    for (int i = 0; i < n; ++i) {
        if (scanf("%d", &a[i]) != 1 || a[i] < -10000 || a[i] > 10000) {
            puts("Unsupported input"); return 1;
        }
    }
    sort(a, n);
    for (int i = 0; i < n; ++i) {
        if (i > 0) { putchar(' '); }
        printf("%d", a[i]);
    }
    putchar('\n');
    return 0;
}

3
5 1 4

1 4 5

Related exam questions

Related questions in the bubble sort category from the supplied papers. The marks below are the printed allocations, including any combined subquestion.

• September/October 2021 · Q5(a) · 7 marks

  Explain bubble sort with an example.

  Paper P01 · page 1
• July 2021 · Q8(b) · 8 marks

  Explain bubble sort and mention its time complexity.

  Paper P04 · page 1

View this category in the exam question bank →

Algorithm

1. Start the next final position at i = 0.
2. Assume a[i] is the smallest remaining value.
3. Scan indices i + 1 through n - 1 and remember the index of a smaller value when found.
4. Swap the chosen minimum into position i, then advance i.

Worked trace

For 5, 1 and 4, the first scan finds 1 at index 1. Swapping it with index 0 gives 1, 5, 4. The next scan finds 4 as the minimum of the remaining two values. The result becomes 1, 4, 5.

Why it works

Each completed pass fixes the next smallest value in the next leftmost position. The values before i are already in their correct sorted places, so the scan only examines the remaining part.

Time complexity

The first pass makes n - 1 comparisons, the next n - 2, and so on. The total is n(n - 1)/2, giving O(n²) comparisons in best, average and worst cases for this version. Already sorted input still requires those scans. At most n - 1 swaps are needed.

Space and stability

The algorithm uses O(1) auxiliary space. The usual distant-swap implementation is not stable. For labelled equal values 2A, 2B, 1, swapping the final 1 with 2A produces 1, 2B, 2A; the equal 2s have changed relative order. To sort descending instead, select the largest remaining value with a suitable comparison.

C program and output

/* CodeBhavya | PPS AR25 | Learning example */
#include <stdio.h>
void sort(int a[], int n)
{
    for (int i = 0; i < n - 1; ++i) {
        int smallest = i;
        for (int j = i + 1; j < n; ++j) {
            if (a[j] < a[smallest]) { smallest = j; }
        }
        if (smallest != i) {
            int temporary = a[i]; a[i] = a[smallest]; a[smallest] = temporary;
        }
    }
}

int main(void)
{
    int n, a[20];
    if (scanf("%d", &n) != 1 || n < 1 || n > 20) {
        puts("Unsupported input"); return 1;
    }
    for (int i = 0; i < n; ++i) {
        if (scanf("%d", &a[i]) != 1 || a[i] < -10000 || a[i] > 10000) {
            puts("Unsupported input"); return 1;
        }
    }
    sort(a, n);
    for (int i = 0; i < n; ++i) {
        if (i > 0) { putchar(' '); }
        printf("%d", a[i]);
    }
    putchar('\n');
    return 0;
}

3
5 1 4

1 4 5

Related exam questions

Related questions in the selection sort category from the supplied papers. The marks below are the printed allocations, including any combined subquestion.

• June 2022 · Q8(b) · 8 marks

  Write a C program for selection sort.

  Paper P03 · page 1
• March/April 2023 · Q11(a) · 8 marks

  What is sorting? Explain selection sort with an example.

  Paper P05 · page 2

View this category in the exam question bank →

Algorithm

1. Treat the first element as a sorted prefix.
2. Save the next value as key.
3. Move preceding values one position right while they are larger than key.
4. Store key in the remaining gap and continue with the next element.

Worked trace

For 5, 1 and 4, key 1 is saved first. Since 5 is larger, shift it right and insert 1 at index 0, giving 1, 5, 4. Next save key 4. Shift 5 right, stop at 1 and insert 4 between them. The result is 1, 4, 5.

Why save the key?

Shifting overwrites array positions. Saving the selected value in a separate variable prevents it from being lost before the gap is ready. The condition j >= 0 && a[j] > key checks the boundary first, so short-circuit evaluation avoids reading a[-1].

Time complexity

For already sorted input, each key needs only a small comparison and no shifting, giving O(n) best-case time. For reverse order, the shifts total 1 + 2 + ... + (n - 1), giving O(n²) worst-case time. The usual average case is quadratic too. It can be useful for small or nearly sorted arrays.

Space and stability

Only a key and counters are added, giving O(1) auxiliary space. Shifting only strictly larger values keeps equal values in their prior relative order, so this version is stable.

C program and output

/* CodeBhavya | PPS AR25 | Learning example */
#include <stdio.h>
void sort(int a[], int n)
{
    for (int i = 1; i < n; ++i) {
        int key = a[i], j = i - 1;
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j]; --j;
        }
        a[j + 1] = key;
    }
}

int main(void)
{
    int n, a[20];
    if (scanf("%d", &n) != 1 || n < 1 || n > 20) {
        puts("Unsupported input"); return 1;
    }
    for (int i = 0; i < n; ++i) {
        if (scanf("%d", &a[i]) != 1 || a[i] < -10000 || a[i] > 10000) {
            puts("Unsupported input"); return 1;
        }
    }
    sort(a, n);
    for (int i = 0; i < n; ++i) {
        if (i > 0) { putchar(' '); }
        printf("%d", a[i]);
    }
    putchar('\n');
    return 0;
}

3
5 1 4

1 4 5

Related exam questions

Related questions in the insertion sort category from the supplied papers. The marks below are the printed allocations, including any combined subquestion.

• September/October 2021 · Q5(b) · 8 marks

  Give a brief note on insertion sort.

  Paper P01 · page 1
• March/April 2023 · Q10(a) · 5 marks

  Explain insertion sort using an example array.

  Paper P02 · page 2

View this category in the exam question bank →

Bubble sort

Adjacent values are compared and swapped when out of order. Each pass fixes a rightmost value. With the early-stop flag used here, sorted input takes O(n); average and worst cases take O(n²). Strictly-greater adjacent swaps preserve equal-value order.

Selection sort

Each pass scans for the minimum remaining value and swaps it into the next leftmost position. The scan count remains quadratic even on sorted input: O(n²). It uses relatively few swaps, at most n - 1, but a distant swap can reverse equal keys, so the usual version is not stable.

Insertion sort

Each next key is inserted into a sorted prefix by shifting larger values. It takes O(n) on already sorted input and O(n²) in the worst case. The strict comparison used here preserves equal-key order. It is often useful for small or nearly sorted lists.

Shared space requirement

All three shown implementations sort within the input array and use only a fixed number of extra variables. Their auxiliary space is O(1). This does not mean the input array takes no space; it means no extra storage proportional to n is needed.

Choosing a method

Look at input size, order, required stability and the cost of moving a record. A comparison of only worst-case Big-O values misses practical differences. For much larger lists, other algorithms may be preferable, but they are outside these three basic syllabus methods.

Comparison table

Related exam questions

Related questions in the bubble sort category from the supplied papers. The marks below are the printed allocations, including any combined subquestion.

• September/October 2021 · Q5(a) · 7 marks

  Explain bubble sort with an example.

  Paper P01 · page 1
• July 2021 · Q8(b) · 8 marks

  Explain bubble sort and mention its time complexity.

  Paper P04 · page 1

View this category in the exam question bank →

Declaration and initialisation

int a[2][3] = {
    {1, 2, 3},
    {4, 5, 6}
};

Access

a[0][0] is 1, a[0][2] is 3 and a[1][1] is 5. The first index selects a row array; the second selects an element within that row. Neither index may leave its own array bounds. a[0][3] is invalid even though another row follows in storage.

Row-major storage

C stores each row contiguously, followed by the next row. The example’s element order is 1, 2, 3, 4, 5, 6. This is called row-major order. A two-dimensional array is not the same type as a pointer to pointer.

Traversal

Use an outer loop for rows and an inner loop for columns. Print a newline after the inner loop to end each row. The program displays the two rows exactly as a table.

Complexity and memory

For r rows and c columns, there are r × c elements. Visiting every element once takes O(rc) time. The array occupies r × c × sizeof(element) C bytes; only loop counters add O(1) auxiliary space. A direct valid access uses O(1) time in the usual model.

Function connection

When passing such an array to a function, the row width must be described correctly so that indexing advances by a complete row. The final topic of this unit explains the fixed-width function form.

C program and output

/* CodeBhavya | PPS AR25 | Learning example */
#include <stdio.h>

int main(void)
{
    int a[2][3] = {{1, 2, 3}, {4, 5, 6}};
    for (int row = 0; row < 2; ++row) {
        for (int col = 0; col < 3; ++col) {
            if (col > 0) { putchar(' '); }
            printf("%d", a[row][col]);
        }
        putchar('\n');
    }
    return 0;
}

1 2 3
4 5 6

Related exam questions

Related questions in the multidimensional arrays category from the supplied papers. The marks below are the printed allocations, including any combined subquestion.

• July 2021 · Q3(a) · 7 marks

  Using a two-dimensional array, write a C program to transpose a 2 × 2 matrix.

  Paper P04 · page 1
• September 2023 · Q1(d) · 1 marks

  What is a two-dimensional array?

  Paper P06 · page 1

View this category in the exam question bank →

Algorithm

1. Read the common row and column counts and check their supported range.
2. Read all elements of A and B.
3. For each valid i and j, calculate C[i][j] = A[i][j] + B[i][j].
4. Display the result row by row.

Worked example

For A rows [1, 2] and [3, 4], and B rows [5, 6] and [7, 8], the result rows are [6, 8] and [10, 12]. Each result position uses only the two elements at that same position.

Function interface

The add function receives both input arrays, the output array and the active dimensions. All row widths are MAX because the actual objects are declared with that width. The function writes its results into C. Reading and validation are separated from the calculation.

Input limits

The sample accepts 1 through 5 rows and columns, with element values between -1000 and 1000. These bounds keep each sum within the minimum guaranteed range of int. A failed input read stops the program before calculation.

Time complexity

There are r × c output elements, and each requires one addition. Thus the addition routine takes O(rc) time. Reading and printing all elements have the same growth rate.

Space complexity

The separate result contains rc elements, so output storage is O(rc). Apart from that output, the addition uses O(1) auxiliary space for counters. This sample allocates fixed MAX-by-MAX arrays; the dimension-based description applies to the active matrix problem.

C program and output

/* CodeBhavya | PPS AR25 | Learning example */
#include <stdio.h>
#define MAX 5
int read_matrix(int a[][MAX], int rows, int cols)
{
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            if (scanf("%d", &a[i][j]) != 1 || a[i][j] < -1000 || a[i][j] > 1000) {
                return 0;
            }
        }
    }
    return 1;
}
void add(int a[][MAX], int b[][MAX], int c[][MAX], int rows, int cols)
{
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) { c[i][j] = a[i][j] + b[i][j]; }
    }
}

int main(void)
{
    int rows, cols, a[MAX][MAX], b[MAX][MAX], c[MAX][MAX];
    if (scanf("%d%d", &rows, &cols) != 2 || rows < 1 || rows > MAX || cols < 1 || cols > MAX) {
        puts("Unsupported dimensions"); return 1;
    }
    if (!read_matrix(a, rows, cols) || !read_matrix(b, rows, cols)) {
        puts("Unsupported input"); return 1;
    }
    add(a, b, c, rows, cols);
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            if (j > 0) { putchar(' '); }
            printf("%d", c[i][j]);
        }
        putchar('\n');
    }
    return 0;
}

2 2
1 2 3 4
5 6 7 8

6 8
10 12

Related exam questions

Related questions in the multidimensional arrays category from the supplied papers. The marks below are the printed allocations, including any combined subquestion.

• July 2021 · Q3(a) · 7 marks

  Using a two-dimensional array, write a C program to transpose a 2 × 2 matrix.

  Paper P04 · page 1
• September 2023 · Q1(d) · 1 marks

  What is a two-dimensional array?

  Paper P06 · page 1

View this category in the exam question bank →

Formula

C[i][j] = sum of A[i][t] * B[t][j]
          for t = 0 through inner - 1

Algorithm

1. Read both matrices’ dimensions. Require colsA == rowsB.
2. Read the two matrices within their allowed bounds.
3. For each result position i, j, set its running total to zero.
4. For each t, add A[i][t] × B[t][j].
5. Store and display the result.

Worked example

For A = [[1, 2], [3, 4]] and B = [[5, 6], [7, 8]], C[0][0] is 1×5 + 2×7 = 19. C[0][1] is 1×6 + 2×8 = 22. The second row is 43, 50. Each result is a dot product of one complete row and one complete column.

Initialisation and types

Set every result accumulator to zero before its inner loop. Otherwise a result might include an old or invalid value. The sample uses long long for the result and 1LL * a[i][t] * b[t][j] to perform the product in that type. Inputs are limited to magnitude 1000 and dimensions at most 5.

Time complexity

For r result rows and c result columns, each position requires k products and additions. The total is r × c × k, giving O(rkc) time. For square n × n matrices this becomes O(n³) for this basic method.

Space complexity

The output contains rc long long values. Output storage is O(rc), while the counters add O(1) auxiliary space beyond the inputs and output. Matrix multiplication is generally not commutative: reversing A and B may change the answer or make the dimensions incompatible.

Dimension table

Diagram or flowchart

C program and output

/* CodeBhavya | PPS AR25 | Learning example */
#include <stdio.h>
#define MAX 5
int read_matrix(int a[][MAX], int rows, int cols)
{
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            if (scanf("%d", &a[i][j]) != 1 || a[i][j] < -1000 || a[i][j] > 1000) {
                return 0;
            }
        }
    }
    return 1;
}
void multiply(int a[][MAX], int b[][MAX], long long c[][MAX],
              int rows, int inner, int cols)
{
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            c[i][j] = 0;
            for (int t = 0; t < inner; ++t) {
                c[i][j] += 1LL * a[i][t] * b[t][j];
            }
        }
    }
}

int main(void)
{
    int ra, ca, rb, cb, a[MAX][MAX], b[MAX][MAX];
    long long c[MAX][MAX];
    if (scanf("%d%d%d%d", &ra, &ca, &rb, &cb) != 4 ||
        ra < 1 || ra > MAX || ca < 1 || ca > MAX ||
        rb < 1 || rb > MAX || cb < 1 || cb > MAX) {
        puts("Unsupported dimensions"); return 1;
    }
    if (ca != rb) { puts("Incompatible dimensions"); return 1; }
    if (!read_matrix(a, ra, ca) || !read_matrix(b, rb, cb)) {
        puts("Unsupported input"); return 1;
    }
    multiply(a, b, c, ra, ca, cb);
    for (int i = 0; i < ra; ++i) {
        for (int j = 0; j < cb; ++j) {
            if (j > 0) { putchar(' '); }
            printf("%lld", c[i][j]);
        }
        putchar('\n');
    }
    return 0;
}

2 2 2 2
1 2 3 4
5 6 7 8

19 22
43 50

Related exam questions

Related questions in the matrix multiplication category from the supplied papers. The marks below are the printed allocations, including any combined subquestion.

• September/October 2021 · Q2(a) · 7 marks

  What is an array? Write a C program for matrix multiplication.

  Paper P01 · page 1
• March/April 2023 · Q5(b) · 5 marks

  Write a program to multiply two matrices of size 2 × 2.

  Paper P02 · page 1

View this category in the exam question bank →

Declaration

int a[2][3][4] = {0};
a[1][2][3] = 7;

Meaning of dimensions

The declaration creates two elements at the first level. Each is an array of three row arrays, and each row holds four integers. The valid index ranges are 0..1, 0..2 and 0..3. The assignment changes one selected int to 7. The {0} initialiser gives all elements zero before that assignment.

Storage and access

C arrays are nested contiguous arrays. The last subscript changes fastest through the element storage order. For dimensions x, y and z, the total element count is x × y × z, and storage is that product times sizeof(element). Every individual index must remain within its corresponding bound.

Traversal

Three nested loops can visit a three-dimensional array. The outer loop selects a group, the next selects a row and the inner selects an element. A direct selected access still has constant work in the usual model; visiting every position has work proportional to the total element count.

Complexity and uses

A full traversal takes O(xyz) time. If all dimensions equal n, it takes O(n³). Loop counters use O(1) auxiliary space when the number of dimensions is fixed. Such arrays can model several matrices, time-based tables or small grids. Choose dimensions carefully: increasing each dimension multiplies storage rather than merely adding a few elements.

C program and output

/* CodeBhavya | PPS AR25 | Learning example */
#include <stdio.h>

int main(void)
{
    int a[2][3][4] = {0};
    a[1][2][3] = 7;
    printf("Selected = %d\n", a[1][2][3]);
    printf("Elements = %zu\n", sizeof a / sizeof a[0][0][0]);
    return 0;
}

Selected = 7
Elements = 24

Related exam questions

Related questions in the multidimensional arrays category from the supplied papers. The marks below are the printed allocations, including any combined subquestion.

• July 2021 · Q3(a) · 7 marks

  Using a two-dimensional array, write a C program to transpose a 2 × 2 matrix.

  Paper P04 · page 1
• September 2023 · Q1(d) · 1 marks

  What is a two-dimensional array?

  Paper P06 · page 1

View this category in the exam question bank →

Fixed-width interface

void show(int a[][3], int rows);
/* equivalent parameter type: int (*a)[3] */

Meaning

The actual array has rows containing three ints. In the parameter, the outer array form adjusts to a pointer to one such row. The first bound may be omitted because the function receives a pointer, but the row width 3 describes the row type and the step used by a[i]. It must match the caller’s actual object.

Example explanation

main holds a 2-by-3 matrix and calls show(a, 2). The function visits two rows and three columns. The example prints the same matrix without copying the whole object. Since its parameter is not const-qualified, the function could modify elements, although this show function only reads them.

Capacity and active dimensions

In the matrix calculation programs, actual arrays have MAX columns even when only some columns are active. Their parameters therefore also use MAX as the row width. Passing cols as a logical count does not change the actual row width. C also supports other suitable dimension-aware forms, but this unit uses fixed-width parameters for clarity.

Important points and complexity

Do not cast an incompatible matrix to int ** or use a wrong row width. Pass and validate the row count separately. A display function for r rows and a fixed c-column width takes O(rc) time and O(1) auxiliary space beyond the input array.

C program and output

/* CodeBhavya | PPS AR25 | Learning example */
#include <stdio.h>
void show(int a[][3], int rows)
{
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < 3; ++j) {
            if (j > 0) { putchar(' '); }
            printf("%d", a[i][j]);
        }
        putchar('\n');
    }
}

int main(void)
{
    int a[2][3] = {{1, 2, 3}, {4, 5, 6}};
    show(a, 2);
    return 0;
}

1 2 3
4 5 6

Related exam questions

Related questions in the multidimensional arrays category from the supplied papers. The marks below are the printed allocations, including any combined subquestion.

• July 2021 · Q3(a) · 7 marks

  Using a two-dimensional array, write a C program to transpose a 2 × 2 matrix.

  Paper P04 · page 1
• September 2023 · Q1(d) · 1 marks

  What is a two-dimensional array?

  Paper P06 · page 1

View this category in the exam question bank →