- 장점
- 구현이 매우 간단하다.
- 단점
- 하나의 요소가 가장 왼쪽에서 가장 오른쪽으로 이동하기 위해서는 배열에서 모든 다른 요소들과 교환되어야 한다.
- Bubble Sort 는 원소 간 비교도 문제이지만 swap 이 빈번하게 발생하므로 비효율적이다.
... 삽입함으로써 정렬을 완성하는 알고리즘이다. More efficient in practice than most other simple quadratic: Selection Sort or Bubble Sort
Insertion Sort Selection Sort Merge Sort Bubble Sort quick Sort Heap Sort
삽입 정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다. More efficient in practice than most other simple quadratic: Selection Sort or Bubble...
Insertion Sort Selection Sort Merge Sort Bubble Sort quick Sort Heap Sort
Max Heap 이나 min Heap 을 구성해 정렬하는 방법 내림차순 정렬: max Heap 오름차순 정렬: min Heap 장점 Heap Sort 는 전체 자료를 정렬하는 것이 아니라 가장 큰 값 몇 개만 필요할 때 자주 사용된다. 단점 원소를 삽입할 때마다 자료 구조를 업데이트 하는 시간이 O(logn) 만큼...
합병 정렬 (merge sort) 과 달리 퀵 정렬은 리스트를 비균등하게 분할한다. 분할 정복 (divide and conquer) 방법 문제를 작은 2 개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다.
분할 단계와 병합 단계로 나뉘는 divide and conquer 알고리즘 시간 복잡도: O(nlog(n)) 공간 복잡도: O(n) (병합 단계에서 사용) 코드
선택 정렬은 다음과 같은 순서로 이루어진다.
입력 크기가 커질 때 알고리즘의 실행 시간이 어떤 비율로 늘어나는지를 나타낸 것이다. 초 단위 실행 시간은 기계와 언어에 따라 달라지므로, 대신 기본 연산이 몇 번 일어나는지를 입력 크기 n 의 함수로 센다.
완전 Binary Tree 의 일종으로 우선순위 큐 를 위하여 만들어진 자료구조이다.
배열이나 문자열 위에서 구간의 왼쪽 끝과 오른쪽 끝을 가리키는 포인터 두 개를 두고, 두 포인터를 각각 한 방향으로만 움직여 답을 찾는 방식이다. 구간이 늘었다 줄었다 하며 앞으로 나아가는 모습이 애벌레를 닮아서 붙은 이름이고, two pointers 나 sliding window 라고도 부른다.
swap out 을 위한 Page 를 선정하기 위한 알고리즘 Memory 에서 앞으로 사용할 가능성이 적은 페이지를 대상 Page 로 선정하여 Page Fault 를 줄이고, 시스템의 성능을 향상한다. 알고리즘 종류 algorithms/First In First Out 교체 알고리즘 LRU 교체 알고리즘 LFU...