1 min read
Insertion Sort Selection Sort Merge Sort Bubble Sort quick Sort Heap Sort
What is the Heap 완전 Binary Tree 의 일종으로 우선순위 큐 를 위하여 만들어진 자료구조이다. 여러 개의 값들 중에서 최댓값 (Max Heap) 이나 최솟값 (Min Heap) 을 빠르게 찾아내도록 만들어진 자료구조이다.
Sorting Insertion Sort Selection Sort Merge Sort Bubble Sort quick Sort Heap Sort Related References.
장점 구현이 매우 간단하다. 단점 하나의 요소가 가장 왼쪽에서 가장 오른쪽으로 이동하기 위해서는 배열에서 모든 다른 요소들과 교환되어야 한다. Bubble Sort 는 원소 간 비교도 문제이지만 swap 이 빈번하게 발생하므로 비효율적이다.
Quick Sort 합병 정렬 (merge sort) 과 달리 퀵 정렬은 리스트를 비균등하게 분할한다. 분할 정복 (divide and conquer) 방법 문제를 작은 2 개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다.
분할 단계와 병합 단계로 나뉘는 divide and conquer 알고리즘 시간 복잡도: O(nlog(n)) 공간 복잡도: O(n) (병합 단계에서 사용) 코드 def mergeSort(arr, l, r): if l < r: Same as (l+r)//2, but avoids overflow for...
Insertion Sort 삽입 정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.
Selection Sort 선택 정렬은 다음과 같은 순서로 이루어진다. 주어진 리스트 중에 최소값을 찾는다. 그 값을 맨 앞에 위치한 값과 교체한다. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다. 하나의 원소만 남을 때까지 위의 과정을 반복한다.
Stack 스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조 (LIFO - Last In First Out) 으로 되어 있다.
Eclat Eclat 은 교집합을 이용한 DFS 방식이다. 그래서 Apriori 과 달리 parallel 하게 수행하는 것이 가능하다. B) Eclat 의 특징 Eclat 은 Apriori 와 비교했을 때 메모리에 모두 적재될 수 있는 적은 데이터셋에 적합하다.
Inorder Search 는 root 를 중간 단계에서 search 하는 방식이다. Traverse the left subtree Visit the root.