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: 40xxxxxxxxxxusing 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;}Let's test your knowledge. Is this statement true or false?
Arrays are dynamic data structures in C++ that allow us to store multiple elements of different types.
Press true if you believe the statement is correct, or false otherwise.
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];xxxxxxxxxxusing 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;}Try this exercise. Fill in the missing part by typing it in.
Array elements can be accessed and modified by their ___.
Write the missing line below.
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.
xxxxxxxxxxusing 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;}Try this exercise. Fill in the missing part by typing it in.
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.
Write the missing line below.
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
5and2. Since5is greater than2, swap the two elements:{2, 5, 8, 12, 1}. - Step 2: Compare
5and8. Since5is not greater than8, no swap is needed. - Step 3: Compare
8and12. Since8is not greater than12, no swap is needed. - Step 4: Compare
12and1. Since12is greater than1, 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}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);Let's test your knowledge. Click the correct answer from the options.
What is the time complexity of Bubble Sort?
Click the option that best answers the question.
- O(n)
- O(n^2)
- O(log n)
- O(1)
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}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++]; }Try this exercise. Fill in the missing part by typing it in.
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:
1int arr[] = {1, 2, 3, 4, 5};To reverse the array, we can use the std::reverse function from the <algorithm> library:
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
12int main() {
13 int arr[] = {1, 2, 3, 4, 5};
14 int size = sizeof(arr) / sizeof(arr[0]);
15
16 cout << "Original Array: ";
17 printArray(arr, size);
18
19 cout << "Reversed Array: ";
20 reverse(arr, arr + size);
21 printArray(arr, size);
22
23 return 0;
24}After reversing the array, the output will be:
1Original Array: 1 2 3 4 5
2Reversed Array: 5 4 3 2 1In 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.
Write the missing line below.
Generating complete for this lesson!