정렬 알고리즘
배열의 데이터는 인덱스를 사용하여 접근할 수 있다. 그렇다면 배열에서 원하는 값이 있는지 찾는 방법에는 무엇이 있을까?
선형탐색
가장 먼저 떠올릴 수 있는 방법이 선형탐색이다. 처음부터 끝까지 하나하나 다 찾아보는 것이다.
1
2
3
4
5
6
7
8
public static int Linear_Search(int[] arr, int target){
for (int i=0;i<arr.length;i++){
if (target == arr[i]){
return i;
}
}
return -1;
}
선형탐색의 시간복잡도는
O(n) : 가장 마지막으로 원하는 값을 찾는 경우
Ω(1) : 가장 첫번째로 원하는 값을 찾은 경우
이다.
이진탐색
주어진 배열이 정렬되어 있는 상태라면 이진탐색을 사용하는 것이 좋다. 이진탐색은 가장 먼저 배열의 가운데를 확인하고 가운데값보다 찾는 값이 작다면 가운데를 기준으로 왼쪽배열의 가운데를 확인한다. 가운데값보다 찾는 값이 크다면 가운데를 기준으로 오른쪽 배열의 가운데를 확인하는 방식으로 값을 찾는다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static int Binary_Search(int[] arr, int target){
int left=0;
int right = arr.length;
int mid;
while(left<=right){
mid = (left+right)/2;
if(arr[mid]==target){
return mid;
}
else if(arr[mid]>target){
right=mid-1;
}
else{
left=mid+1;
}
}
return -1;
}
이진탐색의 시간복잡도는
O(log n) : 탐색을 할 때마다 탐색하는 범위가 반으로 줄어든다. 이때 가장 마지막으로 값을 찾는 경우
Ω(1) : 가장 첫번째로 원하는 값을 찾은 경우
이다.
좀 더 효율적으로 값을 찾기 위해서는 배열을 정렬해야한다. 그렇다면 배열을 정렬하는 방법으로는 무엇이 있을까?
버블정렬
버블정렬은 인접한 두 값을 비교해서 위치를 바꾸는 방식으로 값을 나열한다.
10 9 8 7 : 주어진 배열
9 10 8 7
9 8 10 7
9 8 7 10
8 9 7 10
8 7 9 10
7 8 9 10
인덱스 0에서 부터 해당 값(i)과 다음 인덱스의 값을 비교하여 해당 값이 옆의 값보다 크면 옆의 값과 자리를 바꾼다. 다음 인덱스로 이동하여 이 과정을 반복한다. 자바 코드로 나타내면 다음과 같다.
1
2
3
4
5
6
7
8
9
10
11
12
public static void Buble_Sort(int[] arr){
int tmp;
for(int i=0;i<arr.length;i++){
for(int j=0;j<arr.length-i-1;j++){
if(arr[j]>arr[j+1]){
tmp=arr[j+1];
arr[j+1]=arr[j];
arr[j]=tmp;
}
}
}
}
버블정렬의 시간복잡도
O(n^2) : 내림차순으로 정렬되어 있는 경우 모든 값을 다 돌아야함.
Ω(n^2) : 정렬이 되어 있는 상태에서 버블정렬을 시도하면 모든 값을 다 확인함.
버블정렬를 개선하는 방법으로는 한번도 교환이 일어나지않았을 경우 정렬을 멈추는 것이다. 따라서 O(n)으로 알고리즘을 개선할 수 있다.
선택정렬
선택정렬은 주어진 배열에서 가장 작은 수를 맨 앞으로 옮겨 정렬하는 방식이다. 교환횟수를 최소화해주지만 최소값을 찾아야하기 떄문에 모든 수를 비교해야한다.
10 9 8 7
이 배열에서 가장 작은 값은 7이므로 가장 맨앞의 수 10과 교환한다.
7 9 8 10
정렬된 7을 제외하고 가장 작은 수(8)를 찾고 정렬을 하지않은 인덱스부터 수를 교환(9)한다.
7 8 9 10
자바 코드로 나타내면 다음과 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static void Select_Sort(int[] arr){
int min_inx, tmp;
for(int i=0;i<arr.length;i++){
min_inx=i;
for(int j=i+1;j<arr.length;j++){
if(arr[min_inx]>arr[j]){
min_inx=j;
}
}
if(arr[min_inx]!=arr[i]){
tmp=arr[min_inx];
arr[min_inx]=arr[j];
arr[j]=tmp;
}
}
}
선택정렬의 시간복잡도는
O(n^2):최소값을 찾기위해 배열을 다 돌아야함
Ω(n^2): 정렬되어 있는 배열이라도 최소값을 찾아야 함
또한, 선택정렬은 unstable하다는 특징이 있다. 예를 들어, 성적순으로 선택정렬을하고 이름순으로 배열하고 싶다고 한다면
B C A2 A1 (A < B,C)
A2 C B A1
A2 A1 B C
이런식으로 정렬이 된다. 그러나 내가 원한 배열은 A1 A2 B C 이므로 이러한 상태를 unstable하다고 한다. 여러 가지 정렬 규칙이 있거나 특정한 순서를 유지해야 하는 경우에 문제가 될 수 있다.
병합정렬
병합정렬은 원소가 하나일 때까지 반으로 나누고 정렬한 후 합치는 stable정렬방식이고 합칠때 별도의 메모리공간이 필요하다.
7 4 3 2 6 3 8 1
7 4 3 2 | 6 3 8 1
7 4 | 3 2 | 6 3 | 8 1
7 | 4 | 3 | 2 | 6 | 3 | 8 | 1
요소가 하나일 때까지 나눈 후
4 7|2 3|3 6|1 8 정렬하고 합친다
2 3 4 7|1 3 6 8
1 2 3 3 4 7 8
자바코드로 나타내면 다음과 같다
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
public static void Merge_Sort(int[] arr){
sort(arr,0,arr.length)
}
public static void sort(int[] arr,int left,int right){
if(right-left<2){
return;
}
int mid = (left+right)/2
sort(arr,left,mid)
sort(arr,mid,right)
merge(arr,left,mid,right)
}
public static void merge(int[] arr, int left, int mid, int right){
int[] tmp = new int[right-left];
int t=0, l=left, r=mid;
while(l<mid && r<rifht){
if(arr[l]<arr[r]){
tmp[t++]=arr[l++];
}
else{
tmp[t++]=arr[r++];
}
}
while(l<mid){
tmp[t++]=arr[l++];
}
while(r<mid){
tmp[t++]=arr[r++];
}
for(int i=left;i<right;i++){
arr[i]=tmp[i-left];
}
}
병합정렬의 시간복잡도
O(nlogn) : 반으로 나눌 때 O(log n), 정렬하고 병합할 때 O(n)
Ω(nlogn) : 정렬이 되어 있는 상태에서도 모든 요소를 나누고 병합함
Comments powered by Disqus.