가장 단순한 정렬 알고리즘 중의 하나로써 이미 정렬되어 있는 서브 파일에 새로운 한 개의 레코드를 입력하여 그 순서를 삽입시킨다. 쉽게는 자신보다 앞의 레코드 값이 큰지 작은지 비교를 해서 자신의 위치를 찾아 삽입하는 정렬이다. 따라서 앞의 레코드 값과 비교해야 하기 때문에 배열 인덱스 0 부터 시작으로 생각하면 1부터 비교를 시작한다. ( arr[1] ~ arr[n-1] )
삽입을 하면 배열이 계속 밀리기 때문에 배열의 사이즈가 크면 클수록 비효율적. 시간복잡도는 O(n^2)
삽입 정렬은 안정 정렬이다. 안정 정렬이란 동일한 값에 대해 기존의 순서가 유지되는 정렬 방식 ( 버블 정렬, 삽입 정렬 )
버블 정렬의 기본 전략은 주어진 파일에서 인접한 레코드의 두 개의 키를 비교하여 그 크기에 따라 레코드의 위치를 서로 교환해 준다. 즉 첫 번째와 두 번쨰 키를 비교하여 첫 번째가 두 번째보다 크다면 위치를 교환하고 그 다음에 두 번쨰에 위치한 레코드의 키와 세 번째 키를 비교하여 전술한 과정을 수행한다. 이 과정을 맨 마지막 레코드까지 수행했을 때 가장 큰 값의 키를 갖는 레코드가 맨 마지막에 위치하게 된다. 2회전에서는 마지막 레코드는 제외하고 비교, 교환의 작업을 수행하게 된다.
이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다. 레코드의 수를 n이라 할 때 최대(n-1) 회전을 수행해야 하지만 어느 회전에서든 레코드의 위치 교환이 발생하지 않으면 주어진 파일은 완전히 오름차순으로 순서 배열이 된 셈이다.
선택 정렬은 버블 정렬과 함께 가장 많이 사용되는 정렬 방법 중의 하나이다. 선택 정렬은 버블 정렬이 순서를 바꾸는 Swap 작업을 보완하는 방식이다.
오름차순의 경우, 첫 번째 요소와 두 번째 요소를 비교하여 순서 조정, 첫 번째 요소와 세 번째 요소의 순서 조정, .... , 첫 번째 요소와 N 번째 요소의 순서 조정을 거치면서 n개의 레코드로부터 최소값을 첫 번째 위치로 놓는 것이 1단계의 결과이고, 최종적으로 (N-1)번째 레코드와 N 번째 레코드 중에서 키 값이 작은 레코드를 (N-1) 번째에 놓음으로써 수행은 완료된다.
시간 복잡도는 O(N^2)이다.
선택 정렬은 불안정 정렬이다. 불안정 정렬이란 동일한 값에 대해 기존의 순서가 유지되지 않는 정렬 방식( 선택 정렬 )
퀵 정렬 알고리즘은 다른 알고리즘에 비해 평균 수행 능력이 양호하다고 평가된다. 이것은 분할 정복 방식이고, 순환 알고리즘으로써 주어진 ㅊ파일에다 퀵 정렬 알고리즘을 적용하면 특정한 키(Pivot) 값보다 작은 값을 갖는 레코드와 큰 값을 레코드로 분리되어 한 개의 파일이 논리적으로 두 개의 서브파일로 재배열된다. 각각의 서브 파일에다 퀵 정렬 알고리즘을 적용하는 과정을 반복하면 최종으로 완전히 순서 배열된 파일이 얻어진다.
간단히 말하면 특정한 레코드값(Pivot)을 중심으로 그 왼쪽에는 피봇값보다 작은 레코드가 배열되고, 오른쪽에는 큰 레코드가 놓이게 된다.
평균적인 시간 복잡도는 O(NlogN)이다. 속도가 빠르고 추가적인 공간을 필요로 하지 않는다.
힙 정렬은 힙이라는 데이터 구조를 이용한 알고리즘이다. 힙 구조는 전 이진 트리로써 각 노드의 키 값이 자식 노드의 키 값보다 작지 않은 특징을 가지고 있다. 전 이진 트리로 힙을 구성할 때는 가장 낮은 레벨의 우측 노드부터 그의 부모 노드와 비교하여 자식 노드가 크면 부모 노드와 교환하는 작업을 수행한다.
힙은 최대 힙과 최소 힙이 있는데, 최대 힙은 자식 노드보다 부모 노드의 값이 크게 구성된 경우를 말하고 최소 힙은 반대로 자식 노드보다 부모 노드의 값이 작게 구성된 경우이다.
힙이 일단 구성된 다음, 가장 큰 값을 찾아내고 나머지 노드를 사용하여 힙을 재구성한다. 여기에서 또 두 번째로 큰 값을 찾아낸다. 이러한 작업을 반복하여 트리의 크기를 줄여가면서 수행한다. 시간복잡도는 최악, 최선, 평균 모두 O(nlogn) 이다.
힙 정렬의 특징
정렬을 수행하기 위해 n만큼의 기억 공간이 필요하다.
정렬을 수행하는 속도가 빠르다.
부모 노드의 위치는 index/2이다.
각 노드의 좌측 자식 노드는 2*index이고, 우측 자식의 노드는 2*index+1이다.
‘존 폰 노이만(John von Neumann)’이라는 사람이 제안한 방법으로써 분할 정복 알고리즘이며 O(nlogn)의 시간 복잡도를 갖는 비교 기반 정렬 알고리즘이다. 간단하게 말하면 하나의 배열을 두 개의 균등한 크기로 분할하고 분할된 부분 배열을 정렬한 다음, 두 개의 정렬된 부분 배열을 합쳐 전체가 정렬된 배열이 되게 하는 방법이다.
분할 정복(divide and conquer) 방법이란 문제를 작은 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 방식이다.
분할 정복 방법은 보통 재귀 방식을 이용하여 구현한다.
단점으로는 임시 배열이 필요하다는 점이다. 시간 복잡도는 O(n log n)이다.
합병 정렬은 다음과 같이 작동한다.
리스트의 길이가 1 이하이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는
분할(divide) : 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
정복(conquer) : 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
결합(combine) : 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. 이때 정렬 결과가 임시배열에 저장된다.
복사(copy) : 임시 배열에 저장된 결과를 원래 배열에 복사한다.
병합 정렬의 예(출처 : https://wonjayk.tistory.com/221)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
publicclass Sort {
staticint arr[]= {7,3,5,2,1,8,9,4};
publicstaticvoid main(String[] args) {
// arr = insertion_sort(arr);
// arr = bubble_sort(arr);
// arr = selection_sort(arr);
// quick_sort(arr, 0, arr.length-1);
// heapSort(arr);
mergeSort(arr, 0, arr.length-1);
for(int i=0; i<arr.length; i++) {
System.out.print(arr[i]+" ");
}
}
privatestaticvoid mergeSort(int[] arr, int m, int n) {
// TODO Auto-generated method stub
if(m<n) {
int middle=(m+n)/2;
mergeSort(arr,m,middle);
mergeSort(arr,middle+1,n);
merge(arr,m,middle,n);
}
}
privatestaticvoid merge(int[] arr, int m, int middle, int n) {
# 처음에는 입력받아서 arrayList를 사용하고 index를 조절하며 switch case 문으로 해결하려 했으나 시간초과로 문제를 풀 수 없었다. 다른 방법을 찾아보던 중 스택으로 해결할 수 있다는 글을 보고 스택으로 수정하여 풀었더니 통과하였다. 시간 제한을 신경써야 함.
데이터를 표현하는 한 방법인 트리는 정점과 선분으로 형성된 그래프의 특수한 형태이며, 임의의 두 정점 사이에 사이클을 형성하지 않는 비선형 데이터 구조이며, 주로 포인터를 사용하여 표현한다.
1. 트리
트리 구조는 정보의 항목들이 가지(Branch)로 연관되어 데이터를 구성하고 있다. 트리는 어떤 데이터를 저장하는 노드들이 루트 노드라 불리는 노드를 가장 상위로 하여 계층적으로 구성되어 있는 데이터 구조로써, 한 노드에는 그의 자식(child) 노드들이 연결되며, 자식 노드들은 또 자신의 자식을 가지는 계층 구조이며, 사이클을 허용하지 않는다. 임의 노드의 바로 상위 노드를 그 노드의 부모(Parent) 노드라고 한다.
트리는 계층적인 데이터를 표현하는 데 사용되며 여러 분야에서 매우 널리 사용되는 중요한 데이터 구조이다.
1.1 트리의 정의
트리의 정의는 다음과 같은 조건을 만족하면서 하나 이상의 노드로 구성된 유한된 집합체이다.
단 하나의 루트 노드가 존재해야 한다.
루트 노드에서 각 노드로 가지로 연결되어야 한다.
순환(Loop)를 허용하지 않는다.
루프 노드를 제외한 나머지 노드들은 n(n>=0)개의 서로 분리된 부분집합으로 나누어 진다. 임의의 각 부분집합도 트리 구조이며 이것을 서브 트리라고 한다.
트리의 구조
1.2 트리 용어
트리에서 사용되는 용어를 설명하기 위해 다음 그림을 예로 들어본다.
트리의 예
노드(Node)는 트리를 구성하는 정점(Vertex)이며, A,B,C,D,E 등을 말한다. 가지(Edge)는 노드 간의 관계를 표시하는 연결선이며, 레벨(Level)은 루트 노드의 레벨을 1로 하고, 그 다음 자식 노드는 2, 그 다음 자식 노드의 자식 노드는 3.. 으로 표시 하는 것이다.
루트 노드(Root Node)는 레벨이 가장 낮은 노드인 A가 그림에서의 루트 노드가 되며, 차수(degree)는 서브 트리의 개수로써 A의 차수는 3, B의 차수는 2, C의 차수는 1, K,L,F,G,M,I,J의 차수는 0이 된다.
깊이(depth)는 임의의 트리에서 노드가 가지는 최대 레벨이며, 앞의 그림에서는 4가 깊이가 된다. 자식(child) 노드는 어떤 노드에 연결된 다음 레벨의 노드이다. 예를 들어 A의 자식 노드는 B,C,D이며 B의 자식 노드는 E,F 이다.
부모(Parent) 노드는 어떤 노드에 연결된 상위 노드이다. 예를 들어 B의 부모 노드는 A이다. 형제(Sibling) 노드는 같은 부모 노드를 가진 노드를 말한다. 예를 들어 B,C,D 노드는 형제 노드이다.
단말 노드(Terminal Node 또는 Leaf)는 차수가 0인 노드이며, 앞의 그림에서는 K,L,F,G,M,I,J 가 해당한다. 중간 노드는 차수가 0이 아닌 노드이며, 단말 노드를 제외한 노드를 말한다.
숲(Forest)는 분리된 트리의 집합으로써 앞의 그림을 가지고 다음과 같이 표현할 수 있다.
데이터 구조의 하나로써 원소의 삽입과 삭제가 한쪽 끝에서만 일어나는 선형 리스트이다. 원소들의 삽입, 삭제가 일어나는 부분을 top라고 하며, 원소를 스택에 넣는 것을 push, 스택에서 원소를 꺼내는 것을 pop이라고 한다. 스택에서는 나중에 들어간 원소가 먼저 꺼내어지므로 후입선출(LIFO, Last-In, First Out)이라고 한다.
스택은 주로 어떤 내용을 기억시켰다가 다시 이용하고자 할 때 사용되며 컴퓨터 알고리즘에 자주 쓰이는 데이터 구조이다. 스택의 활용 예로써, 운영체제에서 인터럽트가 발생한 경우에 복귀 주소의 저장이나 산술 계산에 사용된다.
2. 큐(Queue)
데이터 구조의 하나로써 큐도 여러 데이터 항목을 일정한 순서로 입출력하기 위한 선형 데이터구조로써, 선형 리스트의 한쪽 끝에서는 삽입 동작만, 반대쪽에서는 삭제 동작만 이루어진다.
큐에는 한 방향으로 데이터 항목들이 삽입/삭제되는 선형 큐와 시작점과 끝점이 서로 연결되어 있는 환형 큐가 있다. 먼저 입력되는 데이터를 먼저 삭제하므로 선입선출(FIFO, First in First out)이라고 한다.
큐는 rear, front 노드를 이용하여 삽입, 삭제를 구현한다.
큐의 활용 예로써 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 사용한다
캐시(Cache) 구현
우선순위가 같은 작업 예약 (인쇄 대기열)
선입선출이 필요한 대기열 (은행 카운터)
프린터의 출력 처리
3. 데크(Deque : Double-ended queue)
데크는 스택과 큐를 혼합한 상태이며 비슷한 동작으로 양쪽 끝 모두에서 삽입과 삭제가 일어나도록 설계 된 데이터 구조이다. 스택의 한쪽 끝에서 삽입과 삭제가 동시에 일어날 경우 그 위치(주소)를 알려주는 포인터가 1개 필요하였듯이 데크에서는 2개의 포인터가 필요하다. 데크는 선형구조이므로 배열을 이용할 수 있다.
