선택정렬
최소 값을 선택해서 이동한다
버블정렬
0 부터 i - 1 까지, 두 쌍의 값을 비교하여, 왼쪽 값이 크면 서로 위치를 바꾼다.
삽입정렬
a 배열의 0 에서 i-1 사이에서 value 보다 큰 값들을 뒤로 한 칸씩 이동하고, 그 값들 앞에 value를 넣는다
병합정렬
start, end의 중간 지점 계산하고 중간 지점을 기준으로 앞부분과 뒷부분을 정렬한 뒤에 병합한다.
시간복잡도는 O(nlogn). 공간복잡도는 병합할 배열과 동일한 크기의 임시 배열을 생성하기 때문에 O(n)
퀵정렬
임의의 값을 기준으로, 기준값보다 작은 값들은 배열의 앞부분으로 이동하고, 기준값보다 큰 값들은 배열의 뒷부분으로 이동하는 알고리즘.
시간복잡도는 평균 O(nlogn), 최악은 O(n^2) 공간복잡도는 O(1)
병합정렬 vs 퀵정렬
병합정렬의 언제나 시간복잡도는 O(nlogn)이고 공간복잡도는 O(n)이다.
퀵정렬의 시간복잡도는 평균 O(nlogn)이지만 최악은 O(n^2)이며 공간복잡도는 언제나 O(1)이다.
힙정렬
다음 성질을 만족하는 이진 트리(binary tree)를 힙(heap)이라고 부른다.
- 맨 아래 계층은 자식이 없고,
- 맨 아래 계층과 그 바로 위 계층을 제외한 노드는 자식이 두 개이다.
- 맨 아래 계층은 왼쪽부터 꽉 채워져 있다.
- 노드의 값은 자식 노드들의 값보다 시간복잡도는 O(nlogn)이다.