Skip to content

Latest commit

 

History

History
87 lines (77 loc) · 10.6 KB

README.md

File metadata and controls

87 lines (77 loc) · 10.6 KB
Raw

ALGORITHM

Algorithms and data structures in Golang

Data Structures

Data Structures are representations of data sets in a way which makes storage and performing of operations of data very easy.

Classification of Data Structures

  • Linear

    • List : is an abstract data type that represents a finite number of ordered values, where the same value may occur more than once.
    • Set : is an abstract data type can store unique values without any particular order.
    • Tuple : is a finite ordered list (sequence) of elements. Tuple is a reference type.
    • Queue : is an abstract data type that implements a First-In-First-Out (FIFO) queue of generic items.
    • Stack : is an abstract data type that operates on the concept of the Last-In-First-Out (LIFO) principle.
    • Heap : is a specialized tree-based data structure that satisfies the heap property: for any node, the value of that node is greater than or equal to the values of its children.

  • Non - Linear

    • Trees : is a data structure that consists of a set of nested nodes, each node having a value and a set of child nodes.
    • Tables : is a data structure that consists of a set of rows and columns, each row having a set of columns. The table is a two-dimensional array. The table is a reference type.
    • Containers : is a data structure that consists of a set of elements, each element having a key and a value. The container is a reference type. The container is a reference type.

  • Homogeneous

  • Heterogeneous

    • Linked List: is a data structure that consists of a set of nodes, each node having a value and a reference to the next node.
      • Single Linked List : is a data structure that consists of a set of nodes, each node having a value and a reference to the next node. The list is a reference type.
      • Double Linked List : is a data structure that consists of a set of nodes, each node having a value and a reference to the previous and next node. The list is a reference type.
      • Circular Linked List : is a data structure which has the last item contains link of the first element as next and the first element has a link to the last element as previous. The list is a reference type.
        • Circular Single Linked List : is a data structure which has the last item contains link of the first element as next and the first element has a link to the last element as previous. The list is a reference type.
        • Circular Double Linked List : is a data structure which has the last item contains link of the first element as next and the first element has a link to the last element as previous. The list is a reference type.
    • Ordered List : is a data structure that consists of a set of nodes, each node having a value and a reference to the next node. The list is a reference type.
    • Unordered List : is a data structure that consists of a set of nodes, each node having a value and a reference to the next node. The list is a reference type.

  • Dynamic

Algorithms

Algorithm is a set of instructions that describes how to get something done.

Classification of Algorithms

  • SORT

    • Bubble Sort : is a simple sorting algorithm that repeatedly steps through the list, compares elements and swaps them if they are in the wrong order. Bubble Sort has a time complexity of O(n2).
    • Merge Sort : is a comparison based sort that recursively splits the list into smaller sub-lists until the sub-lists are small enough to be sorted individually. Merge Sort was invented by John Von Neumman in 1945. It has a time complexity of O(n log n).
    • Comb Sort : is a sorting algorithm that uses a gap sequence to sort the array. It is a variant of the Bubble Sort algorithm. Comb Sort has a time complexity of O(n2). The algorithm is a variation of the bubble sort algorithm. It was originally designed by Włodzimierz Dobosiewicz and Artur Borowy in 1980
    • Heap Sort : is a comparison based sort that uses a heap data structure to sort the list. Heap Sort has a time complexity of O(n log n).
    • Quick Sort : is a comparison based sort that uses a divide and conquer strategy to sort the list. Quick Sort has a time complexity of O(n log n).
    • Selection Sort : is a comparison based sort that finds the smallest element in the list and places it at the beginning. Selection Sort has a time complexity of O(n2).
    • Insertion Sort : is a comparison based sort that builds the final sorted array one item at a time. Insertion Sort has a time complexity of O(n2).
    • Radix Sort : is a comparison based sort that sorts the list by grouping the list into buckets. It avoids comparison by creating and distributing elements into buckets according to their radix. Radix Sort has a time complexity of O(n2). uncomplete
    • Bucket Sort
    • Shell Sort
    • Tree Sort
    • Counting Sort
    • Smooth Sort
    • Bogo Sort
    • Cycle Sort
    • Gnome Sort
    • Stooge Sort

  • Recursion

    • Fibonacci : is a recursive algorithm that adds the two preceding numbers to produce the next number in the sequence.
    • Factorial : is a recursive algorithm that multiplies all the preceding numbers to produce the next number in the sequence.
    • Euclidean / GCD : is a recursive algorithm that finds the greatest common divisor of two numbers.
    • LCM : is a recursive algorithm that finds the least common multiple of two numbers.
    • Tower of Hanoi : is a recursive algorithm that moves a stack of disks from one tower to another.
    • Ackermann Function : is a recursive algorithm that finds the value of the Ackermann function. It is a total recursive function that can be defined in terms of itself.
    • McCarthy Function : is a recursive algorithm that finds the value of the McCarthy function. It is a total recursive function that can be defined in terms of itself.
    • Palindrome : is an algorithm that checks if a word is equal to its reversed.

  • Search

    • Binary Search : is a search algorithm that finds the position of a target value in a sorted array. It has a time complexity of O(log n) and a space complexity of O(1).
    • Interpolation Search : is a search algorithm that finds the position of a target value in a sorted array.
    • Jump to Search : is a search algorithm that finds the position of a target value in a sorted array. It is a variation of the Binary Search algorithm. It has a time complexity of O(log n) and a space complexity of O(1).
    • Linear Search : is a search algorithm that finds the position of a target value in a sorted array. It has a time complexity of O(n) and a space complexity of O(1).
    • Ternary Search : is a search algorithm that finds the position of a target value in a sorted array.
    • Breadth-First Search : is a search algorithm that finds the position of a target value in a graph. It has a time complexity of O(n) and a space complexity of O(n).

  • Cipher

    • Caesar Cipher : is a cipher that shifts each letter in a message by a certain number of places. It has a time complexity of O(n).
    • Vigenere Cipher : is a cipher that shifts each letter in a message by a certain number of places. It has a time complexity of O(n).
    • Hill Cipher : is a cipher that shifts each letter in a message by a certain number of places. It has a time complexity of O(n).uncomplete
    • Rot13 Cipher : is a cipher that shifts each letter in a message by 13 number of places. It has a time complexity of O(n).

  • Graph

    • A* Search : is a search algorithm that finds the shortest path between two nodes in a graph. It has a time complexity of O(n) and a space complexity of O(b^d).
    • Dijkstra's Algorithm : is a search algorithm that finds the shortest path between two nodes in a graph. It has a time complexity of O(n) and a space complexity of O(n).