---
# System prepended metadata

title: Week 4

---

# Week 4

Main Lecturer: Caroline Xu

## Arrays

An array is a data structure that stores multiple pieces of data/objects of the same data type.

This is really handy when we need to store lots of data of the same type; for example, what if we had to store all of a student's test scores? It would be inefficient to create a separate variable for each score. For that, we can use an array.

To declare, initialize, and instantiate an array, use:

```java
dataType[] myArr = new dataType[int size];
```

For example:
```java
double[] array = new double[5];
```

If an array is small and you know the values, use:

```java   
int[] intArray = {1, 2, 3, 4, 5};
```

To access each individual piece of data in an array, we can **index** the array with **bracket notation**.

```java
intArray[4] = 3;
System.out.println(intArray[2]); // prints out "3"
```

That's strange! Printing out the value at index 2 of the arraay prints out `3`. This is because, lots of times in computer science, zeros are a lot nicer to work with than ones. Therefore, Java **zero-indexes** arrays. This means that indices start at `0` and end at `array.length - 1`. Whenever we print out the value at the 2nd index, we're actually printing out the 3rd value in the array.

Populating an empty array:

```java 
for(int i = 0; i < array.length; i++) 
    array[i] = (Math.random() * 100) + 1;
```

Notice how we started our for loop at `0`. This makes it a lot easier to zero-index.

This looks like:

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

### 2D Arrays

The previous array had one row and five columns. What about data that comes in a spreadsheet/table?

For this, we can use a 2D array. Think of it like an **array of arrays**.

To declare, initialize, and instantiate a 2D array, it is almost the same:

```java
dataType[][] myArr = new dataType[int rows][int cols];
```

For example:

```java
double[][] array = new double[3][5];
```

Populating an array requires another loop:

```java 
for(int i = 0; i < array.length; i++) 
    for(int j = 0; j < array[0].length; j++)
        array[i][j] = (Math.random() * 100) + 1;
```

This looks like:

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

Notice how, generally, we store rows and *then* columns. This is because going through rows and then columns is more natural than going through x and y. For example, say we have `int[][] myValues`.

```java
int[][] myValues = {
    { 0, 1, 2, 3, 4 },
    { 5, 6, 7, 8, 9 }
};
```

As you can see, our array is grouped together by row, not by column. Say we wanted to index the value with containing the `2`; in this case, we would say:

```java
System.out.println(myValues[0][2]); // Prints 2
```

If we are used to `(x, y)` pairs, we would be inclined to think that `myValues[2][0]` would be correct. However, in this case, `myValues[2][0]` does not exist. Because of that, it is better to think of it as `(row, col)` pairs.


## Sorts
Say you have lots of data, but you need it ordered. This is where sorts come in. 

### Bubble Sort
* Looks at first two values and swaps them if they are in the wrong order
* Repeats through the rest of the array
* Once a value is in its correct position, the array is traversed again, but does not look at the correct indexes

![](https://i.imgur.com/SFbXb0K.png)
Resources: 
* https://www.geeksforgeeks.org/bubble-sort/?ref=lbp
* https://www.hackerearth.com/practice/algorithms/sorting/bubble-sort/visualize/

### Selection Sort
* Two subarrays (unsorted and sorted)
* Traverse unsorted array to find minimum value and swap with first index
    * At this point, the sorted array consists of just the first index and the unsorted should consist of everything else
* This process repeats using only the first index of the unsorted array

![](https://i.imgur.com/UzqWHUQ.png)
Resources: 
* https://www.geeksforgeeks.org/selection-sort/
* https://www.hackerearth.com/practice/algorithms/sorting/selection-sort/visualize/



---

## Week 4 Assignment 
Create a program that populates an array with a random number (from 1 to 100) of random numbers (from 1 to 200). 

Extra challenges:
* Populate a 2D array with a random number of rows and columns (other guidelines stay the same)
* Implement a bubble sort or a selection sort to sort the array (if 2D, sort by row)



