[알고리즘 이론] 정렬 알고리즘

알고리즘에는 다양한 정렬 방법이 있다. 필자는 매번 다양한 정렬 방법을 잊어 구글링을 한다.

이번 기회를 통하여 완벽하기 숙지할 예정이다. 

 

정렬 알고리즘

 

1) 버블 정렬 (Bubble sort)

버블 정렬은 O(n^2) 시간에 동작하는 간단한 정렬 알고리즘이다. 이 알고리즘은 n번의 라운드가 진행되고, 매 라운드마다 배열의 원소를 한 번씩 탐색한다. 연속된 두 원소의 순서가 잘못되었을 경우 이를 맞바꾼다.

 

구현

for(int i=0;i<n;i++){
	for(int j=0; j<n-1;j++){
    	if(arr[j] > arrp[j+1]) swap(arr[j],arr[j+1]);
    
    }
}

 

버블 정렬의 첫 라운드가 끝나면 가장 큰 원소가 올바른 위치(맨 마지막)에 위치하게 된다. K번째 라운드가 끝나면 큰 원소 K개가 올바른 위치에 정렬이된다.

 

예시)

 

초기 배열

14

2

4

8

1라운드 =  1개 원소 올바른 위치

2

14

4

8

2

4

14

8

2

4

8

14

2라운드

2

4

8

14

3라운드

2

4

8

14

4라운드

2

4

8

14

 

2) 병합 정렬 (merge sort)

병합 정렬은 재귀를 이용한다. 시간 복잡도는 O(n log n)이다.

arr[a...b]가 있을 경우, 

만일 a=b라면 아무 것도 하지 않는다. 부분 배열이 하나의 원소로 이루어졌을 경우, 이미 정렬이 되었기 때문이다.

가운데 원소의 위치를 k=(a+b)/2의 하한 값으로 계산한다.

그 후 , 재귀적으로 부분 배열 arr[a..k]를 정렬하고 arr[k+1...b]를 정렬한다.

이후 두개의 정렬된 배열을 병합하여, 정렬된 부분 배열 arr[a...b]를 만든다.

 

즉, 8개의 원소로 이루어진 배열이 있을 경우, 4개의 원소의 배열 2개로 나눈다. 그리고 함수를 재귀적으로 호출하여 두 부분 배열을 각각 정렬한다. 이후 두 부분 배열을 병합한다.

 

이 배열은 부분 배열의 크기를 절반으로 줄여나가기 때문에 효율적이다. 

 

 

3) 정렬을 이용한 문제 풀이

스윕 라인 알고리즘

정렬된 순서대로 처리되는 이벤트의 집합으로 문제를 모델링하는 방법이다. 예를 들어, 어떤 날 손님들이 한 음식점을 언제 방문했고 언제 떠났는지에 대한 정보를 모두 알고 있다고 해보자. 문제는 음식점에 동시에 존재했던 손님의 최대값을 구하는 것이다.

 

먼저, 손님의 입장과 퇴장시간을 저장하고, 시간순으로 정렬하여 살펴본다. 동시에 존재하는 손님의 수를 저장하는 cnt변수 역시 필요하다. 만일 손님이 입장하면 cnt를 증가시킨다. 그리고 손님이 퇴장했을 경우 cnt를 감소는 방법을 통해 구현할 수 있다.