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

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

For example:

double[] array = new double[5];

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

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**.

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:

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:


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

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

For example:

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

Populating an array requires another loop:

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:


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`.

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:

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

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

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)