Stage 7: Basic Algorithms in C++ - Manual Implementation

Basic Algorithms: The Foundation of Programming Logic

For your exam, you are prohibited from using ready-made solutions from the <algorithm> library (such as std::sort or std::copy). This means you must be able to implement these mechanisms yourself using loops and conditional statements.

1. Copying Arrays

Since arrays cannot be copied using the assignment operator (tab1 = tab2), we must iterate through each element individually.

cpp

void copyArray(int source[], int destination[], int size) {
    for (int i = 0; i < size; i++) {
        destination[i] = source[i];
    }
}

2. Linear Search

The simplest method to find an element in an unsorted array is linear search. The function should return the index of the found element or -1 if the element does not exist.

cpp

int findElement(int tab[], int size, int target) {
    for (int i = 0; i < size; i++) {
        if (tab[i] == target) return i; // Found!
    }
    return -1; // Not in the array
}

3. Bubble Sort

This is the most frequently required algorithm in introductory exams due to its simplicity. It involves comparing adjacent elements and swapping them if they are in the wrong order.

cpp

void bubbleSort(int tab[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (tab[j] > tab[j + 1]) {
                // Swap
                int temp = tab[j];
                tab[j] = tab[j + 1];
                tab[j + 1] = temp;
            }
        }
    }
}

4. Sequence Generation

Arithmetic Sequence

Each subsequent element differs by a constant value r.

cpp

void generateArithmetic(int tab[], int n, int start, int r) {
    for (int i = 0; i < n; i++) {
        tab[i] = start + i * r;
    }
}

Random Sequence (using <cstdlib> and <ctime>)

Remember to initialize the random number generator using srand(time(NULL)) in the main function.

cpp

void generateRandom(int tab[], int n, int max_value) {
    for (int i = 0; i < n; i++) {
        tab[i] = rand() % (max_value + 1);
    }
}

Key Exam Tips

Complexity: Bubble sort has a complexity of $O(n^2)$ . For very large arrays (e.g., 100,000 elements), it will be very slow, but for exam purposes (arrays of 100-1000 elements), it is sufficient.
Exit Condition: In linear search, always remember to return a value signaling an error (usually -1) if the loop finishes without finding a result.
Loop Ranges: In bubble sort, the inner loop should end at n - i - 1 because after each full iteration, the largest element "bubbles up" to the end and no longer needs to be checked.

Control Task:

Try writing a function that generates a Fibonacci sequence into an array of size N. Remember: tab[i] = tab[i-1] + tab[i-2].

Basic Algorithms: The Foundation of Programming Logic

1. Copying Arrays

Since arrays cannot be copied using the assignment operator (tab1 = tab2), we must iterate through each element individually.

cpp

void copyArray(int source[], int destination[], int size) {
    for (int i = 0; i < size; i++) {
        destination[i] = source[i];
    }
}

2. Linear Search

The simplest method to find an element in an unsorted array is linear search. The function should return the index of the found element or -1 if the element does not exist.

cpp

int findElement(int tab[], int size, int target) {
    for (int i = 0; i < size; i++) {
        if (tab[i] == target) return i; // Found!
    }
    return -1; // Not in the array
}

3. Bubble Sort

This is the most frequently required algorithm in introductory exams due to its simplicity. It involves comparing adjacent elements and swapping them if they are in the wrong order.

cpp

void bubbleSort(int tab[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (tab[j] > tab[j + 1]) {
                // Swap
                int temp = tab[j];
                tab[j] = tab[j + 1];
                tab[j + 1] = temp;
            }
        }
    }
}

4. Sequence Generation

Arithmetic Sequence

Each subsequent element differs by a constant value r.

cpp

void generateArithmetic(int tab[], int n, int start, int r) {
    for (int i = 0; i < n; i++) {
        tab[i] = start + i * r;
    }
}

Random Sequence (using <cstdlib> and <ctime>)

Remember to initialize the random number generator using srand(time(NULL)) in the main function.

cpp

void generateRandom(int tab[], int n, int max_value) {
    for (int i = 0; i < n; i++) {
        tab[i] = rand() % (max_value + 1);
    }
}

Key Exam Tips

Complexity: Bubble sort has a complexity of $O(n^2)$ . For very large arrays (e.g., 100,000 elements), it will be very slow, but for exam purposes (arrays of 100-1000 elements), it is sufficient.
Exit Condition: In linear search, always remember to return a value signaling an error (usually -1) if the loop finishes without finding a result.
Loop Ranges: In bubble sort, the inner loop should end at n - i - 1 because after each full iteration, the largest element "bubbles up" to the end and no longer needs to be checked.

Control Task:

Try writing a function that generates a Fibonacci sequence into an array of size N. Remember: tab[i] = tab[i-1] + tab[i-2].

Stage 7: Basic Algorithms in C++ - Manual Implementation

Basic Algorithms: The Foundation of Programming Logic

1. Copying Arrays

2. Linear Search

3. Bubble Sort

4. Sequence Generation

Arithmetic Sequence

Random Sequence (using <cstdlib> and <ctime>)

Key Exam Tips

Control Task:

You might also like

Stage 8: Basic Math Functions from the <cmath> Library

Stage 5: References and References as Function Parameters

Stage 1: Basic Data Types in C++ - A Comprehensive Guide

Stage 7: Basic Algorithms in C++ - Manual Implementation

Basic Algorithms: The Foundation of Programming Logic

1. Copying Arrays

2. Linear Search

3. Bubble Sort

4. Sequence Generation

Arithmetic Sequence

Random Sequence (using <cstdlib> and <ctime>)

Key Exam Tips

Control Task:

You might also like

Stage 8: Basic Math Functions from the <cmath> Library

Stage 5: References and References as Function Parameters

Stage 1: Basic Data Types in C++ - A Comprehensive Guide