Arrays 101

Arrays are usefule, we all know that, they enable us to organize multiple items in one structure. But there is more to them.

Efficient Memory

Storing data in a sequential manner in computer memory allows arrays to be fast and efficient. And of course, there is also more to this, so lets look at a few array types to understand this subject better.

Static Arrays

Since arrays are stored in memory as a single, uninterrupted block, we must know their size at compile time. Needing their size also means we need to know the type, since a 32bit integer needs more space then a boolean, for example. Thus, static arrays must store data of the same type only.

We can declare and initialize a static array like so:

1var array = new([4]int) // empty array
2var array2 = [..]{2, 4, 0, 3}

Now we have an array the size of 4 and of type int reserved in memory.

The downside of the static array is that everytime we want to allocate more then 4 values, we have to also create a new array (and copy the data from our old array over). Which can be slow, if done too often.

Sorted Arrays

Sometimes we need our array ordered in a specific way. If we use Go (and Go’s slices for that matter) its as simple as calling the sort.Slice function:

1a := []int{2, 4, 0, 3}
2
3sort.Slice(a, func(i, j int) bool {
4    return a[i] < a[j]
5})
6// will sort to: 0, 2, 3, 4

But what if we want to add the number 1 to our sorted array? We would need to either call sort.Slice again, or build our own little insertion sort algorithm (note that go sort.Slice does not use insertion algorithm but the pattern-defeating quicksort by Orson Peters).

1func insertionSort(arr []int) []int {
2    for i := 0, i < len(arr); i++ {
3        for j := i; j > 0 && arr[j-1] > arr[j]; j-- {
4            arr[j], arr[j-1] = arr[j-1], arr[j]
5        }
6    }
7return arr
8},

Here’s what is happening:

Worst case complexity of insertion sort is O(n^2). I have a post about Big-O Complexity if you want to look it up. Insertion sort is very easy to implement, but sadly not very useful as it is just too slow for general-purpose production use.

Dynamic Arrays

On my todo …