# 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 tail?: Node<T>

constructor() {
this.length = 0
}

enqueue(item: T): void {
const node = {value:item} as Node<T>
this.length++
if(!this.tail) {
return
}

this.tail.next = node
this.tail = node
}

deque(): T | undefined {
return undefined
}

this.length--

}

peek(): T | undefined {
}
}
``````

## 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
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;

constructor() {
this.length = 0
}

push(item: T): void {
const node = { value: item } as Node<T>

this.length++
return
}
}

pop(): T | undefined {
this.length = Math.max(0, this.length - 1)
if (this.length === 0) {
}