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:

1int myArray[5];
2
3myArray[0] = 10;
4myArray[1] = 20;
5myArray[2] = 30;
6myArray[3] = 40;
7myArray[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:

1Element at index 3: 40

xxxxxxxxxx

#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;

}

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:

1int myArray[5];

xxxxxxxxxx

#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 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++:

1#include <iostream>
2using namespace std;
3
4int main() {
5  int arr[] = {2, 4, 6, 8, 10};
6  int target = 6;
7  int n = sizeof(arr) / sizeof(arr[0]);
8
9  for (int i = 0; i < n; i++) {
10    if (arr[i] == target) {
11      cout << "Element found at index " << i << endl;
12      break;
13    }
14  }
15
16  return 0;
17}

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.

xxxxxxxxxx

#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;

}

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++:

1#include <iostream>
2#include <algorithm>
3using namespace std;
4
5void printArray(int arr[], int size) {
6  for (int i = 0; i < size; i++) {
7    cout << arr[i] << " ";
8  }
9  cout << endl;
10}
11
12void bubbleSort(int arr[], int size) {
13  for (int i = 0; i < size - 1; i++) {
14    for (int j = 0; j < size - i - 1; j++) {
15      if (arr[j] > arr[j + 1]) {
16        swap(arr[j], arr[j + 1]);
17      }
18    }
19  }
20}
21
22int main() {
23  int arr[] = {5, 2, 8, 12, 1};
24  int size = sizeof(arr) / sizeof(arr[0]);
25
26  cout << "Original array: " << endl;
27  printArray(arr, size);
28
29  bubbleSort(arr, size);
30
31  cout << "Sorted array: " << endl;
32  printArray(arr, size);
33
34  return 0;
35}

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.

xxxxxxxxxx

}

#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);

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++:

1#include <iostream>
2#include <algorithm>
3using namespace std;
4
5void printArray(int arr[], int size) {
6  for (int i = 0; i < size; i++) {
7    cout << arr[i] << " ";
8  }
9  cout << endl;
10}
11
12void mergeArrays(int arr1[], int size1, int arr2[], int size2, int result[]) {
13  // Merge logic
14}
15
16int main() {
17  int arr1[] = {1, 3, 7, 9};
18  int size1 = sizeof(arr1) / sizeof(arr1[0]);
19
20  int arr2[] = {2, 4, 6, 8};
21  int size2 = sizeof(arr2) / sizeof(arr2[0]);
22
23  int result[size1 + size2];
24
25  cout << "Array 1: ";
26  printArray(arr1, size1);
27
28  cout << "Array 2: ";
29  printArray(arr2, size2);
30
31  mergeArrays(arr1, size1, arr2, size2, result);
32
33  cout << "Merged Array: ";
34  printArray(result, size1 + size2);
35
36  return 0;
37}

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.

xxxxxxxxxx

}

#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++];

  }