Sorting algorithms

Bubble sort

In an unordered array, starting from the beginning, if the current value is greater than the next value, we swap them, and then move to the next value and repeat the process. After each iteration, the biggest value is always at the end, and we can start over without including the last n values.

export default function bubble_sort(arr: number[]): void {
    for (let i = 0; i < arr.length ; i++) {
        for (let j = 0; j < arr.length - 1 - i; j++) {
            if(arr[j] > arr[j + 1]) {
                const tmp = arr[j]
                arr[j] = arr[j + 1]
                arr[j + 1] = tmp
            }
        }
    }
}

In this example:

• -1 is used to avoid comparing the last value of the array with nothing (out of bounds error).
• - i is used to avoid comparing values already compared, as the last value of each pass is the biggest.

This Big O for this algorithm is O(n²).

Queue

A queue is a specific implementation of a linked list.

A queue is FIFO structure, for First I, First Out. It's like a real life queue or line, where a new entrant gets in the queue through its end. And if we want to remove an entry, we remove the first in the queue.

There are usually three operations associated with a queue:

Enqueue

Adding to the queue through its tail

Deque

Removing from the queue through its head

Peek

Seeing what is the first element of the queue

Example:

type Node<T> = {
    value: T,
    next?: Node<T>,
}
 
export default class Queue<T> {
    public length: number;
    private head?: Node<T>
    private tail?: Node<T>
 
    constructor() {
        this.head = this.tail = undefined
        this.length = 0
    }
 
    enqueue(item: T): void {
        const node = {value:item} as Node<T>
        this.length++
        if(!this.tail) {
            this.tail = this.head = node
            return
        }
 
        this.tail.next = node
        this.tail = node
    }
 
    deque(): T | undefined {
        if(!this.head) {
            return undefined
        }
 
        this.length--
 
        const head = this.head
        this.head = this.head.next
        return head.value
    }
 
    peek(): T | undefined {
        return this.head?.value
    }
}

Stack

A stack is a specific implementation of a linked list.

A queue is LIFO structure, for Last I, First Out. It's like a real life stack of plates, where a new entrant gets in the stack through its head. And if we want to remove an entry, we remove the last in the queue.

There are usually three operations associated with a queue:

Push

Adding to the stack through its head

Pop

Removing from the stack through its tail

Peek

Seeing what is the first element of the stack

Example:

type Node<T> = {
    value: T,
    prev?: Node<T>
}
 
export default class Stack<T> {
    public length: number;
    private head?: Node<T>
 
    constructor() {
        this.head = undefined
        this.length = 0
    }
 
    push(item: T): void {
        const node = { value: item } as Node<T>
 
        this.length++
        if (!this.head) {
            this.head = node
            return
        }
        node.prev = this.head
        this.head = node
    }
 
    pop(): T | undefined {
        this.length = Math.max(0, this.length - 1)
        if (this.length === 0) {
            const head = this.head
            this.head = undefined
            return head?.value
        }
        const head = this.head as Node<T>
        this.head = head.prev
        return head.value
    }
 
    peek(): T | undefined {
        return this.head?.value
    }
}