EcmaScript 6 Algorithms and Data Structures

This repository contains some popular Data Structures and Algorithms done in JavaScript ES6.

Data Structures

According to Wikipedia:

In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.

The following terms are the foundation terms of a data structure.

• Interface - This represents the set of operation supported by a data structure
• Implementation - This provides the definition of algorithms used in the operations of the data structure i.e. it provides the internal representation of the data structure

Characteristics of a Data Structure

1. Correctness - a data structure should implement its interface correctly
2. Time Complexity - execution time of operations of a data structure should be as small as possible
3. Space Complexity - memory usage of a data structure operation should be as little as possible

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)
AVL Tree	log(n)	log(n)	log(n)	log(n)

Shown below are the data structures covered here:

• Array
• Linked List
• Doubly Linked List
• Stack
• Queue
• Priority Queue
• Set
• Disjoint Set
• Bloom Filter
• Skip List
• Hash Table
• Graph
• Tree
• Binary Search Tree
• AVL Tree
• Red Black Tree
• Splay Tree
• B-Tree
• Trie
• Min Heap
• Max Heap
• Binomial Heap
• Fibonacci Heap

Algorithms

This is a process or set of rules to be followed in calculations or other problem-solving operations, especially by a computer.

The following are the algorithms covered here:

Algorithms by Topic

• Searching
  • Linear Search
  • Binary Search
  • Jump/Block Search
  • Interpolation Search
• Sorting
  • Shell Sort
  • Heap Sort
  • Quick Sort
  • Radix Sort
  • Merge Sort
  • Bubble Sort
  • Insertion Sort
  • Counting Sort
  • Selection Sort
• Sets
  • Longest Increasing Subsequence
  • Longest Common Subsequence (LCS)
  • Shortest Common Supersequence (SCS)
  • Permutations (with and without repetitions)
  • Combinations (with and without repetitions)
  • Combination Sum - find all combinations that form specific sum
  • Maximum Subarray - "Brute Force" and "Dynamic Programming" (Kadane's) versions

Algorithms by Paradigm

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.

• Brute Force - look at all the possibilities and selects the best solution
  • Linear Search
  • Maximum Subarray
  • Travelling Salesman Problem - shortest possible route that visits each city and returns to the origin city
• Greedy - choose the best option at the current time, without any consideration for the future
  • Prim’s Algorithm - finding MST for weighted undirected graph
  • Dijkstra Algorithm - finding shortest path to all graph vertices
  • Kruskal’s Algorithm - finding Minimum Spanning Tree (MST) for weighted undirected graph
• Divide and Conquer - divide the problem into smaller parts and then solve those parts
  • Quick Sort
  • Merge Sort
  • Binary Search
  • Tower of Hanoi
  • Pascal's Triangle
  • Euclidean Algorithm - GCD
  • Tree Depth-First Search (DFS)
  • Graph Depth-First Search (DFS)
  • Permutations (with and without repetitions)
  • Combinations (with and without repetitions)
• Dynamic Programming - build up a solution using previously found sub-solutions
  • Fibonacci

Array Sorting Algorithms Complexity

Name	Best	Average	Worst	Memory	Stable
Bubble sort	n	n2	n2	1	Yes
Insertion sort	n	n2	n2	1	Yes
Selection sort	n2	n2	n2	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)	n2	log(n)	No
Shell sort	n log(n)	depends on gap sequence	n (log(n))2	1	No
Counting sort	n + r	n + r	n + r	n + r	Yes
*