정렬
정렬이란
- 내부정렬: 정렬할 모든 데이터를 하나의 배열에 저장할 수 있는 경우
- 외부정렬: 정렬할 모든 데이터가 많아 하나의 배열에 저장 못하는 경우
정렬의 핵심 = 교환, 선택, 삽입
- 시간복잡도
![enter image description here]()
- 버블정렬
- 단순선택정렬
- 단순삽입정렬
- 셀정렬
- 퀵정렬
- 병합정렬
- 힙정렬
버블정렬 (O(n^2))
끝에 있는 요소부터 시작하여 바로 옆의 값과 비교해 옆의 값이 크면 교환하는 방식.
한번의 순회가 완료되면 가장 작은 요소가 맨 왼쪽 인덱스에 저장된다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public void swap(int[] a, int i, int j)
{
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
public void bubbleSort(int[] a, int n)
{
for(int i = 0; i < n-1; i++)
{
int change = 0;
for(int j = n-1; j > i; j--)
{
if(a[j-1] > a[j])
{
swap(a, j-1, j);
change++;
}
}
if(change == 0) break;
}
}
단순선택정렬 (O(n^2))
순회하며 가장 작은 요소의 값과 정렬이 되지 않은 맨 왼쪽 인덱스의 값을 교환한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public void selectionSort(int[] a)
{
for(int i = 0; i < a.length; i++)
{
int min = i;
for(int j = i+1; j < a.length; j++)
{
if(a[j] < a[min])
{
min = j;
}
}
swap(a, i, min);
}
}
단순삽입정렬 (O(n^2))
아직 정렬되지 않은 부분의 첫 번째 요소를 정렬된 부분의 알맞은 위치에 삽입하는 방식.
[6,4,1,7] 이면 [4,6,1,7], [1,4,6,7] 과 같이 진행된다. (진한 글씨 부분이 정렬된 부분)
1
2
3
4
5
6
7
8
9
10
11
12
13
public void insertionSort(int[] a)
{
for(int i = 1; i < a.length; i++)
{
int j;
int temp = a[i];
for(j = i; j > 0 && a[j-1] > temp; j--)
{
a[j] = a[j - 1];
}
a[j] = temp;
}
}
셸 정렬 (O(n^1.5~2))
단순 삽입 정렬의 장점은 살리고 단점은 보완한 정렬 방식
- 장점 : 정렬을 마쳤거나 마친 상태에 가까우면 정렬 속도가 매우 빨라진다.
- 단점 : 삽입할 위치가 멀리 떨어져 있으면 이동해야 하는 횟수가 많아진다.
n칸 만큼 떨어진 요소를 모아 그룹을 나누어 정렬한다. n/2칸 만큼 떨어진 요소를 모아 그룹을 나누어 정렬한다. 를 반복.
정렬해야 하는 횟수는 늘지만 전체적으로는 요소 이동의 횟수가 줄어들어 비교적 효율적이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public void shellSort(int[] a)
{
for(int i = a.length / 2; i > 0; i /= 2)
{
for(int j = i; j < a.length; j++)
{
int h;
int temp = a[j];
for(h = j - i; h >= 0 && a[h] > temp; h -= i)
{
a[h + i] = a[h];
}
a[h + i] = temp;
}
}
}
퀵 정렬 (O(nlogn))
일반적으로 사용되고 있는 아주 빠른 정렬 알고리즘. 그룹을 나누는 기준을 피벗이라하고 피벗을 설정하고 피벗을 기준으로 그룹나눔을 반복하여 모든 그룹의 요소가 1개가 되면 정렬을 마친다.
ex) [5,7,1,4,6,2,3,9,8] 일 때 피벗이 6이면 6이하 그룹, 6초과 그룹으로 나눈다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public void quickSort(int[] a, int left, int right)
{
int pl = left;
int pr = right;
int pivot = a[(pl + pr) / 2];
do{
while(a[pl] < pivot) pl++;
while(a[pr] > pivot) pr--;
if(pl <= pr)
{
swap(a, pl++, pr--);
}
}while(pl <= pr); // 피벗을 기준으로 나눈다.
if(left < pr) quickSort(a, left, pr);
if(right > pl) quickSort(a, pl, right);
}
병합정렬 (O(nlogn))
나누어진 그룹을 병합하는 과정에서 정렬한다.
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
private int[] temp;
public void __mergeSort(int[] a, int left, int right)
{
if(left < right)
{
int i;
int center = (left + right) / 2;
int p = 0;
int j = 0;
int k = left;
__mergeSort(a, left, center);
__mergeSort(a, center, right);
for(i = left; i <= center; i++)
temp[p++] = a[i];
while(i <= right && j < p)
a[k++] = (temp[j] <= a[i]) ? temp[j++] : a[i++];
while(j < p)
a[k++] = temp[j++];
}
} // 재귀적으로 병합 정렬
public void mergeSort(int[] a)
{
temp = new int[a.length];
__mergeSort(a, 0, a.length - 1);
temp = null;
}
힙 정렬 (O(nlogn))
- 힙 : 부모의 값이 자식의 값보다 항상 큰 완전 이진트리
힙의 요소를 배열로 저장했을 때 아래와 같이 나타낼 수 있다.
- 부모 노드 : a[(child-1)/2]
- 왼쪽 자식 : a[parent*2 + 1]
- 오른쪽 자식 : a[parent*2 + 2]
- 힙의 루트에 있는 가장 큰 값을 꺼내 배열의 마지막 요소와 바꾼다.
- 가장 큰 값이 마지막 요소가 되면 a[0] ~ a[마지막 요소 - 1] 을 힙으로 바꾼다. 다시 이 구간에 대해 1의 과정을 반복하면 마지막 요소와 마지막 요소 - 1은 큰 값으로 정렬이 된다.
- 이 과정을 반복한다.
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
public void downHeap(int[] a, int left, int right)
{
int temp = a[left]; // 루트
int child;
int parent;
for(parent = left; parent < (right + 1) / 2; parent = child)
{
int cl = parent * 2 + 1;
int cr = cl + 1;
child = (cr <= right && a[cr] > a[cl]) ? cr : cl;
// 큰 값을 가진 노드를 자식노드에 대입
if(temp >= a[child])
break;
a[parent] = a[child];
}
a[parent] = temp;
}
public void heapSort(int[] a)
{
for(int i = (a.length-1) / 2; i >= 0; i--)
{
downHeap(a, i, a.length-1); // 트리의 아랫부분부터 힙으로 만들어간다.
}
for(int i = a.length-1; i > 0; i--)
{
swap(a, 0, i);
downHeap(a, 0 ,i-1);
}
}
** java.util.Arrays 클래스의 클래스 메서드를 이용해 퀵 정렬과 병합 정렬을 간단히 사용 가능하다.
1
2
Arrays.sort(arr);
Arrays.sort(arr, PhyscData.HEIGHT_ORDER); // 클래스 데이터의 요소를 선택하여 정렬 가능.