# Algorithms and Data Structures in JavaScript

## JavaScript Algorithms and Data Structures

This repository contains JavaScript based examples of many popular algorithms and data structures.

## Data Structures

Data structure is a particular way of organizing and storing data in a computer so that it can be accessed and modified efficiently. More precisely, a data structure is a collection of data values, the relationships among them, and the functions or operations that can be applied to the data.

## Algorithms

Algorithm is an unambiguous specification of how to solve a class of problems. Algorithm is a set of rules that precisely defines a sequence of operations.

### Algorithms by Topic

An algorithmic paradigm is a generic method or approach which underlies the design of a class of algorithms. It is an abstraction higher than the notion of an algorithm, just as an algorithm is an abstraction higher than a computer program.

## How to use this repository

#### Install all dependencies

`npm install`

#### Run all tests

`npm test`

#### Run tests by name

`npm test -- -t 'LinkedList'`

#### Playground

You may play with data-structures and algorithms in `./src/playground/playground.js` file and write tests for it in `./src/playground/__test__/playground.test.js` .

Then just simply run the following command to test if your playground code works as expected:

`npm test -- -t 'playground'`

## Useful Information

### Big O Notation

Order of growth of algorithms specified in Big O notation.

Source: Big O Cheat Sheet .

Below is the list of some of the most used Big O notations and their performance comparisons against different sizes of the input data.

Big O Notation Computations for 10 elements Computations for 100 elements Computations for 1000 elements
O(1) 1 1 1
O(log N) 3 6 9
O(N) 10 100 1000
O(N log N) 30 60 9000
O(N^2) 100 10000 1000000
O(2^N) 1024 1.26e+29 1.07e+301
O(N!) 3628800 9.3e+157 4.02e+2567

### Data Structure Operations Complexity

Data Structure Access Search Insertion Deletion
Array 1 n n n
Stack n n 1 1
Queue n n 1 1
Linked List n n 1 1
Hash Table - n n n
Binary Search Tree n n n n
B-Tree log(n) log(n) log(n) log(n)
Red-Black Tree log(n) log(n) log(n) log(n)
AVL Tree log(n) log(n) log(n) log(n)

### Array Sorting Algorithms Complexity

Name Best Average Worst Memory Stable
Bubble sort n n^2 n^2 1 Yes
Insertion sort n n^2 n^2 1 Yes
Selection sort n^2 n^2 n^2 1 No
Heap sort n log(n) n log(n) n log(n) 1 No
Merge sort n log(n) n log(n) n log(n) n Yes
Quick sort n log(n) n log(n) n^2 log(n) No
Shell sort n log(n) depends on gap sequence n (log(n))^2 1 No