Arrays

Definition: Arrays in C++ are containers that store multiple values of the same type in a contiguous block of memory.
- All stored values must be of the same type (homogeneous).
Memory Allocation:
- When an array is declared, a specific block of memory is reserved to hold multiple values.
- Arrays in C++ are static, meaning their size is fixed upon declaration.
Characteristics:
- Arrays are not objects and do not have built-in member data or member methods to track their size or current usage.
- Users are required to maintain their own constant variable to track the size of the array.
Addressing:
- The name of the array refers to the address of the first element stored, which is crucial when passing arrays to functions.
- When an array is passed to a function, the reference is passed rather than a copy, which allows for direct modification of the array within the function.
- To prevent modification, arrays can be declared as const when passed to functions.

Header and Source Files Setup:
- Array functions should be prototyped in a header file, implemented in a source file, and tested in a separate main source file.
- Include header guards to prevent multiple inclusions of the same header file.
Outputting Array Values:
- A function to output the values of an array should take two parameters: the array and its size.
- The parameter for the array should be declared as a constant to prevent modifications.
- Example function prototype:
```
void printArray(const int array[], const int size);
```
Implementation:
- Function implementation typically uses a for loop to iterate through indices of the array and display them via cout.
- Include #include <iostream> for input-output operations.
Populating Array with Random Values:
- A function to populate an array with random integers should not be constant since it modifies the contents of the array.
- Example:
```
void populate(int array[], int size);
```
- The population function could take additional parameters to specify a range for random values.
- Random Function: Use rand() from the C standard library to generate random integers.
- To ensure randomness upon multiple executions, srand(time(0)) should be called before generating any random numbers.

When declaring an array, its size must be explicit, and if initializing values, they must fit within the declared size. Any extra values will default to zero.
Example array declaration:

  const int SIZE = 10;
  int numbers[SIZE] = {1, 3, -6, 10, 130, 0, 0, 0, 0, 0};

Insertion Sort:
- Useful for sorting an array of integers in ascending order.
- Operational concept: build up larger and larger sorted lists by inserting elements in the correct position.
- Time complexity: Average case O(n²), Best case O(n) when the input is already sorted.
- The implementation would include a nested loop where the outer loop goes through each element and the inner loop positions the current element in its proper place among the previously sorted elements.
Efficiency and Timing:
- Use a clock function to measure how many machine cycles are used to perform sorting.
- Notable for the quadratic time complexity growth when input size doubles, i.e., if the size of the array is doubled, the time taken will roughly quadruple.
Binary Search:
- Requires a sorted array for efficient searching. It splits the search range in half repeatedly, effectively reducing the potential search space.
- Time complexity: O(log n).
- A function prototype for binary search:
  cpp int binarySearch(const int array[], int size, int target);

C++ allows for the creation of multidimensional arrays (e.g., 2D arrays) that are fixed in size upon declaration.
- Example declaration of a 2D array:
```
const int ROWS = 6;
const int COLS = 4;
int numbers[ROWS][COLS];
```
- Each dimension must have the same number of columns per row, and elements are stored in contiguous memory.
- Addressing: Use indices to access specific elements, and care must be taken to avoid accessing out-of-bounds elements.
- Passing rows of a multidimensional array to functions can be conducted as if they were one-dimensional arrays.
Creating and initializing a double subscripted array can be accomplished with nested loops to fill the elements.

Arrays in C++ are powerful structures that allow for efficient storage and manipulation of multiple values of the same type.
Understanding the nuances of arrays, function passing, memory management, and sorting/searching algorithms are crucial skills in C++ programming.