Lesson 07: Arrays

Defining an Array

You may declare arrays of any data type, including classes. The general form of a singly dimensioned array is:

type variable [size];
type variable [size] = {initValue1, initValue2, … };

Where type specifies the data type of each element in the array, and size specifies the number of elements in the array.

In C/C++, the name of an array always points to the first element of an array. Here, the address of the first element of an array is &age[0]. Also, age represents the address of the pointer where it is pointing. Hence, &age[0] is equivalent to age.

C arrays can be of any type. We define an array of ints, chars, doubles, etc. We can also define an array of pointers as follows. Here is the code to define an array of n char pointers or an array of strings.

char* A[n];

What are Array Elements?

An array is a collection of elements of the same data type stored in contiguous memory locations. Each element in an array has a unique index, which is a non-negative integer starting from 0. These elements are an array's building blocks and represent the data stored in the array structure.

Understanding Array Element Indexing

Indexing is a crucial aspect of accessing and manipulating array elements. Each element in an array is identified by its index, which serves as a pointer to its location in memory. The index of the first element is 0, the index of the second element is 1, and so on. This pattern continues until the last element, which has an index of n-1, where n is the size of the array.

Accessing Array Elements

Accessing an array element involves specifying its index within square brackets []. The index should be within the valid range of 0 to n-1, where n is the size of the array. For instance, to access the third element of an integer array named numbers, you would use:

int numbers[20];                // An integer array of 20 elements
int thirdElement = numbers[2];  // first element of array num
int lastElement  = numbers[19]; // last (20th) element of array num

In this statement, the index 2 refers to the third element of the array, and the value of this element is assigned to the variable thirdElement.

Initializing Array Elements

Arrays can be initialized by using a bracketed list of initializers. For example,

int coins[6] = { 1, 5, 10, 25, 50, 100};

The first element is initialized to 1, the second to 5, etc.

The number of values between brackets ({}) can not be larger than the number of elements that we declare for the array between square brackets ([]).

You can also ignore the array size when you have a set of initialization values. The compiler will automatically calculate the size of the elements by counting the number of initial values.

int score[] = { 1, 5, 10, 25, 50, 100};

When setting the initial value of an array, if the number of set initial values is less than the number of elements of the array, the values of the rest of the elements will be directly filled with 0.

int num[5] = { 5, 10};  // num[] = {5, 10, 0, 0, 0}

Initializing Array to Zero

The array will be initialized to 0 in case we provide an empty initializer list or specify 0 in the initializer list.

int array[5] = {};     // initialize 5 ints to 0 -> array[5] = {0, 0, 0, 0, 0}
int array[5] = {0};    // initialize 5 ints to 0 -> array[5] = {0, 0, 0, 0, 0}

Designated Initializer (Supported by C++Builder)

This initializer is used to initialize a range of elements with the same value.  (Not all compilers support this function)

int num[5] = {[1 ... 2] = 3};       // num[5] = {0, 3, 3, 0, 0}
int num[5] = {[0 ... 4] = 2};       // num[5] = {2, 2, 2, 2, 2}

You may also ignore the size of the array.

int num[] = {[1 ... 2] = 3};       // num[3] = {0, 3, 3}
int num[] = {[0 ... 4] = 2};       // num[5] = {2, 2, 2, 2, 2}

You can assign different index elements with different initial values as follows:

int x = 1233;
int a[10] = { [9] = x + 1, [2] = 3, [1] = 2, [0] = 1 };

Define a 10 elements array and initialize the last element to the value of x + 1 (or to 1234) and the first three elements to 1, 2, and 3, respectively.

Accessing Array Elements

All arrays consist of contiguous memory locations. The lowest address corresponds to the first element, and the highest address to the last element. All the elements can be accessed by indexing the array name. This is done by placing the element's index within square brackets ([]) after the array's name. For example, we declare an integer array score with 6 elements and initialization values as shown below:

int score[6] = { 69, 71, 88, 74, 60, 83};

 The array variable score points to the address of the first elements of the array, which is the same as the address of the score[0].

Suppose the starting address of the score[0] is $1000. Then, the address of the score[1] will be $1004. Similarly, the address of the score[2] will be $1008, and so on. This is because the size of an int is 4 bytes.

Each element in the array can be accessed using an index number. But you cannot directly use an assignment operator (=) to assign one array to another. You have to set each individual element.

int arr1[5];
int arr2[5] = { 3, 6, 4, 5, 8};

arr1 = arr2;                // Error, you can not assign one array to another one
arr1[0] = arr2[0];          // correct
arr1[1] = 57;               // set the index number 1 of element (the 2nd element) to 57
arr2[2] = 78;               // set the index number 2 of element (the 3rd element) to 78
sum = arr1[1] + arr2[2];    // add arr1[1] with arr2[2] together, then assign the result to the sum
float temp[8];              // declare a float array with 8 elements

The two-dimensional (2D) array is also known as a matrix. A matrix can be represented as a table of rows and columns.

type  variable[rows][cols];

For example:

float x[2][4];

Here, we declared a two-dimensional array named x. The array can hold 8 elements. This array is the same as a table with 2 rows, and each row has 4 elements, as shown below:

Initialization of a 2-D array

// Different ways to declare a 2D array with initialization values

int a[2][3] = { { 1,  3,  0},
                {-1,  5,  9}};

int b[][3]  = { { 1,  3,  0},
                {-1,  5,  9}};

int c[2][3] = {   1,  3,  0,  -1,  5,  9}};

Here, x is a two-dimensional array. The array can hold 6 elements.

// C program to find the sum of two matrices of order 2*2

#include <stdio.h>

int main()
{
    float   a[2][2], b[2][2], result[2][2];
    int     i, j;

    // Taking input using nested for loop
    printf("Enter elements of 1st matrix. \n");
    
    for (i = 0; i < 2; ++i)
        for (j = 0; j < 2; ++j) {
            printf("Enter a[%d][%d]: ", i, j);
            scanf("%f", &a[i][j]);
        }

    // Taking input using nested for loop
    printf( "Enter elements of 2nd matrix. \n");
    for (i = 0; i < 2; ++i)
        for (j = 0; j < 2; ++j) {
            printf( "Enter b[%d][%d]: ", i, j);
            scanf("%f", &b[i][j]);
        }

    // adding corresponding elements of two arrays
    for (i = 0; i < 2; ++i)
        for (j = 0; j < 2; ++j) {
            result[i][j] = a[i][j] + b[i][j];
        }

    // Displaying the sum
    printf ("\nSum of Matrix: \n");

    for ( i = 0; i < 2; ++i) {
        for ( j = 0; j < 2; ++j)
            printf("%8.2f", result[i][j]);
        printf("\n");
    }
    return 0;
}

// C++ program to find the sum of two matrices of order 2*2

#include <stdio.h>
#include <iostream>
#include <iomanip>
using namespace std;

int main()
{
    float   a[2][2], b[2][2], result[2][2];
    int     i, j;

    // Taking input using nested for loop
    cout << "Enter elements of 1st matrix." << endl;
    
    for (i = 0; i < 2; ++i)
        for (j = 0; j < 2; ++j) {
            cout << "Enter a["<< i << "][" << j << "]: ";
            cin >> a[i][j];
        }

    // Taking input using nested for loop
    cout << "Enter elements of 2nd matrix." << endl;
    for (i = 0; i < 2; ++i)
        for (j = 0; j < 2; ++j) {
            cout << "Enter b[" << i << "][" << j <<"]: ";
            cin >> b[i][j];
        }

    // adding corresponding elements of two arrays
    for (i = 0; i < 2; ++i)
        for (j = 0; j < 2; ++j) {
            result[i][j] = a[i][j] + b[i][j];
        }

    // Displaying the sum
    cout << endl;
    cout << "Sum of Matrix: " << endl;

    for ( i = 0; i < 2; ++i) {
        for ( j = 0; j < 2; ++j)
            cout << setw(8) << setprecision(2) << fixed << result[i][j];
        cout << endl;
    }
    return 0;
}

The three-dimensional (3D) array is also known as a matrix. A matrix can be represented as a table of rows and columns.

type  variable[page][rows][cols];

For example:

float x[2][3][4];

Here, we declared a three-dimensional array named x. The array can hold 24 elements. This array is the same as a table with two pages; each page has three rows, and each row has four elements, as shown below:

Initialization of a 3-D array

// Different ways to declare a 3D array with initialization values

int x[2][3][4] = {{{  3,  4,  2,  3},
                   {  0, -3,  9, 11},
                   { 23, 12, 23,  2}},
                  {{ 13,  4, 56,  3},
                   {  5,  5,  3,  5},
                   {  3,  1,  4,  9}}};

int y[][3][4]  = {{{  3,  4,  2,  3},
                   {  0, -3,  9, 11},
                   { 23, 12, 23,  2}},
                  {{ 13,  4, 56,  3},
                   {  5,  5,  3,  5},
                   {  3,  1,  4,  9}}};

int z[2][3][4] = { 3, 4, 2, 3, 0, -3, 9, 11, 23, 12, 23, 2, 13, 4, 56, 3, 5, 5, 3, 5, 3, 1, 4, 9};

#include <stdio.h>
#include <iostream>
#include <iomanip>
using namespace std;

int main()
{
    int x[2][3][4] = {{{  3,  4,  2,  3},
                       {  0, -3,  9, 11},
                       { 23, 12, 23,  2}},
                      {{ 13,  4, 56,  3},
                       {  5,  5,  3,  5},
                       {  3,  1,  4,  9}}};

    int y[][3][4]  = {{{  3,  4,  2,  3},
                       {  0, -3,  9, 11},
                       { 23, 12, 23,  2}},
                      {{ 13,  4, 56,  3},
                       {  5,  5,  3,  5},
                       {  3,  1,  4,  9}}};

    int z[2][3][4] = { 3, 4, 2, 3, 0, -3, 9, 11, 23, 12, 23, 2, 13, 4, 56, 3, 5, 5, 3, 5, 3, 1, 4, 9};
    int i, j, k;

    cout << "x[][][]" << endl << endl;
    for (i = 0; i < 2; i++) {
        for (j = 0; j < 3; j++) {
            for (k =0; k < 4; k++) {
                cout << setw(4) << x[i][j][k];
            }
            cout << endl;
        }
        cout << endl;
    }
    cout << endl;
    cout << "y[][][]" << endl << endl;

    for (i = 0; i < 2; i++) {
        for (j = 0; j < 3; j++) {
            for (k =0; k < 4; k++) {
                cout << setw(4) << y[i][j][k];
            }
            cout << endl;
        }
        cout << endl;
    }
    cout << endl;
    cout << "z[][][]" << endl << endl;

    for (i = 0; i < 2; i++) {
        for (j = 0; j < 3; j++) {
            for (k =0; k < 4; k++) {
                cout << setw(4) << z[i][j][k];
            }
            cout << endl;
        }
        cout << endl;
    }
    cout << endl;
    return 0;
}

Declaration of a Multidimensional Array in C/C++:

type variable[size1][size2][size3] … [sizeN];

 Where size1, size2, …, sizeN are the size of each dimension.

For example:

A 4-D array can be used to store a collection of data in Game design. For example, store 3D coordinates and 1D time into 4D arrays for each car in the game,[x][y][z][time]; then, we can use these arrays to check whether there is a collision that occurred between two vehicles or not.

Passing Arrays to Functions

In C/C++, arrays cannot be directly passed to functions as values. Instead, you pass the address of the first element of the array, which is essentially treated as a pointer to the array. This approach allows the function to access and modify the array elements.

void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
}
//------------------------------------------------------------------------------
int main() {
    int numbers[] = {1, 2, 3, 4, 5};
    int size = sizeof(numbers) / sizeof(int);
    printArray(numbers, size);
    return 0;
}

In this example, the printArray function takes an integer array arr and its size size as parameters. The function then iterates through the array and prints each element using the printf function.

Standard Library Array Functions (C++)

The C++ Standard Library provides a rich collection of array functions that cater to various array operations. These functions are defined in the <algorithm> header file and offer a wide range of functionalities, including:

• std::copy: Copies elements from one array to another.
• std::fill: Fills an array with a specified value.
• std::find: Searches for an element in an array.
• std::count: Counts the occurrences of an element in an array.
• std::sort: Sorts an array in ascending or descending order.
• std::reverse: Reverses the order of elements in an array.

These functions greatly simplify array manipulation tasks and promote code reusability.

int sumArray(int arr[], int size) {
    int sum = 0;
    for (int i = 0; i < size; i++) {
        sum += arr[i];
    }
    return sum;
}
//------------------------------------------------------------------------------
int main() {
    int data[] = {10, 20, 30, 40, 50};
    int size = sizeof(data) / sizeof(int);
    int totalSum = sumArray(data, size);

    printf("The sum of the array elements is: %d", totalSum);
    return 0;
}

void sortArray(int arr[], int size) {
    std::sort(arr, arr + size);
}
//------------------------------------------------------------------------------
int main() {
    int numbers[] = {5, 2, 4, 1, 3};
    int size = sizeof(numbers) / sizeof(int);

    sortArray(numbers, size);
    printf("The sorted array is: ");
    for (int i = 0; i < size; i++) {
        printf("%d ", numbers[i]);
    }
    return 0;
}

Matrix Addition — Both matrices should have the same size

Matrices of different sizes can not be added because the sum of two matrices is defined only when both have the same number of rows and columns.

Algorithm to Add Two Matrices

for i = 0 to (rows - 1)
    for j = 0 to (cols - 1)
        C[i][j] = A[i][j] + B[i][j]

Matrix Subtraction — Both matrices should have the same size.

Matrices of different sizes cannot be subtracted because the subtraction of two matrices is defined only when both matrices have the same number of rows and the same number of columns.

Algorithm to Add Two Matrices

for i = 0 to (rows - 1)
    for j = 0 to (cols - 1)
        C[i][j] = A[i][j] - B[i][j]

Matrix Multiplication

The product of two matrices is not defined when the number of columns in the first matrix and the number of rows in the second matrix are different.

${C_{m \times n}} = {A_{m \times p}} \times {B_{p \times n}} = \left[ {{C_{i,j}}} \right]$
\( \Rightarrow {C_{i,j}} = {a_{i,0}} \cdot {b_{0,j}} + {a_{i,1}} \cdot {b_{1,j}} + \cdots + {a_{i,k}} \cdot {b_{k,j}}\)
\( \Rightarrow {C_{i,j}} = \left[ {\sum\limits_{k = 0}^{p-1} {{a_{i ,k }} \cdot {b_{k ,j}}} } \right]\)

$C = A \times B = \left[ {\matrix{
{{a_{00}} \times {b_{00}} + {a_{01}} \times {b_{10}} + {a_{02}} \times {b_{20}}} & {{a_{00}} \times {b_{01}} + {a_{01}} \times {b_{11}} + {a_{02}} \times {b_{21}}} \cr
{{a_{10}} \times {b_{00}} + {a_{11}} \times {b_{10}} + {a_{12}} \times {b_{20}}} & {{a_{10}} \times {b_{01}} + {a_{11}} \times {b_{11}} + {a_{12}} \times {b_{21}}} \cr
} } \right]$

Algorithm to Multiply Two Matrices

for i = 0 to (m - 1)
    for j = 0 to (n - 1)
        for k = 0 to (p - 1)
            C[i][j] += A[i][k] * B[k][j]

Matrix Transpose

Let A =[a_ij] be an m × n matrix. The transpose of A, denoted by A^T, is the n × m matrix obtained by interchanging the rows and columns of A.

Algorithm for Matrix Transpose

for i = 0 to (n - 1)
    for j = 0 to (m - 1)
        C[i][j] = A[j][i]

The determinant of a matrix is the scalar value computed for a given square matrix. Linear algebra deals with the determinant computed using the elements of a square matrix. It can be considered the scaling factor for the transformation of a matrix. Useful in solving a system of linear equations, calculating the inverse of a matrix, and calculus operations.

The determinant of a matrix A,

\[\left[ {\matrix{
{{a_{00}}} & {{a_{01}}} & \cdots & {{a_{0(n - 1)}}} \cr
{{a_{10}}} & {{a_{11}}} & \ldots & {{a_{1(n - 1)}}} \cr
\vdots & \vdots & \ddots & \vdots \cr
{{a_{(n - 1)0}}} & {{a_{(n - 1)1}}} & \cdots & {{a_{(n - 1)(n - 1)}}} \cr
} } \right]\]

is commonly denoted \(det(A)\).

If the \(det(A)\) is 0, the matrix is singular, and if the \(det(A)\) is 1, the matrix is unimodular.

A 2×2 determinant is defined to be: \(\det \left( {\left[ {\matrix{{{a_{00}}} & {{a_{01}}} \cr{{a_{10}}} & {{a_{11}}} \cr} } \right]} \right) = {a_{00}} \times {a_{11}} - {a_{01}} \times {a_{10}}\)

An n×n matrix determinant can be expanded to obtain:

$\eqalign{
& \left[ {\matrix{
{{a_{00}}} & {{a_{01}}} & \cdots & {{a_{0(n - 1)}}} \cr
{{a_{10}}} & {{a_{11}}} & \ldots & {{a_{1(n - 1)}}} \cr
\vdots & \vdots & \ddots & \vdots \cr
{{a_{(n - 1)0}}} & {{a_{(n - 1)1}}} & \cdots & {{a_{(n - 1)(n - 1)}}} \cr
} } \right] = {a_{00}} \times \left[ {\matrix{
{{a_{11}}} & {{a_{12}}} & \cdots & {{a_{1(n - 1)}}} \cr
\vdots & \vdots & \ddots & \vdots \cr
{{a_{(n - 1)1}}} & {{a_{(n - 1)2}}} & \cdots & {{a_{(n - 1)(n - 1)}}} \cr
} } \right] - {a_{01}} \times \left[ {\matrix{
{{a_{10}}} & {{a_{12}}} & \cdots & {{a_{1(n - 1)}}} \cr
\vdots & \vdots & \ddots & \vdots \cr
{{a_{(n - 1)0}}} & {{a_{(n - 1)2}}} & \cdots & {{a_{(n - 1)(n - 1)}}} \cr
} } \right] \cr
& + \cdots \pm {a_{0(n - 1)}} \times \left[ {\matrix{
{{a_{10}}} & {{a_{11}}} & \cdots & {{a_{1(n - 2)}}} \cr
\vdots & \vdots & \ddots & \vdots \cr
{{a_{(n - 1)0}}} & {{a_{(n - 1)1}}} & \cdots & {{a_{(n - 1)(n - 2)}}} \cr
} } \right] \cr} $

A general determinant for a matrix A has a value:

\(\det (A) = \left| A \right| = \mathop \sum \limits_{i = 0}^n {a_{ij}}\,{C_{ij}} = \mathop \sum \limits_{i = 0}^n {a_{ij}}\, \cdot {( - 1)^{i + j}}{M_{ij}}\)

// C program to find Determinant of a matrix
#include <stdio.h> 
#define N 4     // Dimension of input square matrix
// Function to get cofactor of mat[p][q] 
// in temp[][]. n is current dimension of mat[][]
void getCofactor(int mat[N][N], int temp[N][N], int p, int q, int n)
{
    int i = 0, j = 0;
 
    // Looping for each element of the matrix
    for (int row = 0; row < n; row++) {
        for (int col = 0; col < n; col++) {
            // Copying into temporary matrix only those element which are not in given row and column
            if (row != p && col != q) {
                temp[i][j++] = mat[row][col];
 
                // Row is filled, so increase row index and reset col index
                if (j == n - 1) {
                    j = 0;
                    i++;
                }
            }
        }
    }
}
//------------------------------------------------------------------------------
// Recursive function for finding the determinant of matrix.
// n is current dimension of mat[][].
int determinantOfMatrix(int mat[N][N], int n)
{
    // Initialize result
    int D = 0; 
 
    // Base case : if matrix contains single element
    if (n == 1)
        return mat[0][0];
 
    // To store cofactors
    int temp[N][N]; 
 
    // To store sign multiplier
    int sign = 1; 
 
    // Iterate for each element of first row
    for (int f = 0; f < n; f++) {
        // Getting Cofactor of mat[0][f]
        getCofactor(mat, temp, 0, f, n);
        D += sign * mat[0][f] * determinantOfMatrix(temp, n - 1);
 
        // Terms are to be added with alternate sign
        sign = -sign;
    }
     return D;
}
//------------------------------------------------------------------------------ 
// Function for displaying the matrix 
void display(int mat[N][N], int row, int col)
{
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++)
            printf("  %d", mat[i][j]);
        printf("\n");
    }
}
//------------------------------------------------------------------------------
// Driver code
int main()
{
    int mat[N][N] = {{ 1, 0, 2, -1},
                     { 3, 0, 0,  5},
                     { 2, 1, 4, -3},
                     { 1, 0, 5,  0}};
     display(mat, N, N);
    // Function call
    printf("The determinant of the matrix is: %d",
            determinantOfMatrix(mat, N));
    return 0;
}

1 0 2 -1
3 0 0 5
2 1 4 -3
1 0 5 0
The determinant of the matrix is: 30

The inverse of a square matrix A, is called an invertible matrix. We write A^-1 instead of \({1 \over A}\) because we do not divide by a matrix! 

The inverse of a square matrix is another square matrix that produces the identity matrix when multiplied by the original matrix. The identity matrix is a square matrix with ones on the diagonal and zeros everywhere else.

You can obtain an inverse of a matrix using the following method:

1. Calculate determinant of matrix, \(det(A) = {\left| A \right|}\).
   If ( \( {\left| A \right|} \ne 0\) ), then we can say the matrix A has an inverse.
2. Calculate the adjoint of the given matrix, \(adj(A)\).
   Adjoint can be obtained by taking the transpose of the cofactor matrix of the given square matrix.
3. Finally, the inverse of the matrix is given below: \({A^{ - 1}} = {{adj(A)} \over {\left| A \right|}}\)

Matrix division is an undefined function. To divide one matrix by another, the closed equivalent is multiplying by the inverse of the divisor matrix.

\[A/B = A \times {B^{ - 1}}\]

#include <stdio.h>
#define SIZE 5
int     front = 0;
int     rear = 0;
int     buf[SIZE];

void enqueue(int item) {
    if ((rear + 1) % SIZE == front) {
        printf("Buffer is full\n");
        return;
    }
    buf[rear] = item;
    rear = (rear + 1) % SIZE;
}
//------------------------------------------------------------------------------
int dequeue() {
    if (front == rear) {
        printf("Buffer is empty\n");
        return -1;
    }
    int item = buf[front];
    front = (front + 1) % SIZE;
    return item;
}
//------------------------------------------------------------------------------
int main() {
    enqueue(10);
    enqueue(20);
    enqueue(30);

    printf("Dequeued element: %d\n", dequeue());
    printf("Dequeued element: %d\n", dequeue());

    return 0;
}

This code implements a FIFO buffer using a circular array. The enqueue function adds an item to the rear of the buffer, and the dequeue function removes an item from the front of the buffer. The front and rear pointers are used to track the buffer's beginning and end.

#include <stdio.h>
#define SIZE 5

int top = -1;
int buf[SIZE];

void push(int item) {
    if (top == SIZE - 1) {
        printf("Buffer is full\n");
        return;
    }
    buf[++top] = item;
}
//------------------------------------------------------------------------------
int pop() {
    if (top == -1) {
        printf("Buffer is empty\n");
        return -1;
    }

    int item = buf[top];
    top--;
    return item;
}
//------------------------------------------------------------------------------
int main() {
    push(10);
    push(20);
    push(30);

    printf("Popped element: %d\n", pop());
    printf("Popped element: %d\n", pop());
    return 0;
}

This code implements a FILO buffer using an array. The push function adds an item to the top of the buffer, and the pop function removes an item from the top of the buffer. The top pointer is used to keep track of the top of the buffer.

#include <iostream>
class FIFOBuffer {
private:
    int     *buffer; // Array to store the data
    int     capacity; // Maximum capacity of the buffer
    int     front; // Index of the front element
    int     rear; // Index of the rear element

public:
    FIFOBuffer(int capacity) {
        this->capacity = capacity;
        buffer = new int[capacity];
        front = 0;
        rear = 0;
    }

    ~FIFOBuffer() {
        delete[] buffer;
    }

    bool    isEmpty() {
        return front == rear;
    }

    bool    isFull() {
        return (rear + 1) % capacity == front;
    }

    void    enqueue(int item) {
        if (isFull()) {
            std::cout << "Buffer is full" << std::endl;
            return;
        }
        buffer[rear] = item;
 rear = (rear + 1) % capacity;
    }

    int     dequeue() {
        if (isEmpty()) {
            std::cout << "Buffer is empty" << std::endl;
            return -1;
        }
        int frontItem = buffer[front];
        front = (front + 1) % capacity;
        return frontItem;
    }
};
//------------------------------------------------------------------------------
int main() {
    FIFOBuffer buffer(5);  // Create a FIFO buffer with capacity 5
    buffer.enqueue(10);    // Enqueue element 10
    buffer.enqueue(20);    // Enqueue element 20
    buffer.enqueue(30);    // Enqueue element 30

    std::cout << "Dequeued element: " << buffer.dequeue() << std::endl; // Dequeue element (10)
    std::cout << "Dequeued element: " << buffer.dequeue() << std::endl; // Dequeue element (20)

    return 0;
}

In this example, the FIFOBuffer class manages the FIFO buffer operations. The enqueue function adds new elements to the rear of the buffer, and the dequeue function removes elements from the front.

#include <iostream>

class FILOBuffer {
private:
    int     *buffer;  // Array to store the data
    int     capacity; // Maximum capacity of the buffer
    int     top;      // Index of the top element

public:
    FILOBuffer(int capacity) {
        this->capacity = capacity;
        buffer = new int[capacity];
        top = -1;
    }

    ~FILOBuffer() {
        delete[] buffer;
    }

    bool isEmpty() {
        return top == -1;
    }

    bool isFull() {
        return top == capacity - 1;
    }

    void push(int item) {
        if (isFull()) {
            std::cout << "Buffer is full" << std::endl;
            return;
        }

        buffer[++top] = item;
    }

    int pop() {
        if (isEmpty()) {
            std::cout << "Buffer is empty" << std::endl;
            return -1;
        }

        int topItem = buffer[top];
        top--;
        return topItem;
    }
};
//------------------------------------------------------------------------------
int main() {
    FILOBuffer buffer(3); // Create a FILO buffer with capacity 3 buffer.

    buffer.push(10);     // Push element 10
    buffer.push(20);     // Push element 20
    buffer.push(30);     // Push element 30

    std::cout << "Popped element: " << buffer.pop() << std::endl; // Pop element (30)
    std::cout << "Popped element: " << buffer.pop() << std::endl; // Pop element (20)

return 0;
}

This code completes the FILO buffer implementation by adding elements to the stack (push) and removing elements from the stack (pop).

What is Bubble Sort?

Bubble sort is a simple sorting algorithm that repeatedly compares adjacent elements and swaps them if they are in the wrong order. This process continues until the array is sorted. The algorithm is named after the way bubbles rise to the surface of a liquid, as the largest element is "bubble" up to the end of the array.

How Does Bubble Sort Work?

Bubble sort works by repeatedly iterating through the array, comparing adjacent elements, and swapping them if they are in the wrong order. This process continues until no more swaps are required, indicating that the array is sorted. In each iteration, the largest element in the unsorted portion of the array will move to its correct position, effectively reducing the unsorted portion by one element.

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

Example of Bubble Sort Usage

Here's an example of how to use the bubbleSort function to sort an array:

int main() {
    int arr[] = {5, 2, 4, 1, 3};
    int size = sizeof(arr) / sizeof(arr[0]);

    bubbleSort(arr, size);

    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }

  return 0;
}

This code defines an array arr with unsorted elements and calls the bubbleSort function to sort the array. It then prints the sorted array.

Time Complexity of Bubble Sort

The average and worst-case time complexity of bubble sort is \(O({n^2})\), where n is the number of elements in the array. This means that the number of comparisons and swaps grows quadratically with the size of the array, making it less efficient for large datasets.

Advantages and Disadvantages of Bubble Sort

Advantages:

• Simple to understand and implement
• Efficient for small datasets
• In-place sorting algorithm

Disadvantages:

• Quadratic time complexity (\(O({n^2})\)) for average and worst cases
• Inefficient for large datasets
• More comparisons and swaps than other sorting algorithms

Bubble sort is a simple and intuitive sorting algorithm that is easy to understand and implement. However, its quadratic time complexity makes it less efficient for large datasets. Other sorting algorithms, such as merge sort and quick sort, offer better time complexity and performance for larger datasets.

What is the Selection Sort?

Selection sort is a simple and efficient sorting algorithm that repeatedly finds the minimum element in an unsorted subarray and moves it to its correct position in the sorted portion of the array. This process continues until the entire array is sorted.

How Does Selection Sort Work?

Selection sort works by maintaining two portions of the array: a sorted portion and an unsorted portion. Initially, the sorted portion is empty, and the unsorted portion is the entire array. In each iteration, the algorithm selects the minimum element from the unsorted portion and swaps it with the element at the current index of the sorted portion. This effectively moves the minimum element to its correct position in the sorted portion.

void selectionSort(int arr[], int size)
{
    int minIndex;
    for (int i = 0; i < size - 1; i++) {
        minIndex = i;
        for (int j = i + 1; j < size; j++) {
        if (arr[j] < arr[minIndex]) {
            minIndex = j;
        }
    }
    if (minIndex != i) {
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
  }
}

Example of Selection Sort Usage

The provided code demonstrates how to use the selectionSort function to sort an array:

int main() {
    int arr[] = {5, 2, 4, 1, 3};
    int size = sizeof(arr) / sizeof(arr[0]);

    selectionSort(arr, size);
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

This code defines an array arr with unsorted elements and calls the selectionSort function to sort the array. It then prints the sorted array.

Time Complexity of Selection Sort

The selection sort's average and worst-case time complexity is \(O({n^2})\), where n is the number of elements in the array. This means that the number of comparisons and swaps grows quadratically with the size of the array, making it less efficient for large datasets.

Advantages and Disadvantages of Selection Sort

Advantages:

• Simple to understand and implement
• In-place sorting algorithm
• Stable sorting algorithm (preserves the original order of equal elements)

Disadvantages:

• Quadratic time complexity (\(O({n^2})\)) for average and worst cases
• Inefficient for large datasets
• More comparisons than other sorting algorithms

Selection sort is a straightforward and efficient sorting algorithm that is easy to understand and implement. However, its quadratic time complexity makes it less suitable for large datasets. Other sorting algorithms, such as merge sort and quick sort, offer better time complexity and performance for larger datasets.

What is Insertion Sort?

Insertion sort is a simple and efficient sorting algorithm that resembles the way we sort playing cards in our hands. It works by building a sorted subarray one element at a time. Initially, the sorted subarray consists of the first element, and each subsequent element is inserted into its correct position within the sorted subarray.

How Does Insertion Sort Work?

Insertion sort iterates through the array, maintaining a sorted subarray at the beginning of the array. For each unsorted element, it compares it with the elements in the sorted subarray and inserts it into its correct position. This process continues until all elements are sorted.

void insertionSort(int arr[], int size) {
    for (int i = 1; i < size; i++) {
        int currentElement = arr[i];
        int j;
        for (j = i - 1; j >= 0 && currentElement < arr[j]; j--) {
            arr[j + 1] = arr[j];
        }
        arr[j + 1] = currentElement;
    }
}

Example of Insertion Sort Usage

Here's an example of how to use the insertionSort function to sort an array:

int main() {
    int arr[] = {5, 2, 4, 1, 3};
    int size = sizeof(arr) / sizeof(arr[0]);

    insertionSort(arr, size);
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

This code defines an array arr with unsorted elements and calls the insertionSort function to sort the array. It then prints the sorted array.

Time Complexity of Insertion Sort

The average and best-case time complexity of insertion sort is \(O({n^2})\), where n is the number of elements in the array. The worst-case time complexity occurs when the array is already sorted in reverse order, in which case the inner loop performs n comparisons for each iteration.

Advantages and Disadvantages of Insertion Sort

Advantages:

• Simple to understand and implement
• In-place sorting algorithm
• Stable sorting algorithm (preserves the original order of equal elements)
• Efficient for small to medium-sized datasets

Disadvantages:

• Quadratic time complexity (\(O({n^2})\)) for average and worst cases
• Inefficient for large datasets
• More comparisons than other sorting algorithms, especially for large datasets

Insertion sort is a versatile and straightforward sorting algorithm that is easy to understand and implement. While its quadratic time complexity makes it less efficient for large datasets, it performs well for smaller datasets and is often used in practice due to its simplicity and stability.

What is Merge Sort?

Merge sort is a divide-and-conquer sorting algorithm that repeatedly divides an unsorted array into smaller subarrays, sorts them recursively, and merges them back together in sorted order. It is one of the most efficient sorting algorithms with an average and worst-case time complexity of \(O(n\log n)\), where n is the number of elements in the array.

How Does Merge Sort Work?

Merge sort works by recursively dividing the unsorted array into halves until each subarray contains a single element. These single-element subarrays are naturally sorted. Then, the algorithm merges the sorted subarrays pairwise, combining them into larger sorted subarrays.

void merge(int arr[], int left, int mid, int right)
{
    int temp[right - left + 1];
    int i, j, k;

    i = left;
    j = mid + 1;
    k = 0;

    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k] = arr[i];
            i++;
        } else {
            temp[k] = arr[j];
            j++;
        }
        k++;
    }

    while (i <= mid) {
        temp[k] = arr[i];
        i++;
        k++;
    }

    while (j <= right) {
        temp[k] = arr[j];
        j++;
        k++;
    }

    // Copy the merged array back to the original array
    for (i = left; i <= right; i++) {
        arr[i] = temp[i - left];
    }
}
//------------------------------------------------------------------------------
void mergeSort(int arr[], int left, int right)
{
    if (left < right) {
        int mid = (left + right) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

Example of Merge Sort Usage

Here's an example of how to use the mergeSort function to sort an array:

int main()
{
    int arr[] = {5, 2, 4, 1, 3};
    int size = sizeof(arr) / sizeof(arr[0]);

    mergeSort(arr, 0, size - 1);

    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }

    return 0;
}

This code defines an array arr with unsorted elements and calls the mergeSort function to sort the array. It then prints the sorted array.

Time Complexity of Merge Sort

The average and worst-case time complexity of merge sort is \(O(n\log n)\), where n is the number of elements in the array. This makes merge sort one of the most efficient sorting algorithms for large datasets.

Advantages and Disadvantages of Merge Sort

Advantages:

• Efficient time complexity (\(O(n\log n)\)) for average and worst cases
• Stable sorting algorithm (preserves the original order of equal elements)
• Suitable for large datasets

Disadvantages:

• Recursion can cause overhead for small datasets
• Requires additional memory for temporary arrays
• More complex implementation compared to simpler algorithms

Merge sort is a powerful and efficient sorting algorithm that is well-suited for large datasets. Its divide-and-conquer approach and logarithmic time complexity make it popular for various applications.

What is Quick Sort?

Quicksort is a divide-and-conquer sorting algorithm that recursively partitions an unsorted array around a pivot element, effectively dividing the problem into smaller subproblems. It is one of the most efficient sorting algorithms with an average time complexity of \(O(n\log n)\), where n is the number of elements in the array.

How Does Quick Sort Work?

Quicksort works by selecting a pivot element from the array. The pivot element is then placed in its correct position in the sorted array, and the remaining elements are partitioned around it. The algorithm then recursively applies the same process to the smaller subarrays until all elements are sorted.

void swap(int *a, int *b)
{
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}
//------------------------------------------------------------------------------
int partition(int arr[], int low, int high)
{
    int pivot = arr[high];
    int i = (low - 1);

    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}
//------------------------------------------------------------------------------
void quickSort(int arr[], int low, int high)
{
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

Example of Quick Sort Usage

Here's an example of how to use the quickSort function to sort an array:

int main()
{
    int arr[] = {5, 2, 4, 1, 3};
    int size = sizeof(arr) / sizeof(arr[0]);

    quickSort(arr, 0, size - 1);

    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }

    return 0;
}

This code defines an array arr with unsorted elements and calls the quickSort function to sort the array. It then prints the sorted array.

Time Complexity of Quick Sort

The average time complexity of quicksort is \(O(n\log n)\), where n is the number of elements in the array. However, the worst-case time complexity is \(O({n^2})\), which occurs when the pivot element is always the smallest or largest element in the array.

Advantages and Disadvantages of Quick Sort

Advantages:

• Efficient average time complexity (\(O(n\log n)\))
• Suitable for large datasets
• In-place sorting algorithm

Disadvantages:

• The worst-case time complexity of \(O({n^2})\)
• Performance depends on the choice of pivot element
• More complex implementation compared to simpler algorithms

Quicksort is a powerful and efficient sorting algorithm that is well-suited for large datasets. Its average time complexity of \(O(n\log n)\) makes it a popular choice for various applications. However, it is important to note that its performance can be affected by the choice of pivot element. If carefully chosen, the pivot element can significantly improve the performance of quicksort. However, if consistently chosen poorly, the algorithm can degrade to \(O({n^2})\) time complexity, which is less efficient than other sorting algorithms like merge sort.

Quicksort is a versatile and efficient sorting algorithm that balances speed and simplicity. It is a valuable tool for data scientists and programmers who need to sort large datasets.