Arrays

Introduction to Arrays

Arrays are one of the fundamental data structures in C++. They allow us to store multiple elements of the same type in a contiguous block of memory. Arrays are often used to represent collections of similar objects.

Arrays can be declared and initialized as follows:

int myArray[5];

myArray[0] = 10;
myArray[1] = 20;
myArray[2] = 30;
myArray[3] = 40;
myArray[4] = 50;

In the above code snippet, we declare an integer array myArray of size 5. We then assign values to each element of the array using the subscript operator [].

To access an element of an array, we can use the subscript operator [] followed by the index of the element. For example, to access the element at index 3, we would use myArray[3]. The output of the above code would be:

Element at index 3: 40

```cpp
#include <iostream>
using namespace std;

int main() {
  // Array declaration
  int myArray[5];

  // Array initialization
  myArray[0] = 10;
  myArray[1] = 20;
  myArray[2] = 30;
  myArray[3] = 40;
  myArray[4] = 50;

  // Array access
  cout << "Element at index 3: " << myArray[3] << endl;

  return 0;
}
```

Arrays are dynamic data structures in C++ that allow us to store multiple elements of different types.

Array Manipulation

In the previous screen, we learned the basics of arrays. Now, let's dive into array manipulation, which involves performing operations such as creating, accessing, and modifying elements in an array.

Creating an Array

To create an array in C++, you define the type of the elements followed by the name of the array and the size of the array in square brackets. For example:

int myArray[5];

```c++
#include <iostream>
using namespace std;

int main() {
  // Create an array
  int myArray[5];

  // Assign values to the array
  for (int i = 0; i < 5; i++) {
    myArray[i] = i + 1;
  }

  // Accessing elements of the array
  cout << "Element at index 2: " << myArray[2] << endl;

  // Modifying elements of the array
  myArray[3] = 10;

  // Displaying the modified array
  for (int i = 0; i < 5; i++) {
    cout << myArray[i] << " ";
  }
  cout << endl;

  return 0;
}
```

Array elements can be accessed and modified by their _______________.

Array Searching

In the previous screen, we learned about arrays and how to manipulate them. Now, let's explore the topic of array searching.

Array searching involves finding the position or index of a specific element in an array. This operation can be useful in various scenarios, such as locating a value, checking for the presence of an element, or performing further operations on the found element.

One common technique for array searching is linear search.

Linear Search

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

Here's an example of implementing linear search in C++:

#include <iostream>
using namespace std;

int main() {
  int arr[] = {2, 4, 6, 8, 10};
  int target = 6;
  int n = sizeof(arr) / sizeof(arr[0]);

  for (int i = 0; i < n; i++) {
    if (arr[i] == target) {
      cout << "Element found at index " << i << endl;
      break;
    }
  }

  return 0;
}

In the code snippet above, we have an array arr containing numbers and a target value target that we want to search for. We iterate through each element of the array and check if it matches the target value. If a match is found, we print the index at which the element is found.

Linear search has a time complexity of O(n), where n is the number of elements in the array. This means that in the worst-case scenario, it may need to iterate through all elements in the array.

While linear search is a simple and straightforward technique, it may not be efficient for large arrays. In upcoming screens, we will explore more advanced array searching algorithms that offer better performance for different scenarios.

```c++
#include <iostream>
using namespace std;

int main() {
  // Linear Search
  int arr[] = {2, 4, 6, 8, 10};
  int target = 6;
  int n = sizeof(arr) / sizeof(arr[0]);

  for (int i = 0; i < n; i++) {
    if (arr[i] == target) {
      cout << "Element found at index " << i << endl;
      break;
    }
  }

  return 0;
}
```

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

Bubble Sort

One of the simplest sorting algorithms is the Bubble Sort. It works by repeatedly swapping adjacent elements if they are in the wrong order. The algorithm continues to iterate through the array until no more swaps are needed, indicating that the array is sorted.

Here's an example of implementing Bubble Sort in C++:

#include <iostream>
#include <algorithm>
using namespace std;

void printArray(int arr[], int size) {
  for (int i = 0; i < size; i++) {
    cout << arr[i] << " ";
  }
  cout << endl;
}

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

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

  cout << "Original array: " << endl;
  printArray(arr, size);

  bubbleSort(arr, size);

  cout << "Sorted array: " << endl;
  printArray(arr, size);

  return 0;
}

In the code snippet above, we have an array arr filled with integer values. We then define a function printArray to print the elements of an array, and another function bubbleSort to implement Bubble Sort.

The bubbleSort function consists of two nested loops that iterate through the array. On each iteration, adjacent elements are compared, and if they are in the wrong order, they are swapped. This process continues until the entire array is sorted.

Let's take a closer look at the steps the Bubble Sort algorithm takes to sort the array {5, 2, 8, 12, 1}:

• Step 1: Compare 5 and 2. Since 5 is greater than 2, swap the two elements: {2, 5, 8, 12, 1}.
• Step 2: Compare 5 and 8. Since 5 is not greater than 8, no swap is needed.
• Step 3: Compare 8 and 12. Since 8 is not greater than 12, no swap is needed.
• Step 4: Compare 12 and 1. Since 12 is greater than 1, swap the two elements: {2, 5, 8, 1, 12}.

After the first iteration, the largest element 12 is in its correct position at the end of the array. The process then repeats for the remaining elements until the entire array is sorted.

Bubble Sort has a worst-case and average time complexity of O(n^2), where n is the number of elements in the array. Although simple to implement, Bubble Sort is not suitable for large arrays or performance-critical applications as its time complexity makes it inefficient.

There are more efficient sorting algorithms available, such as Quick Sort, Merge Sort, and Heap Sort, which we will explore in upcoming screens.

```c++
#include <iostream>
#include <algorithm>
using namespace std;

void printArray(int arr[], int size) {
  for (int i = 0; i < size; i++) {
    cout << arr[i] << " ";
  }
  cout << endl;
}

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

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

  cout << "Original array: " << endl;
  printArray(arr, size);

  bubbleSort(arr, size);

  cout << "Sorted array: " << endl;
  printArray(arr, size);

  return 0;
}

```

What is the time complexity of Bubble Sort?

Merging Arrays

Merging arrays involves combining two or more arrays into a single array. This operation is useful when you need to combine related data or manipulate arrays in different ways. In C++, you can merge arrays using the mergeArrays function.

Here's an example of merging two sorted arrays in C++:

#include <iostream>
#include <algorithm>
using namespace std;

void printArray(int arr[], int size) {
  for (int i = 0; i < size; i++) {
    cout << arr[i] << " ";
  }
  cout << endl;
}

void mergeArrays(int arr1[], int size1, int arr2[], int size2, int result[]) {
  // Merge logic
}

int main() {
  int arr1[] = {1, 3, 7, 9};
  int size1 = sizeof(arr1) / sizeof(arr1[0]);

  int arr2[] = {2, 4, 6, 8};
  int size2 = sizeof(arr2) / sizeof(arr2[0]);

  int result[size1 + size2];

  cout << "Array 1: ";
  printArray(arr1, size1);

  cout << "Array 2: ";
  printArray(arr2, size2);

  mergeArrays(arr1, size1, arr2, size2, result);

  cout << "Merged Array: ";
  printArray(result, size1 + size2);

  return 0;
}

In the code snippet above, we have two sorted arrays: arr1 and arr2. We want to merge them into a single sorted array. We define the function mergeArrays, which takes the two arrays, their respective sizes, and an empty result array as parameters.

The mergeArrays function uses a two-pointer approach to merge the arrays. It compares elements from both arrays and adds the smaller element to the result array. The function continues until all elements from both arrays have been processed.

After merging, the resulting array contains all elements from arr1 and arr2 in sorted order. In the example, the output will be:

Array 1: 1 3 7 9 Array 2: 2 4 6 8 Merged Array: 1 2 3 4 6 7 8 9

Merging arrays is a common operation when working with data that is spread across multiple arrays and needs to be combined for further processing. It is especially useful when dealing with sorted arrays, as merging can be done efficiently without the need for additional sorting.

You can experiment further by merging arrays of different sizes or unsorted arrays. The mergeArrays function can be modified to accommodate various merge logics and requirements.

```c++
#include <iostream>
#include <algorithm>
using namespace std;

void printArray(int arr[], int size) {
  for (int i = 0; i < size; i++) {
    cout << arr[i] << " ";
  }
  cout << endl;
}

void mergeArrays(int arr1[], int size1, int arr2[], int size2, int result[]) {
  int i = 0, j = 0, k = 0;

  while (i < size1 && j < size2) {
    if (arr1[i] <= arr2[j]) {
      result[k++] = arr1[i++];
    } else {
      result[k++] = arr2[j++];
    }
  }

  while (i < size1) {
    result[k++] = arr1[i++];
  }

  while (j < size2) {
    result[k++] = arr2[j++];
  }
}

int main() {
  int arr1[] = {1, 3, 7, 9};
  int size1 = sizeof(arr1) / sizeof(arr1[0]);

  int arr2[] = {2, 4, 6, 8};
  int size2 = sizeof(arr2) / sizeof(arr2[0]);

  int result[size1 + size2];

  cout << "Array 1: ";
  printArray(arr1, size1);

  cout << "Array 2: ";
  printArray(arr2, size2);

  mergeArrays(arr1, size1, arr2, size2, result);

  cout << "Merged Array: ";
  printArray(result, size1 + size2);

  return 0;
}
```

Array operations allow us to perform various manipulations on arrays, such as ___________, reversing, and rotating. These operations can help us solve different programming problems efficiently.

For example, let's say we have an array of integers:

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

To reverse the array, we can use the std::reverse function from the <algorithm> library:

#include <iostream>
#include <algorithm>
using namespace std;

void printArray(int arr[], int size) {
  for (int i = 0; i < size; i++) {
    cout << arr[i] << " ";
  }
  cout << endl;
}

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

  cout << "Original Array: ";
  printArray(arr, size);

  cout << "Reversed Array: ";
  reverse(arr, arr + size);
  printArray(arr, size);

  return 0;
}

After reversing the array, the output will be:

Original Array: 1 2 3 4 5
Reversed Array: 5 4 3 2 1

In this example, we use the std::reverse function to reverse the elements in the arr array. The function takes two iterators as parameters, representing the beginning and end of the range to be reversed. After calling the function, the array is reversed in-place.

Array operations like reversing can be useful in scenarios such as reversing the order of elements in an array for processing or displaying purposes. Other array operations, such as merging and rotating, also provide valuable functionality when working with arrays.

Generating complete for this lesson!