NESTED LOOPS IN C++

Page Content

Welcome to the page dedicated to nested loops in C++! This page provides all the key information, code examples, and practical tips for working with nested loops, which are essential for iterating through complex data structures and multidimensional data. Using the table of contents, you can quickly jump to interesting sections and find the content that interests you.

Introduction

Nested loops are loops inside other loops. When one loop is inside the body of another loop, the inner loop executes completely for each iteration of the outer loop. This structure is used when iterating through complex data, such as arrays, lists of lists, or multidimensional arrays.

How do nested loops work?

The outer loop starts the first iteration.
When the outer loop enters the body, the inner loop starts and completes all its iterations.
After the inner loop completes, control returns to the outer loop, which moves on to the next iteration.
This process is repeated until the outer loop has completed all of its iterations.

When are they used?

Nested loops are useful in the following situations:

Iterate through two-dimensional data structures, such as arrays.
Generation of forms or tables.
Implementation of algorithms, such as sorting or searching in data structures.
Multidimensional data processing in games, graphics, or simulations.

Loops or cycles are commands whose role is to repeat one or more other commands a certain number of times. Those repeating statements are written in the body of the for loop. It can be any other command, and therefore a new for command.
Let us now look at the next task

Basic Structure of Nested Loops

Nested loops are structures where one loop is placed inside another. This concept enables iteration through multidimensional data structures, such as matrices, where the outer loop manages rows, and the inner loop manages columns.

The key elements of this structure are:

Initialization and condition of the outer loop for iterating through rows.
Initialization and condition of the inner loop for iterating through columns of each row.
Processing of each element in the matrix within the body of the inner loop.

Consider the following C++ example that illustrates the basic structure of nested loops:


for (int i = 0; i < broj_redova; i++) {
    for (int j = 0; j < broj_kolona; j++) {
        // Processing the element at position [i][j]
        std::cout << matrica[i][j] << " ";
    }
    std::cout << std::endl;
}

In this example, the outer loop controls the rows of the matrix, while the inner loop iterates through the columns of each row. This approach allows for systematic processing of each element in a two-dimensional structure.

Notes:

Ensure proper initialization and conditions for the loops to avoid infinite iterations.
In the case of multidimensional structures, excessive depth of nested loops can reduce code readability and affect performance.
Consider using functions or modularizing the code for more complex operations to keep the code organized.

Examples of nested loops

Example 1: Writing numbers by rows and columns

Task: Write the first 100 natural numbers in 10 rows and 10 columns.

This task can be done without nested loops. See example on Loops in C/C++ examples
However, we will show here how the same example can be done using nested loops.

To print a number, we use the cout command:

cout << number << " ";

To print one row, we use a for loop in which we will mark the control variable with the letter j, and this will also represent the row number of the column of the matrix to be printed:

for(int j=1; j<=10; j++)
{

cout << number << " ";

}
cout << endl;

This will print 1 line. This should now be repeated 10 times, for each row. For that we will use another loop, so that the previous statements are in the body of that loop, ie between the curly brackets. The control variable of the outer loop that we'll label with i will be the line number minus 1, so it changes from 0 to 9.
The number variable should be associated with both j and i as follows:
number =10 * i + j;
When the first row is printed, i=0, so numbers are printed that only depend on the current column j, so that 1 is printed in the 1st column, 2 in the 2nd column, etc.
In the next row, values that are greater than the values of the previous row by 1*10 are printed, so that we get 11, 12, 13,...
In each next row, the numbers are 10 higher than in the previous one.

int number;
for(int i=0; i<10; i++)
{

for(int j=1; j<=10; j++)
{

number = 10*i + j;
cout << number << " ";

}
cout << endl;

}

Example 2: Generating the Multiplication Table

Task: Write a program that will print the multiplication table on the screen

Explanation:
The code to generate the multiplication table uses nested loops where the outer loop iterates through the rows and the inner loop iterates through the columns.

#include <iostream>
using namespace std;

// Program for generating a multiplication table
int main() {

int n = 10; // Size of the multiplication table

for (int i = 1; i <= n; i++) {

for (int j = 1; j <= n; j++) {

cout << i * j << "\t";

}
cout << endl;

}

return 0;

}

Test your code in the editor!

// Write your C++ code here...

Enter input for the program:

Example 3: Drawing a Star Pattern

The code to draw the star triangle uses nested loops where the inner loop specifies the number of stars per row.

#include <iostream>
using namespace std;

// Program for drawing a star triangle
int main() {

int n = 5; // Height of the triangle

for (int i = 1; i <= n; i++) {

for (int j = 1; j <= i; j++) {

cout << "*";

}
cout << endl;

}

return 0;

}

Solution explanation:

First step: Start by defining the number of rows in the form. In this task, the number of rows (n) should be entered by the user.
Step Two: Use an outer loop (for) to iterate through the rows. The number of rows should be equal to the entered value n.
Step Three: For each row, inside the outer loop, use an inner loop that will print the corresponding number of stars. In each subsequent row, the number of stars should be one more than in the previous one.
Step Four: After the inner loop is finished, move to the next row and repeat the process.

Example 4: Looping through a Two-Dimensional Array

Task: Write a C++ program that uses nested loops to loop through a two-dimensional array. The program needs to enter the dimensions of the array (number of rows and number of columns) and then fill the array with the values entered by the user. Finally, the program should display the contents of the array.

Example for dimension 3x3

Enter the number of rows: 3
Enter the number of columns: 3
Enter the matrix elements:
1 2 3
4 5 6
7 8 9
The matrix elements are:
1 2 3
4 5 6
7 8 9

The code for printing the elements of a two-dimensional array demonstrates the implementation of nested loops for processing matrices.

#include <iostream>
using namespace std;

// Program for iterating through a two-dimensional array
int main() {

int matrix[3][3] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}; // 3x3 matrix

for (int i = 0; i < 3; i++) {

for (int j = 0; j < 3; j++) {

cout << matrix[i][j] << " ";

}
cout << endl;

}

return 0;

}

Code explanation

Entering the dimensions of the matrix: The program first asks the user to enter the number of rows n and the number of columns m.
Creating a matrix: A two-dimensional array of matrices[n][m] is created, where n is the number of rows and m is the number of columns.
Inputting elements: Two nested loops are used to input matrix elements. The outer loop iterates through the rows, while the inner loop inputs values for each element in that row.
Print the matrix: Another nested loop is used to print the elements of the matrix. The inner loop prints the values in one row, while the outer loop moves to the next row.

Explanation of More Complex Scenarios Using Nested Loops

1. Iteration Through Two-Dimensional Arrays

One of the most common scenarios for using nested loops is working with two-dimensional arrays (matrices). A two-dimensional array can be thought of as a table with rows and columns. Each value in the table can be accessed using two indexes: one for rows and one for columns.

#include <iostream>
using namespace std;

// Program for printing a two-dimensional array
int main() {

const int rows = 3, cols = 3;
int matrix[rows][cols] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}; // Declare and initialize the matrix

cout << "Printing a two-dimensional array:" << endl;

for (int i = 0; i < rows; i++) {

for (int j = 0; j < cols; j++) {

cout << matrix[i][j] << " "; // Print matrix element

}
cout << endl; // Move to the next line

}

return 0; // End of program

}

This program uses two loops: the outer loop goes through the rows and the inner loop through the columns of the matrix. This allows access to each element of a two-dimensional array.

2. Implementation of Algorithms with Multiple Levels of Loops

#include <iostream>
using namespace std;

// Main function implementing the Bubble Sort algorithm
int main() {

// Define an array to be sorted
int arr[] = {5, 2, 9, 1, 5, 6};
int n = sizeof(arr) / sizeof(arr[0]);

// Display the original array before sorting
cout << "Original array: ";
for (int i = 0; i < n; i++) {

cout << arr[i] << " ";

}
cout << endl;

// Bubble Sort algorithm
for (int i = 0; i < n - 1; i++) {

// Inner loop compares adjacent elements
for (int j = 0; j < n - i - 1; j++) {

// Swap elements if the current one is greater than the next
if (arr[j] > arr[j + 1]) {

int temp = arr[j]; // Temporarily store the current value
arr[j] = arr[j + 1]; // Swap current element with the next
arr[j + 1] = temp; // Assign stored value to the next position

}

}

// Display the sorted array
cout << "Sorted array: ";
for (int i = 0; i < n; i++) {

cout << arr[i] << " ";

}
cout << endl;

// Return 0 to indicate successful execution
return 0;

}

This code implements the Bubble Sort algorithm using nested loops:

The outer loop repeats the sorting process for each element.
The inner loop compares adjacent elements and swaps them if they are not in the correct order.

Warnings about Potential Errors with Nested Loops

When working with nested loops, errors often occur that can cause the program to malfunction or lead to unexpected results. Here are the most common mistakes and tips on how to avoid them:

1. Infinite Loops

If the loop does not have a valid termination condition, it can execute indefinitely, which will stop the program from continuing.

Common cause:

Forgotten control variable value change.
Incorrectly defined conditions for exiting the loop.

An example of an error

for (int i = 0; i < 5; /* Missing increment: i++ */) {

cout << i << endl;

}

Solution:

Check that the control variable changes correctly within each iteration

for (int i = 0; i < 5; i++) {

cout << i << endl;

}

2. Improperly Initialized Variables

If the variable controlling the loop is not initialized properly, it can cause unexpected results.

Example of a code error

int j;
for (int i = 0; i < 3; i++) {

j += i; // The variable 'j' is not initialized

}

Solution:

Initialize variables before using them:

int j = 0;
for (int i = 0; i < 3; i++) {

j += i;

}

3. Unnecessarily Large Number of Iterations

When the iteration conditions are incorrectly defined, the loop can perform more iterations than necessary, which slows down the program significantly.

Example error:

for (int i = 0; i < 1000; i++) {

for (int j = 0; j < 1000; j++) {

cout << i * j << endl;

}

Solution:

Check conditions and optimize iterations, using only those that are necessary.

4. Dependence of Control Variables

When one loop uses the control variable of another loop, unpredictable behavior can occur.

Example error:

for (int i = 0; i < 5; i++) {

for (int j = 0; j < i; j++) {

i++; // The 'i' is changed inside the inner loop

}

Solution:

Maintain independence of control variables.

5. Break Statement

Incorrect use of break can cause an unexpected termination of the execution of the inner loop.

Example of a code error:

for (int i = 0; i < 3; i++) {

for (int j = 0; j < 3; j++) {

if (j == 1) break;
cout << j << endl;

}

Solution:

Check the logic of the condition for stopping the execution.

More examples in this area can be found on the web page: Nested loops in C/C++ examples

Advanced Uses of Nested Loops in C++

Nested Loops in Sorting Algorithms

Nested loops are often used in sorting algorithms, such as Bubble Sort.

#include <iostream>

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

int main() {
    int array[] = {5, 3, 8, 4, 2};
    int n = sizeof(array) / sizeof(array[0]);
    
    bubbleSort(array, n);
    
    std::cout << "Sorted array: ";
    for (int i = 0; i < n; i++) {
        std::cout << array[i] << " ";
    }
    std::cout << "\n";
    
    return 0;
}

Finding Triplets of Numbers with a Given Sum

Nested loops are frequently used in combinatorial problems. The following example finds all triplets of numbers in an array whose sum equals a given value.

#include <iostream>

void findTriplets(int arr[], int n, int target) {
    for (int i = 0; i < n - 2; i++) {
        for (int j = i + 1; j < n - 1; j++) {
            for (int k = j + 1; k < n; k++) {
                if (arr[i] + arr[j] + arr[k] == target) {
                    std::cout << "Triplet: " << arr[i] << ", " << arr[j] << ", " << arr[k] << "\n";
                }
            }
        }
    }
}

int main() {
    int array[] = {1, 4, 6, 8, 3, 7};
    int target = 15;
    int n = sizeof(array) / sizeof(array[0]);
    
    findTriplets(array, n, target);
    
    return 0;
}

Conclusion

Nested loops enable the solving of complex problems such as sorting and combinatorial tasks. The efficiency of an algorithm depends on the number of iterations, so it's important to consider optimizations when working with large datasets.

Explanation of the Code

This code searches through all possible triplet combinations from the array and checks if their sum matches the given target value.

First loop (i from 0 to n-2)

Sets the first number of the triplet.

Second loop (j from i + 1 to n-1)

Sets the second number of the triplet.

Third loop (k from j + 1 to n)

Sets the third number of the triplet.

Condition check (arr[i] + arr[j] + arr[k] == targetSum)

If the sum of the numbers equals targetSum, the triplet is printed.

Example with an array

Array: [1, 5, 3, 7, 2, 4, 6], targetSum = 12

Possible triplets that sum to 12 are:

(1, 5, 6)
(1, 4, 7)
(3, 4, 5)

Relation to Combinatorics

This problem falls into combinatorial problems as it requires checking all possible combinations of three elements from a set.

Number of Possible Combinations

If we have n elements, the number of ways to choose three elements (without considering the order) can be calculated using the combinatorial coefficient:

C(n, 3) = n! / (3!(n − 3)!) = n(n − 1)(n − 2) / 6

In the Code

The triple loop goes through all possible combinations, resulting in a time complexity of O(n³).

Problem Optimization

Sorting + Two Pointers Method – O(n²)
This can be improved by first sorting the array and then using the two pointers method instead of the third loop.

Hash Map Method – O(n²)
Instead of the third loop, we can use a hash table for a faster check of targetSum - (arr[i] + arr[j]).

Conclusion

This example demonstrates how nested loops are used in combinatorial problems. Although this approach is simple, it may be inefficient for large arrays. Optimizations such as the "Two Pointers" method or using a hash table can improve performance.

In the following example of the optimized version of the code for finding triplets that sum to a given number, sorting and the two-pointer technique are used to achieve better efficiency compared to three nested loops.


        #include <iostream>
        #include <algorithm>  // For sort() function

        void findTriplets(int arr[], int n, int targetSum) {
            // First, sort the array
            std::sort(arr, arr + n);

            for (int i = 0; i < n - 2; i++) {
                // If the current element is the same as the previous one, skip it to avoid duplicates
                if (i > 0 && arr[i] == arr[i - 1]) {
                    continue;
                }

                int left = i + 1; // Left pointer
                int right = n - 1; // Right pointer

                while (left < right) {
                    int sum = arr[i] + arr[left] + arr[right];

                    if (sum == targetSum) { // If the sum is equal to the target number, print the triplet
                        std::cout << "Triplet: (" << arr[i] << ", " << arr[left] << ", " << arr[right] << ")\n";
                        left++;
                        right--;

                        // Skip duplicates
                        while (left < right && arr[left] == arr[left - 1]) left++;
                        while (left < right && arr[right] == arr[right + 1]) right--;
                    }
                    else if (sum < targetSum) { // If the sum is smaller than the target, move the left pointer
                        left++;
                    }
                    else { // If the sum is greater, move the right pointer
                        right--;
                    }
                }
            }
        }

        int main() {
            int arr[] = {1, 5, 3, 7, 2, 4, 6};
            int n = sizeof(arr) / sizeof(arr[0]);
            int targetSum = 12;

            findTriplets(arr, n, targetSum);

            return 0;
        }

Explanation of the Optimized Code:

Sorting the array: First, we sort the array, which allows the use of two pointers.
Skipping duplicates: If the current element is the same as the previous one, we skip it to avoid duplicates in the output.
Two-pointer technique: After selecting the first element of the triplet, we set two pointers, one at the next element and the other at the last element. Then, we move the pointers based on the sum of the numbers in relation to the target sum.
Time complexity: This optimization reduces the complexity from \(O(n^3)\) to \(O(n^2)\), which significantly improves efficiency for larger arrays.

This optimized version is much faster for larger arrays because it uses sorting and two pointers to reduce the number of checks.

Previous
|< Nested loops in C++

Next
Arrays in C++ >|

NESTED LOOPS IN C++

Page Content

Introduction

How do nested loops work?

When are they used?

Basic Structure of Nested Loops

Examples of nested loops

Example 1: Writing numbers by rows and columns​

​Example 2: Generating the Multiplication Table

Test your code in the editor!

​​Example 3: Drawing a Star Pattern

Solution explanation:

​​​Example 4: Looping through a Two-Dimensional Array

Code explanation​

​​​​Explanation of More Complex Scenarios Using Nested Loops

1. Iteration Through Two-Dimensional Arrays

2. Implementation of Algorithms with Multiple Levels of Loops

​​​​​Warnings about Potential Errors with Nested Loops

1. Infinite Loops

An example of an error

Solution:

2. Improperly Initialized Variables

Example of a code error

Solution:

3. Unnecessarily Large Number of Iterations

Example error:

Solution:

4. Dependence of Control Variables

Example error:

Solution:

5. Break Statement

Example of a code error:

Solution:

Advanced Uses of Nested Loops in C++

Nested Loops in Sorting Algorithms

Finding Triplets of Numbers with a Given Sum

Conclusion

Explanation of the Code

First loop (i from 0 to n-2)

Second loop (j from i + 1 to n-1)

Third loop (k from j + 1 to n)

Condition check (arr[i] + arr[j] + arr[k] == targetSum)

Example with an array

Possible triplets that sum to 12 are:

Relation to Combinatorics

Number of Possible Combinations

In the Code

Problem Optimization

Conclusion

Cookie settings

Example 1: Writing numbers by rows and columns

Example 2: Generating the Multiplication Table

Example 3: Drawing a Star Pattern

Example 4: Looping through a Two-Dimensional Array

Code explanation

Explanation of More Complex Scenarios Using Nested Loops

Warnings about Potential Errors with Nested Loops