Search algorithms that are used to retrieve information from a data structure, in this post I'll describe 3 search algorithms to find an element in lists.

### Linear Search

Linear search is the most basic and easier to understand search algorithm, it simply starts from the first element in the list, and check each element to see if it is the element we are searching for, if the element is found returns its position in the list, else returns `-1`, `null` or `undefined`. Since it goes through the entire list, its time complexity is _O(n)_.

```typescript
function linearSearch(list:number[], n:number): number {
  for(let i=0; i< list.length; i++) {
    if(list[i] === n) return i
  }
}

const list = [2,6,4,8,9,0,1,5]
console.log(linearSearch(list, 1)) // 6
```

What if we are given a [sorted](/starting-with-sorting-algorithms) list? The next two algorithms work on sorted lists and are faster than the Linear Search algorithm.

### Jump Search

Instead of check element-by-element, This algorithm search block-by-block, so it checks fewer elements.

1. We start defining a block size
2. Starting from the beginning of the list, we check the last element of each block, if the element is smaller than the value we are looking for, we _jump_ to the next block.
3. But, if the last element of the current block is greater than the value we are looking for, we do a linear search in that block.

Jump Search time complexity in the average and worst cases is _O(√ n)_.

```typescript
function jumpSearch(list:number[], n:number): number {
  const blockSize = Math.floor(Math.sqrt(list.length))
  const start = 0
  
  while(list[start+blockSize-1] < n) {  	
    if(start + blockSize >= list.length) {
    	start += list.length - 1 - start
    }else {
    	start += blockSize
    }
  }
  
  for(let i=start; i < start+blockSize-1; i++) {
  	if(list[i] === n) return i
  }
}

const sortedList = [1,2,3,4,5,6,7,8,9,10]
console.log(jumpSearch(sortedList, 5)) // 4
```

### Binary Search

This algorithm is also meant for [sorted](/starting-with-sorting-algorithms) lists, it uses a divide-and-conquer technique, which means it divides the problem into smaller parts that are easier to solve.

1. Start by checking the element in the middle of the lists, if this element is the element we are searching for returns its position.
2. If that middle element is greater than the element we are searching for, repeat the first step for the right half.
3. But, if that middle element is smaller, repeat the first step for the left half.

Notice that this algorithm keeps dividing the sublists into even smaller ones checking only the element in the middle of each sublist, and it might, eventually, wind up with a sublist that contains a single element. Since this algorithm is halving the list at each iteration its time complexity is _O(log n)_.

Worth mentioning that this algorithm is also implemented for a [Binary Search Tree](/data-structures-in-typescript-binary-search-tree).

Here's an recursive implementation of Binary Search without any auxiliary data structures:

```typescript
function binarySearch(list:number[], n:number, low:number, high:number): number {
  // base case
  if(low > high) return
  
  let middle = Math.floor((low + high) / 2)
  
  if(list[middle] === n) return middle
  
  if(n < list[middle]) return binarySearch(list, n, low, middle-1)
  
  if(n > list[middle]) return binarySearch(list, n, middle+1, high)
}

const sortedList = [1,2,3,4,5,6,7,8,9,10]
console.log(binarySearch(sortedList, 3, 0, sortedList.length - 1))
```

Search algorithms that are used to retrieve information from a data structure, in this post I'll describe 3 search algorithms to find an element in lists

Starting with search algorithms

Quick Sort is an in-place [sorting algorithm](/tag/sorting) that uses a divide-and-conquer technique to sort a given list, which means it breaks down a problem into smaller parts in order to be simpler to solve and doesn't uses auxiliary data structures.

Quick Sort starts by selecting an element from the list to be the **pivot**, usually is the first or last element.

Next, rearrange the other elements, so all elements smaller than the pivot go to its left and all elements greater than the pivot goes to its right.

This process is repeated for the right and left sides of the pivot.

![quicksort](https://res.cloudinary.com/dje4crtui/image/upload/v1628888249/algorithms/sorting/quicksort_nag90i.gif)

## Implementation

Here is a recursive implementation of Quick Sort in [TypeScript](/tag/typescript)

```typescript
/**
 * swap function
 */
export function swap(arr: number[], i: number, j: number) {
  [arr[i], arr[j]] = [arr[j], arr[i]];
}

/**
 * recursive function
 */
function quickSort(arr: number[], start: number, end: number) {
  // base case
  if (start >= end) return;

  // rearrange the entire array based on a pivot
  // this pointer is the middle of the array, it will be explained in the next function
  const pointer = rearrange(arr, start, end);

  // rearrange the left and right side of the pivot
  quickSort(arr, start, pointer - 1);
  quickSort(arr, pointer + 1, end);
}

/**
 * function to rearrange the array based on a pivot
 */
function rearrange(arr: number[], start: number, end: number) {
  // choose last element to be the pivot
  const pivot = arr[end];

  // this pointer works like a placeholder for the pivot, at the end, it will be in the middle of the array, and will swap with the pivot that is in the end
  let pointer = start;

  for (let i = start; i < end; i++) {
    if (arr[i] < pivot) {
      swap(arr, pointer, i);

      // increment pointer, so it stays ahead of the elements that are smaller than the pivot
      pointer++;
    }
  }

  // put the pivot in the middle
  swap(arr, pointer, end);
  return pointer;
}

const arr = [3, 7, 2, 6, 5];
quickSort(arr, 0, arr.length - 1);
console.log(arr); // 2, 3, 5, 6, 7
```

The important part of Quick Sort is the choice of the **pivot**, since a bad choice leads to the worst-case time complexity, speaking of which, the average case time complexity of this algorithm is _O(n log n)_, while in the worst case is _O(n²)_, however, the worst-case can be avoided using a randomized version of this algorithm. Also, unlike [Merge Sort](/merge-sort), Quick Sort is an in-place algorithm, which gives it the advantage of having a constant space complexity _O(1)_.


Quick Sort is an in-place sorting algorithm that uses a divide-and-conquer technique to sort a given list

Quick Sort

Merge sort is a sorting algorithm that uses a divide-and-conquer technique to sort a given list, which means it breaks down a problem into smaller parts in order to be simpler to solve.

Merge Sort starts by splitting the list into halves, and continues to split those sublists until only sublists with a single element are left. Then merge those sublists into sorted sublists, and continue doing so until end up with a single sorted list.

```
                [4, 3, 2, 1];
                |           |
               |             |
Divide      [4,3]           [2,1]
            |   |           |   |
           |     |         |     |
         [4]     [2]     [2]     [1]
           |     |         |     |
            |   |           |   |
Conquer     [2,4]           [1,2]
                |           |
                 |         |
                 [1, 2, 3, 4]
```

## Implementation

This algorithm can be implemented with two functions, one to **divide** and another to **merge** :

```typescript
/**
 * Function to merge
 **/
function merge(left: number[], right: number[]): number[] {
  const sorted = [];

  // until one of the sublists has a element, insert them into the sorted list
  while (left.length && right.length) {
    if (left[0] < right[0]) {
      sorted.push(left.shift());
    } else {
      sorted.push(right.shift());
    }
  }

  // one of the sublists can still have leftover elements, so we need to merge them
  return [...sorted, ...left, ...right];
}

/**
 * Function to divide
 **/
function mergeSort(list: number[]): number[] {
  // base case
  if (list.length <= 1) return list;

  // split the list into two halves
  let left = list.slice(0, list.length / 2);
  let right = list.slice(list.length / 2, list.length);

  left = mergeSort(left);
  right = mergeSort(right);

  // merge the sublists
  return merge(left, right);
}

const unsorted = [5, 4, 3, 2, 1];
const sorted = mergeSort(unsorted);
console.log(sorted); // [1, 2, 3, 4, 5]
```

Merge Sort performs in O(n log n) in terms of time complexity, its space complexity is O(n) since it uses auxiliary arrays to store the sublists.
Also, we can leverage multi-threading to implement Merge Sort, sorting each half in separated threads, for example. Moreover, we can combine Merge Sort with other [sorting algorithms](https://ricardoborges.dev/starting-with-sorting-algorithms), for example, instead of splitting the list into single element sublists, we could split into small sublists with a few elements, and apply [Insertion Sort](https://ricardoborges.dev/starting-with-sorting-algorithms) to sort them.


Merge sort is a sorting algorithm that uses a divide-and-conquer technique to sort a given list

Merge Sort

a sorting algorithm is an algorithm that sorts elements in a list into an order, among other uses, sorting can be applied to prepare a set of data for another algorithm, for example, Binary Search.

In this post, I'll describe three sorting algorithms that, although not the most efficient, are easy to understand and are in-place algorithms, meaning that they don't require auxiliary data structures.

### Bubble Sort

Bubble sort starts at the beginning of the list, comparing each pair of adjacent elements, if the first is greater than the second, it swaps them. Then it starts again at the beginning of the list and repeats this process until no swap occurred on the last pass.

![bubble sort](https://res.cloudinary.com/dje4crtui/image/upload/v1627934933/algorithms/sorting/bubble-sort_az17q6.gif)

```typescript
function swap(arr: number[], i: number, j: number) {
  [arr[i], arr[j]] = [arr[j], arr[i]];
}

function bubbleSort(arr: number[]) {
  for (let i = 0; i < arr.length - 1; i++) {
    let swapped = false;

    for (let j = 0; j < arr.length - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        swap(arr, j, j + 1);
        swapped = true;
      }
    }

    if (!swapped) break;
  }
}

const arr = [5, 3, 1, 2, 4];
bubbleSort(arr);
console.log(arr);
```

Since its time complexity is Ο(n^2) on average and worst cases, this algorithm is more suitable for small or nearly ordered data sets.

### Selection Sort

The list is divided into a sorted part at the left and an unsorted part at the right in this algorithm. Initially, the sorted sublist is empty and the unsorted one is all the list. Then it searches for the smallest element in the unsorted sublist and swaps it with the leftmost unsorted element, moving the sublist boundaries one element to the right.

![selection sort](https://res.cloudinary.com/dje4crtui/image/upload/v1627934933/algorithms/sorting/selection-sort_limbbw.gif)

```typescript
function selectionSort(arr: number[]) {
  for (let i = 0; i < arr.length - 1; i++) {
    let min = i;

    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[min]) {
        min = j;
      }
    }

    swap(arr, min, i);
  }
}
```

Like Bubble Sort, this algorithm has a quadratic time complexity Ο(n^2), so it is also more suitable for small or nearly ordered data sets. However, Selection Sort performs fewer swaps than Bubble Sort.

### Insertion Sort

Insertion Sort keeps a sorted sublist at the beginning of the list, and for each element from the list, it searches for the right position in that sublist to _insert_ that element.

![insertion sort](https://res.cloudinary.com/dje4crtui/image/upload/v1627934933/algorithms/sorting/Insertion-sort_txmv8m.gif)

```typescript
function insertionSort(arr: number[]) {
  for (let i = 1; i < arr.length; i++) {
    let value = arr[i];
    let j = i - 1;

    while (j >= 0 && arr[j] > value) {
      arr[j + 1] = arr[j];
      j = j - 1;
    }
    arr[j + 1] = value;
  }
}
```

Insertion sort has a quadratic time complexity for average and worst cases too, however, it's the fastest sorting algorithm for small lists.


In this post, I'll describe three sorting algorithms that, although not the most efficient, are easy to understand.

Starting with sorting algorithms

This is one of those problems that have properties that, given an example, we can identify them right away, like "_check if this array is ordered_", if it contains only a few elements we just have to look at it and we will know.

Before we continue, if necessary, take some time to understand what is a BST reading [this post](https://ricardoborges.dev/data-structures-in-typescript-binary-search-tree).

For example, look at this Binary tree:

![binary tree](https://res.cloudinary.com/dje4crtui/image/upload/v1626722908/data%20structures/tree/bst_yeac5b.png)

You know this is a BST because it satisfy the definition: `left.data <= current.data < right.data`.

So far, we understand the problem and we can identify a BST just looking at it, what is pending now, is the algorithm. Basically, all we have to do is check if every subtree satisfies the definition of the BST, let's see how we would do that.

- Starting with the **root node**, well that node can have any value, in this case, **5**;
- Moving on to the left child node **2**, now this node can't be greater than its parent (**5**);
- Node **2**'s left child **1** also has a limit (**2**);
- Node **2**'s right child **3** must have a value that is greater than its parent (**2**) but less than 5.

Up until now, we have noticed that some node has to be between a minimum and maximum value. Left nodes don't have a minimum constraint, and the root node doesn't have any constraints at all.

- Now moving to the right subtree, the root node's right child **7**, has to be greater than its parent;
- Node **7**'s right child **8** must be greater than **7**;
- Node **7**'s left child **6** must be between **5** and **7**.

Now we know that both subtrees have similar constraints, with this information, we know that our algorithm will start with the root node and will check if some nodes are between some **min** and **max** values, while other nodes don't have a **min** or **max** limit:

```typescript
function isBST(node: BinarySearchTreeNode<number>, min: number, max: number) {}
```

We can do this recursively, so we need a base case:

```typescript
function isBST(node: BinarySearchTreeNode<number>, min: number, max: number) {
  if (!node) return true; // base case
}
```

Next step is to check if the current node, is between those **min** and **max** values, we also have to consider that some nodes don't have those constraints, so we can expect that **min** and **max** can be _null_:

```typescript
function isBST(node: BinarySearchTreeNode<number>, min: number, max: number) {
  if (!node) return true; // base case

  if ((min && node.data <= min) || (max && node.data > max)) {
    return false;
  }
}
```

Finally, we have to do the same for left and right subtrees, if any of them don't satisfy the BST definition we simply return _false_

```typescript
function isBST(node: BinarySearchTreeNode<number>, min: number, max: number) {
  if (!node) return true; // base case

  if ((min && node.data <= min) || (max && node.data > max)) {
    return false;
  }

  // if the right or the left subtree is not a BST, return false
  if (
    !isBST(node.leftNode, min, node.data) ||
    !isBST(node.rightNode, node.data, max)
  ) {
    return false;
  }

  // finally, if all subtrees are under those constraints, return true
  return true;
}
```

That's it, I tried to explain step by step this algorithm, I hope I succeed.


Checking if a Binary Tree is a BST step by step

How to check if a Binary Tree is a BST

In a [Singly Linked List](https://ricardoborges.dev/data-structures-in-typescript-linked-list), each node has only a pointer to the next node, and there are some ways to reverse it, the one that I want to show here doesn't require extra space.

In this algorithm, we start from the list's head, and we use three pointers, each one for **previous node**, **current node** and **next node**.
In the beginning, The **current** and the **next** points to the list's head, and the **previous** points to null. While the **current** are pointing to a node we do the following:

1. **next** point to its next node
2. **current.next** points to **previous node**
3. **previous node** points to the **current node**
4. **current node** points to **next node**

This loop continues until the current points to null, which will mean that we reached the end of the list. Like this:

```typescript
prev = null;
current = head;
next = head;

while (current !== null) {
  next = next.next;
  current.next = prev;
  prev = current;
  current = next;
}
```

A single iteration works like this:

![images](https://res.cloudinary.com/dje4crtui/image/upload/v1626015999/data%20structures/reverse-linked-list_yloqhh.png)

This algorithm may vary according to the Linked List implementation, using [this implementation](https://ricardoborges.dev/data-structures-in-typescript-linked-list), looks like this:

```typescript
function reverse(linkedList: LinkedList<number>) {
  let prev = null;
  let current = linkedList.head;
  let next = linkedList.head;

  while (current !== null) {
    next = next.next;
    current.next = prev;
    prev = current;
    current = next;
  }

  linkedList.head = prev;
}

const linkedList = new LinkedList((a: number, b: number) => a === b);

linkedList.append(1);
linkedList.append(2);
linkedList.append(3);
linkedList.append(4);
linkedList.append(5);

reverse(linkedList);

linkedList.traverse();
```


There are some ways to reverse a Singly Linked List, the one that I want to show here doesn't require extra space.

How to reverse a Singly Linked List

Topological sort is an ordering of the vertices of a directed acyclic graph, in a way that if there is an edge from a vertex A to B, then A comes before B. For example, let's say there is a set of projects and some of them depend on other projects:

![graph](https://res.cloudinary.com/dje4crtui/image/upload/v1625769510/data%20structures/top_sort_q7iaub.png)

In this example project B and C depends on project A, and project D depends on projects B and C. Therefore, project A must be executed first, then projects B and C, and finally project D. Resulting in this order: [A, B, C, D] or [A, C, B, D].

Note that we start from node A because it doesn't have dependencies and repeat it, that is after A is done, B and C haven't dependencies anymore, so we can choose either one to be the next. That's why this algorithm works only on acyclic graphs.

We can use a modified depth-first search for this algorithm, [here I talk more about DPS](https://ricardoborges.dev/data-structures-in-typescript-graph). The steps are the following:

1 - For every unvisited node visit it and its adjacent nodes (DPS)
2 - After visiting a node and its adjacent add it at the beginning of a list (you can use a stack instead), this list will be in the topological order.

Here's an implementation in TypeScript, I'm using [this implementation of a graph](https://ricardoborges.dev/data-structures-in-typescript-graph):

```typescript
function topSort(
  node: Node<number>,
  visited: Map<number, boolean>,
  order: number[]
) {
  if (!node) return;

  // set node as visited
  visited.set(node.data, true);

  // for each of node's unvisited adjacent call topSort
  node.adjacent.forEach((item) => {
    if (!visited.has(item.data)) {
      topSort(item, visited, order);
    }
  });

  // add node at the beginning of the order list
  order.unshift(node.data);
}

// topological order list
const order = [];
// map to keep track of visited nodes
const visited = new Map();

// For every unvisited node visit it and its adjacent nodes
for (const entry of graph.nodes.entries()) {
  const node = entry[1];
  if (!visited.has(node.data)) {
    topSort(node, visited, order);
  }
}
```

There are other problems that topological sorting can resolve, like the order that courses have to be selected during college, since they may have other courses as a prerequisite. Or even the order of steps of a recipe, in which some must be taken before others.

There are a lot of explanations for this algorithm on the internet, here I tried to explain it in a little different way, I hope this helped you to make sense of it or if you haven't heard about topological sorting before, at least this may be an introduction of it.


Topological sort is an ordering of the vertices of a directed acyclic graph, in a way that if there is an edge from a vertex A to B, then A comes before B.