Engineering Computation Workshop 6 === ###### tags: `comp20005` `workshop` `c` --- ### Arrays, Sorting & Strings --- ### Arrays Linear data structures that are the most primitive building block.  --- ### Array Declaration ```cpp type array_name [ array_size ]; int nums[5]; //an array of size 5 ``` How would we define an array of 100 doubles? --- ### Array Declaration ```cpp double nums[500]; ``` --- ### Array Declaration How do we assign values to the array's element at creation? ```cpp int nums[10] = {1,2,3,4,5,6,7,8,10}; // both work int nums[] = {1,2,3,4,5,6,7,8,10}; // both work ``` --- ### Array Access How do we access the elements stored within the array? With something called indexing! ```cpp int nums[] = {1,2,3,4,5,6,7,8,10}; int a = nums[3]; printf("%d", a); ``` What would the value of a be? --- ### Array Access The value would be: 4 Note that the indexing for arrays starts at 0 e.g. Why is that? --- ### Array Indexing Well as it turns out, arrays as you declare them are really just a special type of pointer  --- ### Array Indexing - Arrays as Pointers ```cpp int check(int* A, int n, int check) { int index = -1; for (int i=0;i<n;++i) index = A[i] == check ? i : index; return index; } ``` Is identical to: ```cpp int check(int A[], int n, int check) { int index = -1; for (int i=0;i<n;++i) index = A[i] == check ? i : index; return index; } ``` --- ### Array Indexing - Arrays as pointers Well if the variable of type `int A[]` is really just `int *A`, which really just points to the element at `&A[0]` then shouldn't we be able to index into them with an offset? Well yes - but it can be a little confusing ... but here is how --- ### Array Indexing - Arrays as pointers ```cpp int nums[] = {1,2,3,4,5,6,7,8,10}; // normal way of indexing and accessing index 3 int index_3 = nums[3]; ``` ```cpp int nums[] = {1,2,3,4,5,6,7,8,10}; // not normal way of indexing and accessing index 3 int index_3 = *(nums + 3); ``` --- ### Array Indexing Summary 1. Arrays are essentially just a bunch of pointers to the same type 2. The array A[index] notation is just syntatic sugar for *(A + index) 3. Arrays START AT 0 (you will get used to this pretty quickly) --- ### n-dimensional Arrays What if we want to represent a matrix? or an array of matrices (cube) or a matrix of matrices (4 dimensions)? Well its made pretty easy actually ```cpp int A[5][5]; // declares a 5x5 matrix ``` ```cpp int A[][] = {{1,2}, {3,4}, {5,6}, {7,8} } ``` --- ### Iteration over Arrays Just as you would expect, you need to know the size of the array before you start (for now). ```cpp int nums[] = {1,2,3,4,5,6,7,8,10}; int n = 10; for (int i=0;i<n;++i) printf("%d ", nums[i]); ``` --- ### Iteration over n-dimensional Arrays Well luckily you really will only be dealing with at most 3 dimensions (any more is just way too much space and the problem can usually be solved using smarter methods) ```cpp int A[][] = {{1,2}, {3,4}, {5,6}, {7,8} }; int n = 4; int m = 2; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { printf("%d ", A[i][j]) } } ``` --- ### Character Arrays - (strings?) An array of characters e.g. [h,e,l,l,o,\0] specify a string e.g. ```cpp char []str = "hello"; char [6]str = ['h','e','l','l','o','\0'] ``` Note that the use of `\0` is known as the null-byte character and is used to terminate (end) strings. --- ### Sorting There are lots of different sorting algorithms out there! The study of sorting algorithms is very comprehensive and the actual speed of algorithms vary greatly --- ### Sorting [6,1,9,3,4] -> [1,3,4,6,9] Ascending or Stricly Increasing Order $$A[i] \leq A[i+1]$$ [6,1,9,3,4] -> [9,6,4,3,1] Descending or Strictly Decreasing Order $$A[i] \geq A[i+1]$$ --- ### Sorting What is the simplest way to sort something? Well we want to get the smallest (or largest but for the rest this example we will say smallest) element and put it at the front. Then we get the next smallest element left ... and then the last element --- ### Sorting $[8,5,10,3,6,1,5]$ Start $[1,8,5,10,3,6,5]$ Find 1 and put it at index 0 sorted up to $[1]$ $[1,3,8,5,10,6,5]$ Find 3 and put it at index 1 sorted up to $[1,3]$ $[1,3,5,8,10,6,5]$ Find 5 and put it at index 2 sorted up to $[1,3,5]$ $[1,3,5,5,8,10,6]$ Find 5 and put it at index 3 sorted up to $[1,3,5,5]$ --- ### Sorting $[1,3,5,5,6,8,10]$ Find 6 and put it at index 4 sorted up to $[1,3,5,5,6]$ $[1,3,5,5,6,8,10]$ Find 8 and put it at index 5 sorted up to $[1,3,5,5,6,8]$ $[1,3,5,5,6,8,10]$ Find 10 and put it at index 6 sorted up to $[1,3,5,5,6,8,10]$ --- ### Sorting Well that wasn't too bad and it seem slike it might not be too tricky to implement either? That algorithm was called **selection sort**. Where we repeatedly find the smallest element, select it and move it to the sorted position within our array. --- ### Sorting **Insertion Sort**: What if instead of find the globally smallest element and moving each time, we just grew a partially sorted array from i=0,1...n? Steps: 1. Loop from i=1 to n-1 a. Pick element A[i] and insert it into sorted sequence A[0...i-1] Done ... well we need to figure out how we are going to insert our element into the sorted sequence such that it doesn't ruin our sorted order each time. --- ### Sorting ```cpp void insert_sort(int A[], int n) { int key, j; for (int i = 1; i < n; i++) { key = A[i] j = i-1; // Move elements that are greater than our key to the right one index while (j >= 0 && A[j] > key) { A[j+1] = A[j]; j -= 1; } A[j+1] = key; } } ``` --- ### Questions