Arrays

1. Definition
2. Search algorithms for arrays
3. Sorting algorithms for arrays

• Data structures are concepts, they are not related to programming languages :
  • What programming languages do is using data structures for implementing the primitives they provide.
  • For instance, the Array class in javascript is not an array data structure per se.
• Array data structure properties :
  • Physically speaking, an array if a finite number of contiguous bytes in the computer's memory.
  • Logically speaking, an array is a finite number of elements of a given size that are stored in a "physical" array.
  • Once initialized, it can't be resized (it will always store the same number of elements).
  • As a result, both "inserting" an "deleting" an element effectively results in overwriting another element.

// this function (return x elements from the array beginning at index i) has a time complexity of O(1)
(x, i) => this.memory.subarray(this.ARRAY_START_OFFSET + i * this.BYTES_PER_ELEMENT, this.ARRAY_START_OFFSET + (i + x) * this.BYTES_PER_ELEMENT);

Note : Actual arrays do not even have the .length property available: it has to be specified at initialization depending on the space allocated and the element size in order to be available at a later stage.

• Search by iterating over all the elements of an array to find a search value.
• Time complexity: O(n).
• Use cases :
  1. Return whether the search value is present in an array.
  2. Return the first index in which the search value is found in an array.

• Only works on sorted arrays.
• Search by comparing search value x to the value y = array[Math.floor(array.length / 2)] :
  • If x === y : value is found.
  • If x < y : repeat the search on the first half of the array (excluding y).
  • If x > y : repeat the search on the second half of the array (excluding y).
• Repeat the search until the value is found or the array length becomes 0.
• Time complexity: O(log n) :
  • For instance, the compare / half operation will have to be successively performed 12 times for an array with 4096 elements Log2(4096) = 12.
• Use cases :
  1. Return whether the search value is present in the array.

• Only works on sorted arrays.
• Search by defining an increment of i = sqrt(array.length) :
  • Iterate over array elements at indexes separated by i until the search value is found at index j.
  • Then, perform a linear search from index j - i until the search value is found at index k with k > j - i && k <= j.
• Time complexity: O(sqrt(n)).
• Use cases :
  1. Return the first index where the search value is found (outperforms the linear search's O(n) complexity).

Notes :

• The point of using sqrt(array.length) instead of n-root(array.length) is because the increment decreases as the root factor increases.
• The above will eventually lead to increments of 1 (linear search).

Reminder : an array is sorted if each of its elements verifies a[x] <= a[x + 1].

• Sort by iterating over pairs of array elements and swapping the elements in a pair if the pair itself is not sorted:
  • if (a[x] > a[x + 1]) {y = a[x]; a[x] = a[x + 1]; a[x + 1] = y;}.
  • After a single iteration, the largest value will always be at the last index of the array.
  • As a result, only a.slice(0, a.length - 1) is unsorted at this stage.
  • Repeat successive iterations on the unsorted part of the array until the length of the unsorted part is 1.
• Time complexity: O(n²).
• Use cases :
  1. Sort an array.