Please enable JavaScript.
Coggle requires JavaScript to display documents.
Algorithms, Sorting - Coggle Diagram
Algorithms
Asymptotic notations used to describe the running time of an algorithm when the input tends towards a particular value or a limiting value.
Constant time: O(1) - an algorithm is said to run in constant time if it requires the same amount of time regardless of the input size. Ex: array - accessing any element; fixed-size stack - push/pop methods;
Linear time: O(n) - ... in linear time if its time execution is directly proportional to the input size, i.e., time grows linearly as input size increases. Ex: array - linear search, find minimum; ArrayList - contains method; queue - contains method.
Logarithmic time: - O(log n) - ...in logarithmic time if its time execution is proportional to the logarithm of the input size. Ex: binary search.
Quadratic time: - O(n2) - ...in logarithm time if its time is proportional to the square of the input size. Ex; bubbles sort, insertion sort, selection sort (nested loops).
-
-
Data structure: linear - the elements are arranged in sequence one after the other: a) array b) stack - elements are stored in the LIFO principle (Last In, First Out) c) queue - FIFO (First In, First Out) d) linked list - connected through a series of nodes; non-linear - arranged in a hierarchical manner where one element will be connected to one or more elements: a) graphs - each node is called vertex and each vertex is connected to other vertices through edges. b) tree - there can only be one edge between 2 vertices.
Divide and conquer algorithm : 1. breaking the problem into smaller sub-problems; 2. solving the sub-problems, and 3. combining them to get desired output (recursion). The result of each subproblem is not stored for future reference, whereas, in a dynamic approach, the result of each subproblem is stored for future reference.
-
Hash table data structure stores elements in key-value pairs where: key - unique integer that is used for indexing the values; value - data that are associated with keys
Heap Data Structure is a complete binary tree that satisfies the heap property, where any given node is: always greater than its child node/s and the key of the root node is the largest among all other nodes. This property is also called max heap property; always smaller than the child nodes and the key of the root node is the smallest among all other nodes. This property is also called min heap property.
-
-
Dynamic programming is a technique in computer programming that helps to efficiently solve a class of problems that have overlapping subproblems and optimal substructure property. (fibonacci)
Balanced Binary Tree is defined as binary tree in which the height of the left and right subtree of any node differ by not more than 1
-
Sorting
-
-
Selection selects the smallest element from an unsorted list in each iteration and places that element at the beginning at the unsorted list
Insertion places an unsorted element at its suitable place in each iteration. We assume that the first card is already sorted then, we select an unsorted card. If the unsorted card is greater than the card in hand, it is placed on the right otherwise, to the left. In the same way, other unsorted cards are taken and put in their right place.
Merge is divided into multiple sub-problems. Each sub-problem is solved individually. Sub-problems are combined to form the final solution.
Quicksearch - array is divided into subarrays by selecting a pivot element (left from pivot - less, right - greater). Left and right also are divided. Elements are combined.
Counting sorts the elements of an array by counting the number of occurrences of each unique element in the array. The count is stored in an auxiliary array and the sorting is done by mapping the count as an index of the auxiliary array.
Radix sorts the elements by first grouping the individual digits of the same place value. Then, sort the elements according to their increasing/decreasing order.
Bucket divides the unsorted array elements into several groups called buckets. Each bucket is then sorted by using any of the suitable sorting algorithms or recursively applying the same bucket algorithm.
Shell is a generalized version of the insertion sort. It first sorts elements that are far apart from each other and successively reduces the interval between the elements to be sorted.
Linear is a sequential searching where we start one end and check every element of the list until the desired element is found.
Binary is a searching algorithm for finding an element's position in a sorted array. In this approach, the element is always searched in the middle of a portion of an array. Can be implemented only on a sorted list of items. If the elements are not sorted already, we need to sort them first.