정렬(Sort)
-
요소들을 일정한 순서대로 열거하는 알고리즘
-
비교식 정렬과 분산식 정렬로 나뉜다.
-
상황에 따라 정렬의 성능이 달라질 수 있다.
비교식 정렬(Comparative Sort)
비교하고자 하는 요소 두 개를 서로 비교해서 교환하는 정렬
버블 정렬(Bubble Sort)
- 서로 인접한 두 요소를 비교하는 정렬
선택 정렬(Selection Sort)
- 선택된 요소와 가장 우선순위가 높은 요소를 비교해서 교환하는 정렬
삽입 정렬(Insertion Sort)
-
선택한 요소를 삽입할 수 있는 위치를 찾아 삽입하는 방식의 정렬
-
선택된 요소보다 크거나 작은 값을 한쪽으로 밀면서 정렬한다.
-
배열을 이용해 구현 시, 두 번째 원소부터 비교를 시작한다.
분산식 정렬(Distribute Sort)
자료를 여러 개의 부분 집합으로 분해하고, 부분 집합을 정렬해서 전체를 정렬하는 방식
주로 문제를 작은 2개의 문제로 분리하고, 더 이상 분리가 불가능 할때 합치는 분할 정복 알고리즘을 이용해 구현한다
합병 정렬(Merge Sort)
-
분할 정복 알고리즘을 이용한 정렬
-
최선의 경우와 최악의 경우 모두 O(n log n)의 시간 복잡도를 가지는 정렬이다.
-
중복된 값을 정렬할 때, 입력 순서를 유지하는 안정 정렬(Stable Sort)이다.
퀵 정렬(Quick Sort)
-
합병 정렬과 마찬가지로 분할 정복 알고리즘을 이용한 정렬
-
최선의 경우 O(n log n)의 시간 복잡도를 가지지만, 최악의 경우 O(n2)만큼 걸린다.
-
중복된 값의 입력 순서를 유지하지 않는 불안정 정렬(Unstable Sort)이다.
퀵 정렬 순서
-
배열 가운데 원소 하나를 고른다. 이 원소를 피벗(pivot) 이라고 한다.
-
피벗 앞에는 피벗보다 작은 값이, 뒤에는 피벗보다 큰 값이 오도록 배열을 둘로 나눈다.
-
나눈 배열의 첫 번째 요소들을 피벗으로 하여 1, 2 과정을 반복한다.
-
더 이상 나눌 수 없을 때, 배열을 합치면 자동으로 정렬된다.
이진 탐색(Binary Search)
정렬되어있는 리스트에서 검색 범위를 반씩 좁혀가며 탐색하는 알고리즘
-
O(log n)의 시간 복잡도를 가진다.
-
배열 혹은 이진 트리를 이용해서 구현이 가능하다.
이진 탐색 트리(Binary Search Tree)
배열로 구현한 이진 탐색에서 추가/삭제의 단점을 해소하기 위해 만들어진 트리
-
이진 트리의 왼쪽 서브 트리는 루트보다 작은 값, 오른쪽 서브 트리는 루트보다 큰 값이 위치하도록 구성한 트리
-
하위 트리또한 같은 규칙을 따른다.
-
중위 순회(inorder)를 하면 정렬된 값을 얻을 수 있다.
요소 삽입 과정
-
처음 삽입한 정점이 루트 노드가 된다.
-
그 뒤에 삽입한 정점은 루트와 비교하여 작다면 왼쪽, 크다면 오른쪽에 위치한다.
-
서브 트리에도 2번 규칙이 적용된다.
요소 삭제 과정
-
리프 노드를 삭제하는 경우
단순히 부모 노드와의 연결을 끊는다.
-
제거되는 노드가 하나의 서브 트리를 가지는 경우
제거하는 노드의 자식과 제거하는 노드의 부모를 연결한다.
-
제거되는 노드가 두 개의 서브 트리를 가지는 경우
왼쪽 서브 트리의 가장 큰 값, 혹은 오른쪽 서브 트리의 가장 작은 값과 교체한다.
문제점
-
배열을 이용해 구현 시, 요소의 추가 삭제가 일어나면 O(N)의 시간 복잡도를 가진다.
-
이진 탐색 트리는 최악의 경우 편향 트리가 될 수 있는데, 이때 탐색 시간은 O(N)이 된다.
-
이러한 문제는 AVL 트리 혹은 레드-블랙 트리로 해결이 가능하다.
