function linear_search(List, target):
var found <-- Falsefor counter = 1 to len(List)if Lit[counter] == target thenfound <-- Truereturn found, counterO(n)
https://www.geeksforgeeks.org/iterative-merge-sort/ # Iterative Merge sort (Bottom Up) # Iterative mergesort function to # sort arr[0...n-1] def mergeSort(a): current_size = 1 # Outer loop for traversing Each # sub array of current_size while current_size < len(a) - 1: left = 0 # Inner loop for merge call # in a sub array # Each complete Iteration sorts # the iterating sub array while left < len(a)-1: # mid index = left index of # sub array + current sub # array size - 1 mid = left + current_size - 1 # (False result,True result) #[Condition] Can use current_size # if 2 * current_size < len(a)-1 # else len(a)-1 right = ((2 * current_size + left - 1, len(a) - 1)[2 * current_size + left - 1 > len(a)-1]) # Merge call for each sub array merge(a, left, mid, right) left = left + current_size*2 # Increasing sub array size by # multiple of 2 current_size = 2 * current_size # Merge Function def merge(a, l, m, r): n1 = m - l + 1 n2 = r - m L = [0] * n1 R = [0] * n2 for i in range(0, n1): L[i] = a[l + i] for i in range(0, n2): R[i] = a[m + i + 1] i, j, k = 0, 0, l while i < n1 and j < n2: if L[i] > R[j]: a[k] = R[j] j += 1 else: a[k] = L[i] i += 1 k += 1 while i < n1: a[k] = L[i] i += 1 k += 1 while j < n2: a[k] = R[j] j += 1 k += 1 # Driver code a = [12, 11, 13, 5, 6, 7] print("Given array is ") print(a) mergeSort(a) print("Sorted array is ") print(a) # Contributed by Madhur Chhanganishifting is faster than swapping
def insertion_sort(a):for i in range(1, len(a)): curVal =a[i] j = i-1 while j >=0 and curVal < a[j]: a[j+1] = a[j] j -= 1 a[j+1] = curVal# for a graph represented in a dictionary {node : [nbrs]}def df_recursive(graph, start, path=[]): path += [start] ## showing in visited order for v in graph[start]: if v not in path: path = df_recurive(graph, v, path) return pathdef df_iterative(graph, start): path, stack = [], [start] while stack: v = stack.pop() ## pop(index) if v not in path: path.append(v) for nbr in graph[v]: stack.append(nbr) return path# For a graph created with Graph() and Vertex(), more properties could be included - more realistic.to be continued...# for a graph represented in a dictionary {node : [nbrs]}def bf_iterative(graph, start): path, queue = [], [start] while queue: v = queue[0] path += [v] queue = queue[1:] for u in graph[v]: if u not in queue: queue.append(u) return path# this graph is a simple one. try weighted, directed.# a maze solving algorithm, or a routing one, can employ DFS, BFS, Dijkstra, A*
# Because of weights, use a graph created with Graph() and Vertex()g = {'a' : [{'b':5}, {'c':1}], 'b' : [{'c':5}, {'d':3}],'c' : [{'e':2}, {'f':6}], 'e' : [], 'f' : []}g = []g = [def dijkstra(graph, start):"""the node with the lowest distance get checked nextits neighbour are pushed into the list, then sortedstart = the name of the start nodereturn the list ordered by distance"""visited=[]stack = [{start: 0}] # the distance reaching this node from swhile stack :s= stack.pop()key= s.key()nbrs = graph[key]for x in nbrs: ## a {key: value}x.value += s.valuestack.append(x)visited.append(s)stack = stack.sorted(stack.items(), key=lambda x: x[1], reverse=True)# if not true, then pop(0)improved Dijkstra, by considering the distance to the destination, not just the distance travelled -a heuristic solution.
Until all nodes are traversed −Step 1 − Visit root node.Step 2 − Recursively traverse left subtree.Step 3 − Recursively traverse right subtree.Until all nodes are traversed −Step 1 − Recursively traverse left subtree.Step 2 − Visit root node.Step 3 − Recursively traverse right subtree.Until all nodes are traversed −Step 1 − Recursively traverse left subtree.Step 2 − Recursively traverse right subtree.Step 3 − Visit root node.import java.util.ArrayList;public class MyClass { public static void main(String args[]) { String[] letters = new String[]{"A", "B", "C", "D","E"}; //, "F", "G", "H","J", "K", "L", "M" };//{'A', 'B', 'C', 'D','E', 'F', 'G', 'H','J', 'K', 'L', 'M' }; Node[] nodeList= new Node[12]; ArrayList<Node> nodes = new ArrayList<Node>(); for (int i=0; i < letters.length; i++){ Node a=null; a = new Node(letters[i]); System.out.println(i + ": Value: " + a.getValue()); nodeList[0] = a; nodes.add(a); } System.out.println("length of nodeList: " + nodeList.length); System.out.println("length of nodes: " + nodes.size()); System.out.println(nodeList[0].getValue()); try{ for (int i = 0; i < nodeList.length; i++){ System.out.println(i + ": Value: " + nodeList[i].getValue()); }} catch(Exception e){ System.out.println("Something is wrong"); //e.message()); } try{ for (int i = 0; i < nodes.size(); i++){ System.out.println(i + ": Value: " + nodes.get(i).getValue()); }} catch(Exception e){ System.out.println("Something is wrong"); //e.message()); } BTree binaryTree1 = new BTree(nodes.get(2)); for (int i = 0; i<nodes.size(); i++){ binaryTree1.add(binaryTree1.getRoot(), nodes.get(i)); System.out.println(i+1 + " nodes into the tree ----------"); } //String visited = ""; //visited = binaryTree1.in_order(nodes.get(2), visited); // System.out.println(visited); System.out.println( " PRE-------------------------------------------------"); //System.out.println("size of tree: "+ binaryTree1.size()); //binaryTree1.preOrder(nodes.get(2)); System.out.println( " IN-------------------------------------------------"); //binaryTree1.inOrder(nodes.get(2)); System.out.println( " POST------------------------------------------------"); binaryTree1.postOrder(nodes.get(2)); System.out.println( " ------------------------------------------------"); }}class Node{ String value; Node left; Node right; public Node(String v){ this.value = v; this.left = null; this.right = null; } String getValue(){ return this.value; } Node getLeft(){ return this.left; } Node getRight(){ return this.right; } void setLeft(Node l){ this.left = l; } void setRight(Node r){ this.right = r; }}class BTree{ Node root; public BTree(Node root){ this.root = root; } Node getRoot(){ return this.root; } void add(Node root, Node nd){ System.out.println("-----------------------"); System.out.println(root.getValue() + " : " + nd.getValue()); System.out.println(root.getLeft() + " L:R " + nd.getRight()); int diff = (root.getValue()).compareTo(nd.getValue()); System.out.println(diff); if (diff >= 0){ System.out.println("LEFT branch"); if( root.getLeft() == null){ root.setLeft(nd); return; }else{ add(root.getLeft(), nd); } System.out.println("LEFT branch done."); }else { System.out.println("RIGHT branch"); if (root.getRight() == null){ root.setRight(nd); return; }else{ add(root.getRight(), nd); } System.out.println("RIGHT branch done!"); } } String in_order(Node root, String visited){ if (root.getLeft()!= null){ in_order(root.getLeft(), visited); } visited += root.getValue() + " : "; if (root.getRight() != null){ in_order(root.getRight(), visited); } return visited; } void inOrder(Node node) { //A B C C F E if (node == null) { return; } inOrder(node.getLeft()); //System.out.println(node.getValue()); System.out.printf("%s ", node.getValue()); inOrder(node.getRight()); } void preOrder(Node node) { //A B C C F E if (node == null) { return; } //System.out.println(node.getValue()); System.out.printf("%s ", node.getValue()); preOrder(node.getLeft()); preOrder(node.getRight()); } void postOrder(Node node) { //A B C C F E if (node == null) { return; } postOrder(node.getLeft()); postOrder(node.getRight()); System.out.printf("%s ", node.getValue()); //System.out.println(node.getValue()); }}class Graph:"""directed, weighted, undirected, unweighted, vertices {}, add_node, add_edge, """def __init__():import java.util.ArrayList;public class MyClass { public static void main(String args[]) { String[] letters = new String[]{"A", "B", "C", "D","E", "F", "G", "H","J", "K", "L", "M" };//{'A', 'B', 'C', 'D','E', 'F', 'G', 'H','J', 'K', 'L', 'M' }; Node[] nodeList= new Node[12]; ArrayList<Node> nodes = new ArrayList<Node>(); for (int i=0; i < letters.length; i++){ Node a=null; a = new Node(letters[i], null, null); System.out.println(i + ": Value: " + a.getValue()); nodeList[0] = a; nodes.add(a); } System.out.println("length of nodeList: " + nodeList.length); System.out.println(nodeList[0].getValue()); try{ for (int i = 0; i < nodeList.length; i++){ System.out.println(i + ": Value: " + nodeList[i].getValue()); }} catch(Exception e){ System.out.println("Something is wrong"); //e.message()); } try{ for (int i = 0; i < nodes.size(); i++){ System.out.println(i + ": Value: " + nodes.get(i).getValue()); }} catch(Exception e){ System.out.println("Something is wrong"); //e.message()); } BTree binaryTree1 = new BTree(nodes.get(6)); for (int i = 0; i<nodes.size(); i++){ binaryTree1.add(binaryTree1.getRoot(), nodes.get(i)); } }}class Node{ String value; Node left; Node right; public Node(String v, Node l, Node r){ this.value = v; this.left = l; this.right = r; } String getValue(){ return this.value; } Node getLeft(){ return this.left; } Node getRight(){ return this.right; } void setLeft(Node l){ this.left = l; } void setRight(Node r){ this.right = r; }}class BTree{ Node root; public BTree(Node root){ this.root = root; } Node getRoot(){ return this.root; } void add(Node root, Node nd){ System.out.println(root.getValue() + " : " + nd.getValue()); System.out.println(root.getLeft() + " L:R " + nd.getRight()); if ((root.getValue()).compareTo(nd.getValue())>=0){ System.out.println("LEFT branch"); if( root.getLeft() == null){ root.setLeft(nd); return; }else{ add(root.getLeft(), nd); } }else { System.out.println("RIGHT branch"); if (root.getRight() == null){ root.setRight(nd); return; }else{ add(root.getRight(), nd); } } }}import randomclass Node: def __init__(self, v): self.value = v self.left = None self.right = Noneclass BinaryTree: def __init__(self, root): self.root = root def addNode(self, root, node): if root.value > node.value: if root.left == None: root.left = node return True; else: self.addNode(root.left, node) else: if root.right == None: root.right = node return True else: self.addNode(root.right, node) def inOrder(self, root): if root == None: return self.inOrder(root.left) print(root.value, end=", ") self.inOrder(root.right) def preOrder(self, root): if root == None: return print(root.value, end=", ") self.preOrder(root.left) self.preOrder(root.right) def postOrder(self, root): if root == None: return self.postOrder(root.left) self.postOrder(root.right) print(root.value, end=", ")random.seed(2)numbers = [random.randint(1, 100) for i in range(20)]print(numbers)rt = Node(50)tree = BinaryTree(rt)for i in range(len(numbers)): node = Node(numbers[i]) tree.addNode(rt, node)print("____IN ORDER_____")tree.inOrder(rt)print()print("____IN ORDER_____")print("____PRE ORDER_____")tree.preOrder(rt)print()print("____pre ORDER_____")print("____post ORDER_____")tree.postOrder(rt)print()print("____post ORDER_____")import randomclass Node: def __init__(self, v): self.value = v self.left = None self.right = Noneclass BinaryTree: def __init__(self, root): self.root = root self.visited_post=[] self.visited_pre=[] self.visited_in=[] def addNode(self, root, node): if root.value > node.value: if root.left == None: root.left = node return True; else: self.addNode(root.left, node) else: if root.right == None: root.right = node return True else: self.addNode(root.right, node) def inOrder(self, root): if root == None: return self.inOrder(root.left) print(root.value, end=", ") self.inOrder(root.right) def preOrder(self, root): if root == None: return print(root.value, end=", ") self.preOrder(root.left) self.preOrder(root.right) def postOrder(self, root): if root == None: return self.postOrder(root.left) self.postOrder(root.right) print(root.value, end=", ") def preOrder2(self, root): if root == None: return #print(root.value, end=", ") self.visited_pre.append(root.value) self.preOrder2(root.left) self.preOrder2(root.right) def inOrder2(self, root): if root == None: return self.inOrder2(root.left) #print(root.value, end=", ") self.visited_in.append(root.value) self.inOrder2(root.right) def postOrder2(self, root): if root == None: return "" self.postOrder2(root.left) self.postOrder2(root.right) #print(root.value, end=", ") self.visited_post.append(root.value) returnrandom.seed(2)numbers = [random.randint(1, 100) for i in range(5)]print(numbers)rt = Node(50)tree = BinaryTree(rt)for i in range(len(numbers)): node = Node(numbers[i]) tree.addNode(rt, node)print("____IN ORDER_____")tree.inOrder(rt)print()print("____IN ORDER_____")print("____PRE ORDER_____")tree.preOrder(rt)print()print("____pre ORDER_____")print("____post ORDER_____")tree.postOrder(rt)print()print("____post ORDER_____")vs= ""tree.inOrder2(rt)tree.preOrder2(rt)tree.postOrder2(rt)print("--in-order--------------")for i in range(len(tree.visited_in)):##-1, 0, -1): print(tree.visited_in[i], end=", ")print("\n--pre-order--------------")for i in range(len(tree.visited_in)):##-1, 0, -1): print(tree.visited_pre[i], end=", ")print("\n--post-order--------------")for i in range(len(tree.visited_in)):##-1, 0, -1): print(tree.visited_post[i], end=", ")dictionary in python
d = dict()d ={}value = d[key]d[key] = valuePython Dictionary clear()Removes all ItemsPython Dictionary copy()Returns Shallow Copy of a DictionaryPython Dictionary fromkeys()creates dictionary from given sequencePython Dictionary get()Returns Value of The KeyPython Dictionary items()returns view of dictionary's (key, value) pairPython Dictionary keys()Returns View Object of All KeysPython Dictionary popitem()Returns & Removes Element From DictionaryPython Dictionary setdefault()Inserts Key With a Value if Key is not PresentPython Dictionary pop()removes and returns element having given keyPython Dictionary values()returns view of all values in dictionaryPython Dictionary update()Updates the DictionaryPython any()Checks if any Element of an Iterable is TruePython all()returns true when all elements in iterable is truePython ascii()Returns String Containing Printable RepresentationPython bool()Converts a Value to BooleanPython dict()Creates a DictionaryPython enumerate()Returns an Enumerate ObjectPython filter()constructs iterator from elements which are truePython iter()returns iterator for an objectPython len()Returns Length of an ObjectPython max()returns largest elementPython min()returns smallest elementPython map()Applies Function and Returns a ListPython sorted()returns sorted list from a given iterablePython sum()Add items of an IterablePython zip()Returns an Iterator of Tupleshttps://www.programiz.com/python-programming/methods/dictionary
set in python
s = set()s= {}s = set([iterable])s.add(item)s.update([multiple items])s ={1,2}s.update([4,5,6], {7,8,9}){1,2,3,4,5,6,7,8,9}s.discard(4)s.remove(5)s.pop()s.clear()s.union(s2)add()Adds an element to the setclear()Removes all elements from the setcopy()Returns a copy of the setdifference()Returns the difference of two or more sets as a new setdifference_update()Removes all elements of another set from this setdiscard()Removes an element from the set if it is a member. (Do nothing if the element is not in set)intersection()Returns the intersection of two sets as a new setintersection_update()Updates the set with the intersection of itself and anotherisdisjoint()Returns True if two sets have a null intersectionissubset()Returns True if another set contains this setissuperset()Returns True if this set contains another setpop()Removes and returns an arbitary set element. Raise KeyError if the set is emptyremove()Removes an element from the set. If the element is not a member, raise a KeyErrorsymmetric_difference()Returns the symmetric difference of two sets as a new setsymmetric_difference_update()Updates a set with the symmetric difference of itself and anotherunion()Returns the union of sets in a new setupdate()Updates the set with the union of itself and otherstuple in python
t = tuple() t= (1, 2, 3, 4, 5, 6) - immutablet[2] https://www.programiz.com/python-programming/methods/tuple
Python Tuple count()returns occurrences of element in a tuplePython Tuple index()returns smallest index of element in tuplePython any()Checks if any Element of an Iterable is TruePython all()returns true when all elements in iterable is truePython ascii()Returns String Containing Printable RepresentationPython bool()Converts a Value to BooleanPython enumerate()Returns an Enumerate ObjectPython filter()constructs iterator from elements which are truePython iter()returns iterator for an objectPython len()Returns Length of an ObjectPython max()returns largest elementPython min()returns smallest elementPython map()Applies Function and Returns a ListPython reversed()returns reversed iterator of a sequencePython slice()creates a slice object specified by range()Python sorted()returns sorted list from a given iterablePython sum()Add items of an IterablePython tuple() FunctionCreates a TuplePython zip()Returns an Iterator of Tupleslist in python
lst = list()lst = ist([iterable])lst =[]lst.append(item)lst3 = lst1 + lst2lstPython List append()Add Single Element to The ListPython List extend()Add Elements of a List to Another ListPython List insert()Inserts Element to The ListPython List remove()Removes Element from the ListPython List index()returns smallest index of element in listPython List count()returns occurrences of element in a listPython List pop()Removes Element at Given IndexPython List reverse()Reverses a ListPython List sort()sorts elements of a listPython List copy()Returns Shallow Copy of a ListPython List clear()Removes all Items from the ListPython any()Checks if any Element of an Iterable is TruePython all()returns true when all elements in iterable is truePython ascii()Returns String Containing Printable RepresentationPython bool()Converts a Value to BooleanPython enumerate()Returns an Enumerate ObjectPython filter()constructs iterator from elements which are truePython iter()returns iterator for an objectPython list() Functioncreates list in PythonPython len()Returns Length of an ObjectPython max()returns largest elementPython min()returns smallest elementPython map()Applies Function and Returns a ListPython reversed()returns reversed iterator of a sequencePython slice()creates a slice object specified by range()Python sorted()returns sorted list from a given iterablePython sum()Add items of an IterablePython zip()Returns an Iterator of Tuples