Study Log

Quick Sort Based on the divide and conquer(D&C) paradigm. Overall procedure Pivot selection: Pick an element, called a pivot, from the list. ex) For each list, select a pivot as the left-most element. Partitioning: reorder the list with the pivot. The elements less than the pivot come before the pivot. The elements greater than the pivot come after the pivot. ex) Partitino the list into two subl..

Divide & Conquer (D&C) Paradigm Breaking down a problem into two or more subproblems of the same or related type. The solutions to the subproblems are combined to be a solution to the original problem. main step Divide: Break the original problem into smaller, often identical or similar subproblems. This division continues recursively until the subproblems become simple enough to be solved direc..

Shell sort Start by sorting pairs of elements far apart from each other, then reduce the gap between elements to be compared. Generalization of insertion sort Sort every k-th elements by considering k interleaved lists. Reduce the size of k by 1. This is similar to insertion sort, but considers the gap between elements. When the gap is one, it is same as insertion sort. void IncInsertionSort(int..

Bubble Sort At the i th iteration (0 0; i--) { for (int j = 0; j list[j + 1]) { // Swap if they are in the wrong order. SWAP(list[j], list[j + 1], temp); } } } } Time complexity Best case: O(n) Worst case: O(n²) Bubble sort is stable.

Selection sort At the i-th iteration (0

Sorting Algorithms Given a set of records, the output is to the non-decreasing order(numerical order or lexicographical order) of records. The output is a permutation of the input. https://www.toptal.com/developers/sorting-algorithms Sorting Algorithms Animations www.toptal.com Sorting has been commonly used as the pre-processed method for searching and matching. Sorting is also used as the basi..

Traversal The process of visiting each node in a graph. How to visit all nodes once? Depth-first search(DFS) Breadth-first search(BFS) Depth-First Search(DFS) Keep moving until there is no more possible block. Go back the previous step and move other unvisited block. Algorithm of DFS Visit the start vertex. Visit one of unvisited vertices neighboring to the start vertex. Repeat step 2 until ther..

Priority Queue Similar to a regular queue(FIFO) The key difference is that each element has a priority An element with high priority is served before an element with low priority A priority queue possesses the following attributes: Every item has a priority. Items with higher priority are dequeued before items with lower priority. If two items have the same priority, they are dequeued based on t..