ALGORITHM

Quicksort(A, left, right)
if |A| = 0 then return //A is empty 
end if
split = Partition(A, left, right) 
Quicksort(A, left, split − 1)
Quicksort(A, split + 1, right)

Initial call: Quicksort(A, 1, n)

Partition(A, left, right)
	pivot = A[right]
	split = left − 1

	for j=left to right−1 do
		if A[j] ≤ pivot then 
			swap(A[j], A[split + 1]) 
			split = split + 1
		end if 
	end for

	swap(pivot, A[split + 1])        //place pivot after A[split] (why?) 
	return split + 1                 //the final position of pivot

# Python3 implementation of QuickSort
# Function to find the partition position
def partition(array, low, high):

	# Choose the rightmost element as pivot
	pivot = array[high]

	# Pointer for greater element
	i = low - 1

	# Traverse through all elements
	# compare each element with pivot
	for j in range(low, high):
		if array[j] <= pivot:
			# If element smaller than pivot is found
			# swap it with the greater element pointed by i
			i = i + 1

			# Swapping element at i with element at j
			(array[i], array[j]) = (array[j], array[i])

	# Swap the pivot element with
	# e greater element specified by i
	(array[i + 1], array[high]) = (array[high], array[i + 1])

	# Return the position from where partition is done
	return i + 1

# Function to perform quicksort


def quick_sort(array, low, high):
	if low < high:

		# Find pivot element such that
		# element smaller than pivot are on the left
		# element greater than pivot are on the right
		pi = partition(array, low, high)

		# Recursive call on the left of pivot
		quick_sort(array, low, pi - 1)

		# Recursive call on the right of pivot
		quick_sort(array, pi + 1, high)

step 1: start

step 2: declare array and left, right, mid variable

step 3: perform merge function.
    if left == right
        return
    mid= (left+right)/2
    mergesort(array, left, mid)
    mergesort(array, mid+1, right)
    merge(array, left, mid, right)

step 4: Stop

merge (A, left, right, mid)
	L = A[left, mid]
	R = A[mid + 1, right]
	Maintain two pointers p_L, p_R, initialized to point to the first
	elements of L, R, respectively
	while both lists are nonempty do
		Let x, y be the elements pointed to by pL, pR
		Compare x, y and append the smaller to the output
		Advance the pointer in the list with the smaller of x, y
	end while
	Append the remainder of the non-empty list to the output.

Remark: the output is stored directly in A[left, right], thus the
subarray A[left, right] is sorted after merge(A, left, right, mid).

# Python program for implementation of MergeSort
def mergeSort(arr):
	if len(arr) > 1:

		# Finding the mid of the array
		mid = len(arr)//2

		# Dividing the array elements
		L = arr[:mid]

		# into 2 halves
		R = arr[mid:]

		# Sorting the first half
		mergeSort(L)

		# Sorting the second half
		mergeSort(R)

		i = j = k = 0

		# Copy data to temp arrays L[] and R[]
		while i < len(L) and j < len(R):
			if L[i] <= R[j]:
				arr[k] = L[i]
				i += 1
			else:
				arr[k] = R[j]
				j += 1
			k += 1

		# Checking if any element was left
		while i < len(L):
			arr[k] = L[i]
			i += 1
			k += 1

		while j < len(R):
			arr[k] = R[j]
			j += 1
			k += 1

# Python3 Program for recursive binary search.

# Returns index of x in arr if present, else -1

def binarySearch(arr, l, r, x):

	# Check base case
	if r >= l:

		mid = l + (r - l) // 2

		# If element is present at the middle itself
		if arr[mid] == x:
			return mid

		# If element is smaller than mid, then it
		# can only be present in left subarray
		elif arr[mid] > x:
			return binarySearch(arr, l, mid-1, x)

		# Else the element can only be present
		# in right subarray
		else:
			return binarySearch(arr, mid + 1, r, x)

	else:
		# Element is not present in the array
		return -1

def binarySearch(v, To_Find):
	lo = 0
	hi = len(v) - 1

	# This below check covers all cases, so need to check
	# for mid=lo-(hi-lo)/2
	while hi - lo > 1:
		mid = (hi + lo) // 2
		if v[mid] < To_Find:
			lo = mid + 1
		else:
			hi = mid

	if v[lo] == To_Find:
		print("Found At Index", lo)
	elif v[hi] == To_Find:
		print("Found At Index", hi)
	else:
		print("Not Found")

该算法通过重复从数组的未排序部分中取出一个元素并将其插入数组已排序部分中的正确位置来对项目数组进行排序。

Input: Array A
n = length(A)
1. 外部 for loop 从索引“1”开始并运行“n-1”次迭代，其中“n”是数组的长度。
2. 内部 while loop从外部 for 循环的当前索引 i 开始，
	 并将每个元素与其左邻居进行比较。 如果一个元素小于它的左邻居，则交换元素。
3. 内部 while loop 继续将元素向左移动，直到它小于其左侧的元素停止while loop。
4. 内部 while loop 完成后，当前索引"j"处的元素即为数组已排序部分中的正确位置。
5. 外层的 for 循环继续遍历数组，直到所有元素都在正确的位置并且数组已完全排序。

insertionSort(A: list of sortable items)
   n = length(A)
   for i = 1 to n - 1 do
       j = i
       while j > 0 and A[j-1] > A[j] do
           swap(A[j], A[j-1])
           j = j - 1
       end while
   end for
end algorithm

BFS(G = (V, E), s ∈ V )
	# discovered array表示一个vertex是否已被访问过
	# 如果被访问过则记为1，没有则记为0
	array discovered[V] initialized all vertices to 0 ---- O(n)

	# The dist array记录了source到每一个vertex的最短路径
	# 除了source自身，所有vertex的初始路径都为无穷大
	array dist[V] initialized to infinity array ---- O(n)

	# The parent array记录了每一个vertex的parent
	parent[V] initialized to NIL ---- O(n)

	# q记录正在被处理或者当前被访问的vertices
	queue q ---- O(1)

	# Initialize with source ---- O(1)
	discovered[s] = 1
	dist[s] = 0
	parent[s] = NIL

	# 因为source是第一个visited的vertex, 将当前要处理的vertex s加入queue
	enqueue(q, s) ---- O(1)

	# 当当前需要处理的queue不为空时
	while size(q)>0 do
	# 取出第一个vertex 'u'并检索所有从'u'延伸出的edges(u, v)
	u =dequeue(q)
		# 对于每一个与'u'相连的vertex 'v'
		for (u, v) ∈ E do
		# 如果'v'还未被访问过，即discovered[v] == 0
			if discovered[v] == 0 then 
				# 则标记'v'为已访问过，即discovered[v] == 1
				discovered[v] = 1
				# 对于unweighted graph，source到'v'的距离 = source到'u'的距离 + 1
				dist[v] = dist[u] + 1
				# 更新当前vertex 'v'的parent为'u'
				parent[v] = u
				# 把'v'添加进q作为下一个layer要检索的vertex
				enqueue(q, v)
				# 如果vertex'v'已被访问过，则进入下一个for loop检索未被访问的'v'
			end if 
		end for
	end while

# Python3 Program to print BFS traversal
# from a given source vertex. BFS(int s)
# traverses vertices reachable from s.
from collections import defaultdict

# This class represents a directed graph
# using adjacency list representation


class Graph:

	# Constructor
	def __init__(self):

		# default dictionary to store graph
		self.graph = defaultdict(list)

	# function to add an edge to graph
	def addEdge(self, u, v):
		self.graph[u].append(v)

	# Function to print a BFS of graph
	def BFS(self, s):

		# Mark all the vertices as not visited
		visited = [False] * (max(self.graph) + 1)

		# Create a queue for BFS
		queue = []

		# Mark the source node as
		# visited and enqueue it
		queue.append(s)
		visited[s] = True

		while queue:

			# Dequeue a vertex from
			# queue and print it
			s = queue.pop(0)
			print(s, end=" ")

			# Get all adjacent vertices of the
			# dequeued vertex s. If a adjacent
			# has not been visited, then mark it
			# visited and enqueue it
			for i in self.graph[s]:
				if visited[i] == False:
					queue.append(i)
					visited[i] = True

• 1. A natural way to solve 2-colorability(bipartite-ness)
  • If a graph contains an odd-length cycle, then it is not 2-colorable.

  bipartite(G = (V,E))
  	1. Start BFS from any vertex; color it red.
  	2. Color white all nodes in the first layer L1 of the BFS tree.
  	If there is an edge between two nodes in L1, output no and stop.
  	3. Otherwise, continue from layer L1, coloring red the vertices
  	in even layers and white in odd layers.
  	4. If BFS terminates and all nodes in V have been explored 
  	(hence 2-colored), output yes.

• 2. 找到所有的SCC

  AllConnectedComponents(G = (V, E))
  	1. Start with an arbitrary node s; run BFS(G, s) and output
  	the resulting BFS tree as one connected component.
  	2. Continue with any node u that has not been visited by
  	BFS(G, s); run BFS from u and output the resulting BFS
  	tree as one connected component.
  	3. Repeat until all nodes in V have been visited.

# array explored来记录一个vertex是否已被访问
DFS(G = (V, E)) 
	# Initialize the global variable time to 0
	time = 0
	# 对于每一个V中的vertex，标记每一个vertex的初始状态为未被访问
	for u ∈ V do
		explored[u] = 0 
	end for
	
	# 对于每一个V中的vertex u
	for u ∈ V do
		# 如果'u'尚未被访问，则call检索function search(u)
		if explored[u] == 0 then 
			Search(u) 
		end if
	end for

Search(u) 
	previsit(u)
	#更改'u'的标记为已被访问
	explored[u] = 1 
	# 对于每一个与'u'相连的vertex 'v'
	for (u, v) ∈ E do
		# 如果'v'未被访问，则call search(v)
		if explored[v] == 0 then 
			Search(v)
		end if 
	end for
	postvisit(u)

# start(u) is the time when u is pushed in the stack
# finish(u) is the time when u is popped from the stack

previsit(u)
	time += 1
	start(u) = time
	push(stack, u)

postvisit(u)
	time += 1
	finish(u) = time
	pop(stack, u)

# Python3 program to print DFS traversal
# from a given graph
from collections import defaultdict

# This class represents a directed graph using
# adjacency list representation


class Graph:

	# Constructor
	def __init__(self):

		# default dictionary to store graph
		self.graph = defaultdict(list)

	# function to add an edge to graph
	def addEdge(self, u, v):
		self.graph[u].append(v)

	# A function used by DFS
	def DFSUtil(self, v, visited):

		# Mark the current node as visited
		# and print it
		visited.add(v)
		print(v, end=' ')

		# Recur for all the vertices
		# adjacent to this vertex
		for neighbour in self.graph[v]:
			if neighbour not in visited:
				self.DFSUtil(neighbour, visited)

	# The function to do DFS traversal. It uses
	# recursive DFSUtil()
	def DFS(self, v):

		# Create a set to store visited vertices
		visited = set()

		# Call the recursive helper function
		# to print DFS traversal
		self.DFSUtil(v, visited)

Dijkstra-v1(G = (V, E, w), s ∈ V) 

	Initialize(G, s)

	# Initialize the set S with only source vertex s.
	S = {s}

	# This loop continues until S contains all vertices in the graph.
	while S != V do
		# This loop iterates over all vertices x 
		# that are not in S and have at least one edge from S.
		For every x ∈ V − S with at least one edge from S compute
			d(x) = min {dist[u] + w_{ux}}
					u ∈ S,(u,x) ∈ E
		Select v such that d(v) = min d(x)
														x ∈ V−S
		S = S ∪ {v} 
		dist[v] = d(v) 
		prev[v] = u
	end while

# This function initializes the distances and predecessors of all vertices in the graph. 
# It sets the distance of the source vertex s to 0 and the distance of all other vertices to infinity.
Initialize(G, s) 
	for v ∈ V do
		dist[v] = ∞
		prev[v] = NIL 
	end for
	dist[s] = 0

def preorderTraversal(root):
    if root != None:
        # Visit the root node
        print(root.val)
        # Recursively traverse the left subtree
        preorderTraversal(root.left)
        # Recursively traverse the right subtree
        preorderTraversal(root.right)

def inorderTraversal(root):
    if root != None:
        # Recursively traverse the left subtree
        inorderTraversal(root.left)
        # Visit the root node
        print(root.val)
        # Recursively traverse the right subtree
        inorderTraversal(root.right)

def postorderTraversal(root):
    if root != None:
        # Recursively traverse the left subtree
        postorderTraversal(root.left)
        # Recursively traverse the right subtree
        postorderTraversal(root.right)
        # Visit the root node
        print(root.val)