6. DSA with C++ - Arrays Implementation and Its Various Operations

Arrays Implementation and Its Various Operations

Declaration and Initialization: To declare an array in C++, you specify the data type of its elements, followed by the array name and the size of the array enclosed in square brackets [].

dataType arrayName[SIZE];
    

For example:

int numbers[5]; // Declaration of an integer array of size 5
    

You can also initialize the array at the time of declaration by providing a comma-separated list of values enclosed in curly braces {}.

dataType arrayName[SIZE] = {val1, val2, ..., valN};
    

For example:

int numbers[5] = {1, 2, 3, 4, 5}; // Declaration and initialization of an integer array
    

Accessing Array Elements: Array elements can be accessed using their index, which starts at 0 for the first element. The index is enclosed in square brackets after the array name.

dataType element = arrayName[index];
    

For example:

int x = numbers[2]; // Accessing the third element of the array
    

Modifying Array Elements: Array elements can be modified by assigning a new value to the desired index.

arrayName[index] = newValue;
    

For example:

numbers[2] = 10; // Modifying the value of the third element to 10
    

Array Size: The size of an array is fixed and determined at compile time. To determine the size of an array in C++, you can use the `sizeof()` operator, which returns the size in bytes.

int size = sizeof(arrayName) / sizeof(arrayName[0]);
    

Iterating over Array Elements: You can use loops, such as the `for` loop, to iterate over the elements of an array.

for (int i = 0; i < size; i++) {
    // Access and manipulate array elements using arrayName[i]
}
    

For example:

for (int i = 0; i < size; i++) {
    cout << numbers[i] << " "; // Printing each element of the array
}
    

Arrays and Pointers: In C++, the name of the array acts as a pointer to its first element. You can use pointer arithmetic to access array elements.

dataType* ptr = arrayName;
    

For example:

int* ptr = numbers; // Assigning the pointer to the array
int x = *(ptr + 2); // Accessing the third element of the array using pointer arithmetic
    

Common Array Operations:

1. Finding the Maximum or Minimum Element:

To find the maximum or minimum element in an array, you can iterate over the array elements and keep track of the maximum or minimum value encountered.

dataType maxElement = arrayName[0];
for (int i = 1; i < size; i++) {
    if (arrayName[i] > maxElement) {
        maxElement = arrayName[i];
    }
}

    

2. Array Reversal:

You can reverse the order of elements in an array by swapping elements from the outermost posions towards the middle.

int start = 0;
int end = size - 1;
while (start < end) {
    // Swap arrayName[start] and arrayName[end]
    dataType temp = arrayName[start];
    arrayName[start] = arrayName[end];
    arrayName[end] = temp;
    start++;
    end--;
}
    

3. Array Concatenation

To concatenate two arrays, you can create a new array with a size equal to the sum of the sizes of both arrays and then copy the elements from each array into the new array.

dataType newArray[SIZE1 + SIZE2];
for (int i = 0; i < SIZE1; i++) {
    newArray[i] = arrayName1[i];
}
for (int i = 0; i < SIZE2; i++) {
    newArray[SIZE1 + i] = arrayName2[i];
}

    

4. Checking for Equality

To check if two arrays are equal, you can iterate over the corresponding elements of both arrays and compare them.

bool isEqual = true;
for (int i = 0; i < size; i++) {
    if (arrayName1[i] != arrayName2[i]) {
        isEqual = false;
        break;
    }
}

        

5. Array Traversal in Reverse Order

To traverse an array in reverse order, you can start the loop from the last index and decrement the loop counter until it reaches 0.

for (int i = size - 1; i >= 0; i--) {
    // Access array elements in reverse order using arrayName[i]
}

        

6. Linear Search

Linear search is a simple search algorithm that checks each element in the array sequentially until the target value is found or the end of the array is reached.

 int linearSearch(dataType arrayName[], int size, dataType target) {
    for (int i = 0; i < size; i++) {
        if (arrayName[i] == target) {
            return i; // Return the index if the target is found
        }
    }
    return -1; // Return -1 if the target is not found
}

            

7. Binary Search

Binary search is a more efficient search algorithm that requires the array to be sorted. It repeatedly divides the search interval in half until the target value is found or determined to be absent.

int binarySearch(dataType arrayName[], int size, dataType target) {
    int left = 0;
    int right = size - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arrayName[mid] == target) {
            return mid; // Return the index if the target is found
        }
        else if (arrayName[mid] < target) {
            left = mid + 1;
        }
        else {
            right = mid - 1;
        }
    }
    return -1; // Return -1 if the target is not found
}

            

8. Array Sorting

Sorting algorithms are used to arrange the elements of an array in a specific order. Some commonly used sorting algorithms include Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, Quick Sort, and Heap Sort.

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

9. Array Copy

To create a copy of an array, you can iterate over the elements of the source array and assign each element to the corresponding index in the destination array.

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

10. Array Comparison

To compare two arrays, you can iterate over the corresponding elements of both arrays and compare them. The comparison can be done element by element or by using the `std::equal()` function from the `` library.

bool isArrayEqual(dataType array1[], dataType array2[], int size) {
    for (int i = 0; i < size; i++) {
        if (array1[i] != array2[i]) {
            return false;
        }
    }
    return true;
}