Study Log

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..

Graph A collection of nodes and arcs to represent a structure Objects: A finite set of nodes (or vertices ,points) Relationship: A finite set of arcs (or edges, links) Formally, a graph is denoted by G = (V,E). V: a set of vertices E: a set of edges, a set of 2-elements of V In general, a graph may have parallel edgesand self loops. But, Simple graph don't have parallel edges and self loops. Ass..

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..

List A linear collection of storing elements of the same types. May have duplicate elements Implemented as either an array or a linked list. Operations InitList: Make a list empty. IsEmpty: Check whether the list is empty. IsFull: Check whether the list is full. Insertion: Insert an item at the specific position. InsertFirst: Insert an item at the first position. InsertLast: Insert an item at th..

큐(Queue) 입구와 출구가 따로 있는 통로 형태 A collection of elements that are inserted and removed according to the first-in first-out(FIFO) Principle. 가장 먼저 추가된 요소가 가장 먼저 제거됩니다. 모든 삽입(insertion)은 큐의 뒷부분(rear)에서 이루어집니다. 모든 제거(deletion)은 큐의 앞부분(front)에서 이루어집니다. 용어(Terminology): Front: The front of queue, where deletions take place or the position of the first item. Rear: The rear of queue, where insertions take..

스택(stack) 데이터를 쌓아놓은 더미. A collection of elements that are inserted and removed according to the last-in first-out(LIFO) principle. 마지막으로 들어온 요소가 가장 먼저 제거됩니다. Input과 Output은 stack의 가장 맨 위에서만 이루어집니다. 용어(Terminology): Top: The top of stack (default = -1) Push: Insert an item on the top. Pop: Remove the item on the top. 작동(Operation): InitStack: Make stack empty. IsFull: Check whether stack is full...