---
# System prepended metadata

title: FOA Sem 2 Workshop 4

---

## Arrays

Stores a number of elements of the same type in a continuous block of memory.

```c
int arr[7] = {1, 5, 3, 2, 5, 6, 8};
```

---

How it looks in memory
```c
int arr[5] = {1, 2, 3, 4, 5};
```

![](https://i.imgur.com/bcg1IN5.png)

---

```c=
int arr[7] = {1, 5, 3, 2, 5, 6, 8};
int garbage[10]; // uninitialised, elements are garbage
int arr[200] = {1, 2}; // last 198 els are set to 0
// a character array (length can be inferred for any type)
char hello[] = {'h', 'e', 'l', 'l', 'o', '\0'};
// more concise initialisation of a character array (string)
char hello_again[] = "hello again";
```

---

## Things to keep in mind
- Arrays in C have no slicing. (no `A[1:3]`)
- You can't compare two arrays with `A == B`
- You can't copy two arrays with `A = B`
- There is no length operator for arrays.
- Arrays need to be defined with a static size (no variable length)
- Arrays have static length, once we define a size, we cannot change it.
- Arrays do not store the number of elements defined (length), you need to keep a variable for it for yourself!

---

### Arrays and functions
- passing an array to a function passes a pointer to the first element of the array
- changes to an array in a function are kept
- no way to return an array from a function
    - solutions
        - pass an output array as an argument
        - return a malloc'd array

---

```c=
#include <stdio.h>

void fillzeros(int[], int);

void fillzeros(int arr[], int n){
    for (int i = 0; i < n; i++){
        arr[i] = 0;
    } 
}

int main(int argc, char *argv[]) {
    int arr[5] = {1, 2, 3, 4, 5};
    fillzeros(arr, 5);
    for (int i = 0; i < 5; i++) {
        printf("%d ", arr[i]);
    }
}
```

```c
0 0 0 0 0 
```
<!-- .element: class="fragment" data-fragment-index="1" -->

---

```c=
void fillzeros(int arr[], int n){
    for (int i = 0; i < n; i++){
        arr[i] = 0;
    } 
}

int main() {
    int arr[5] = {1, 2, 3, 4, 5};
    fillzeros(arr + 2, 3);
    // print array as before
}
```

```c
1 2 0 0 0 
```
<!-- .element: class="fragment" data-fragment-index="1" -->

---

```c=
void fillzeros(int arr[], int n){
    for (int i = 0; i < n; i++){
        arr[i] = 0;
    } 
}

int main() {
    int arr[5] = {1, 2, 3, 4, 5};
    fillzeros(arr + 2, 5);
    // print array as before
}
```

```c
Seg Fault!!!!
```
<!-- .element: class="fragment" data-fragment-index="1" -->

---

# 2D Arrays 

2D arrays are exactly what they sound like... an array where each element is an array

```c 
int arr[3][3] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
```

Note: Technically the internal arrays do not have to all be the same length or same type, however it is rare to see this. As a general rule of thumb, use 2D arrays when they are the same length and type, otherwise use an array of structs (you will learn about this later)

---

There are two ways to visualise 2D arrays:

```c 
  0: 0  1   2  1: 0  1  2  2: 0  1  2
  {{11, 27, 3}, {62, 4, 18}, {0, 7, 200}}
```

```c 
     0  1   2
 0 {{11, 27, 3}, 
 1 {62, 4, 18}, 
 2 {0, 7, 200}}
```

---

### Accessing Values

```c 
int arr[3][3] = {{11, 27, 3}, {62, 4, 18}, {0, 7, 200}};
printf("%d\n", arr[0][2]);
```

```
3
```

```c 
printf("%d\n", arr[2][2]);
```

```
200
```

---

You can also index a 2D array as if it is a 1D one:

```c 
int mat[3][4] = {
    {1,  2,  3,  4},
    {5,  6,  7,  8},
    {9, 10, 11, 12}
};
int *p = mat[0];
printf("%d\n", p[6]);
```

```
7
```

---

Example: printing an $r \times c$ dimensional array.

```c!
for (int i = 0; i < r; i++) {
    for (int j = 0; j < c; j++) {
        printf("%d ", arr[i][j]);
    }
    printf("\n");
}
```

---

### Other ways of assigning 2D arrays
**Legal**: `int mat[][4] = {1, 2, 3, 4, 5, 6, 7, 8};`
=> can infer there are 2 int[4]s


Illegal: `int mat[][] = {1, 2, 3, 4, 5, 6, 7, 8};`
Where would mat[1][0] be?


Illegal: `int mat[4][] = {1, 2, 3, 4, 5, 6, 7, 8};`

**Rule of thumb**: we must give dimensions for all but the first dimension

---

### Passing 2D arrays to functions

```c
void print_int_arr0(int r, int c, int arr[r][c]){ 
    // r and c must be passed in first
}
```

```c
void print_int_arr1(int arr[1][3]){ 
}
```

```c
void print_int_arr2(int c, int arr[][c]){ 
    // r and c must be passed in first
    // only legal with C99 compiler
}
```

```c
void print_int_arr1(int *arr, int r, int c){ 
}
```

---

# Sorting

## Insertion sort
Build the sorted array one element at a time.

1. Pick the first unsorted element, $x$
2. Shift it towards the left, until it is "in place" (element left of it is $\leq x$)
3. Repeat until there are no more unsorted elements

---

```c
void insertion_sort(int A[], int n) {
  for (int i = 1; i < n; i++) {    // i : first 'not sorted' index
    for (int j = i; j > 0; j--) {  // j : element being sorted
      if (A[j - 1] >= A[j]) break; // A[j] in place?-> next element
      int_swap(A + j - 1, A + j);  // No? move A[j] one to the left
    }
  }
}
```

---

Personally I find sorting algorithms easiest to understand via animation.  There are these Romanian folk dancing videos online for each sorting algorithm...

Insertion sort here: https://www.youtube.com/watch?v=EdIKIf9mHk0

---
# Searching

## Linear Search
Idea: Iterate one-by-one through the search space, checking if the target matches.

![](https://media.geeksforgeeks.org/wp-content/cdn-uploads/Linear-Search.png)

---