정렬 알고리즘

1. 개요

정렬이란 데이터를 특정한 기준에 따라 순서대로 나열하는 것입니다.
문제 상황에 따라 다른 정렬 알고리즘을 사용합니다. (데이터의 범위가 한정되어 있을 때, 이미 데이터가 정렬 되어 있을때 등..)

2. 선택 정렬

처리되지 않은 데이터 중에서 가장 작은 데이터를 선택하여 맨 앞에 있는 데이터와 바꾸는 것을 반복합니다. 매번 현재 범위에서 가장 작은 것을 골라 맨 앞으로 보내주는 것입니다.
처리되지 않은 데이터 중 가장 작은 '0'을 7과 교환합니다.

그럼 첫번째 원소까지는 데이터 정렬이 수행된 것입니다.

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
for i in range(len(array)):
	min_index = i #i는 가장 작은 원소의 인덱스를 의미합니다.
    for j in range(i+1, len(array)): #검사된 부분 제외하고 나머지 선형탐색
    	if array[min_index] > array[j]:
        	min_index = j
    array[i], array[min_index] = array[min_index], array[i] # exchange
print(array)

#include<bits/std++.h>

using namespace std;
int n = 10;
int target[10] = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8}

int main(void){
	for (int i = 0 ; i < n; i++){
    	int min_index = i;
        for ( int j = i +1 ; j < n ; j++){
        	if (target[min_index] > target[j]){
            	min_index = j;
            }
        }
        swap(target[i], target[min_index]);
    }
    for (int i = 0 ; i < n ; i++){
    	cout<< target[i] <<' ';
    }
    return 0;}

선택 정렬의 시간 복잡도는 어떻게 될까?

• 선택 정렬은 N번만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 합니다.

  N + (N - 1) + (N - 2) + ... +2

  이를 계산하면 등차수열이므로 (N^2 + N - 2) /2 O(N^2) 입니다.

  3. 삽입 정렬

  처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입합니다.
  선택 정렬에 비해 구현 난이도가 높지만, 더욱 효율적으로 동작합니다.

임의의 데이터를 이미 정렬이 되어 있다고 판단합니다. (여기서는 첫번째 데이터) 그리고 그 다음의 데이터가 어디로 갈 지 결정합니다. 이미 정렬된 값보다 값이 작다면 왼쪽으로 들어가고, 크다면 오른쪽으로 들어가게 합니다.(올바른 위치에 삽입하는 것임)

정렬되기 이전의 모습입니다. key로 7을 정합니다.

7의 왼쪽으로 데이터 5가 들어간 모습입니다.

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
for i in range(1, len(array)):
	for j in range(i, 0, -1): #인덱스 i부터 1까지 감소하며 반복합니다.
    	if array[j] < array [j-1]:
        	array[j], array[j-1] = array[j-1], array[j] #한 칸씩 왼쪽으로 이동합니다.
        else: #자신보다 작은 데이터를 만나면, 해당 위치에서 멈춥니다.
        	break
print(array)

#inclue<bits/stdc++.h>

using namespace std;
int n = 10;
int target[10] = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};

int main(void){
	for (int i = 1; i < n ; i++){
    	for (int j = 1; j > 0 ; j--){
        	if (target[j] < target[j-1]){
            	swap(target[j], target[j-1]);
            }
            else break;
        }
    }
    for (int i = 0 ; i < n ; i++) {
    	cout << target[i] << ' ';
    }
    return 0;
}

삽입 정렬의 시간 복잡도는 어떻게 될까?

• 시간 복잡도는 O(N^2)입니다. 반복문이 두 번 중첩되기 때문에 (중첩적)
• 삽입 정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작.
• 최선의 경우 O(N)의 시간 복잡도를 가집니다. (자기 자리 확인하는 과정만 필요)

4. 퀵 정렬

기준 데이터를 설정하고, 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법입니다.
일반적인 상황에서 가장 많이 사용됩니다.
병합 정렬과 더불어 프로그래밍 언어의 정렬의 라이브러리의 근간이 되는 알고리즘입니다.
가장 기본적으로는 첫 번째 데이터를 기준 데이터 (Pivot)으로 설정합니다.

첫 번째 원소를 pivot으로 설정합니다. 왼쪽에서부터는 기준 데이터보다 큰 값을 선택하고, 오른쪽에서부터는 기준 데이터보다 작은 값을 선택해야 합니다. 그때까지 계속 자리를 이동합니다. 그러한 값이 선택된다면 두 데이터의 위치를 서로 변경합니다.

위와 같은 방법으로 계속해서 진행합니다. 위치가 엇갈리는 경우 피벗과 작은 데이터의 위치를 서로 변경해줍니다.

그러면 pivot을 중심으로 왼쪽에는 pivot값보다 작은 데이터, 오른쪽에는 pivot값보다 큰 데이터들이 분할됩니다.

이후 나눠진 부분들을 하나의 배열로 생각하여 퀵 정렬을 똑같이 수행됩니다.
재귀적으로 수행하며 수행을 하면서 그 범위가 점점 좁아집니다.

퀵 정렬의 시간 복잡도는 어떻게 될까?

• 데이터가 절반씩 이상적으로 줄어든다고 생각하면 너비(데이터의 개수)는 N이고, 높이는 logN이기 때문에 평균적으로 O(NlogN)의 시간 복잡도를 가집니다.
• 피벗 값을 어떻게 설정하느냐에 따라 편향된 결과가 나타날 수 있습니다. 최악의 경우 O(N^2)의 시간 복잡도를 가집니다.
• 모두 정렬된 배열에서 첫번째 원소를 피벗으로 삼을 때, 퀵 정렬을 수행하면 모든 데이터를 돌아오게 됩니다. 피벗 값 자기 자신의 위치에서 자기 자신의 위치로 이동하기 때문에 매번 분할이 이루어질때 오른쪽의 정렬만 남게 되고 선형 탐색이 그때마다 일어나서 O(N^2)의 시간 복잡도를 가지는 것입니다.

array =[5, 7, 9, 0, 3, 1, 6, 2, 4, 8]
def quick_sort(array, start, end):
	if start >= end: #원소가 1개인 경우 종료됩니다.
    	return
    pivot = start #일반적으로 pivot은 시작 값으로 설정
    left = start + 1
    right = end
    while (left <= right):
    	#피벗보다 큰 데이터를 찾을 때까지 반복합니다. 
    	while(left <= end and array[left] <= array[pivot]):
        	left += 1
        #피벗보다 작은 데이터를 찾을 때까지 반복
        while(right > start and array[right] >= array[pivot]):
        	right -= 1
        if(left > right) : #엇갈렸다면 작은 데이터와, 피벗을 교체합니다.
        	array[right], array[pivot] = array[pivot], array[right]
        else : #엇갈리지 않았다면 작은 데이터와 큰 데이터 교체합니다.
        	array[left], array[right] = array[right], array[left]
    #분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
    quick_sort(array, start, right - 1)
    quick_sort(array, right + 1, end)
quick_sort(array, 0, len(array - 1)
print(array)

파이썬은 아래와 같이 코드를 더욱 간결하게 짤 수 있다.

array = [5,7,9,0,3,1,6,2,4,8]

def quick_sort(array):
	#리스트가 하나 이하의 원소만을 담고 있다면 종료
    if len(array) <= 1:
    	return array
    pivot = array[0] #피벗은 첫 번째 원소
    tail = array[1:] #피벗을 제외한 리스트
    left_side = [ x for x in tail if x<=pivot] #분할된 왼쪽 부분
    right_side = [ x for x in tail if x > pivot] #분할된 오른쪽 부분
    
    #분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행, 전체 리스트 반환
    return quick_sort(left_side) + [pivot] + quick_sort(right_side)
print(quick_sort(array))

다음은 C++ 코드이다

#include<bits/stdc++.h>

using namespace std;
int n = 10;
int target[10] ={7, 5, 9, 0, 3, 1, 6, 2, 4, 8}

void quickSort(int* target, int start, int end){
	if(start >= end) return;
    int pivot = start;
    int left = start + 1;
    int right = end;
    while (left <= right){
    	while(left <= end && target[left] <= target[pivot]) left++;
        while(right > start && target[right] >= target[pivot]) right--;
        if (left > right) swap(target[pivot], target[right]);
        else swap(target[left], target[right]);
        }
    quickSort(target, start, right - 1);
    quickSort(target, right + 1, end);
}
int main(void){
	quickSort(target, 0 , n-1);
    for(int i = 0 ; i < n ; i++) cout<<target[i] <<' ';
    return 0;
}

5. 계수 정렬

특정한 조건이 부합할 때만 사용할 수 있지만, 매우 빠르게 동작하는정렬 알고리즘입니다.
계수 정렬은 데이터의 크기 범위가 제한되어 정수 형태로 표현 가능할 때 사용합니다.
데이터의 개수가 N, 데이터(양수) 중 최댓값이 K일 때 최악의 경우에도 수행시간 O(N+K)를 보장합니다.

• 정렬할 데이터 : 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2
  
  가장 작은 데이터부터 가장 큰 데이터까지의 범위가 모두 담길 수 있도록 리스트를 초기화합니다. 인덱스가 정렬할 데이터의 값이고, 각 인덱스의 값이 몇 번 등장하였는지 확인해야 합니다.

정렬할 데이터를 하나하나 돌면서 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시키면 됩니다.
결과를 확인할 때에는 리스트의 첫 번째 데이터부터 하나씩 그 값만큼 반복하며 인덱스를 출력하면 됩니다.

array = []

count = [0] * (max(array) + 1) # 0부터 9까지 존재하기 때문

for i in range(len(array):
	count[array[i]] +=1 # 각 데이터에 해당하는 인덱스의 값 증가
for i in range(len(count)): #리스트에 정렬된 내용 확인합니다.
	for j in range((count[i]):
    	print(i, end=' ') #띄어쓰기 구분

퀵 정렬의 시간 복잡도는 어떻게 될까?

for i in range(len(count)): #원소 중에서 가장 큰 K 확인
	for j in range((count[i]): #그 인덱스에 써져 있는 만큼만 반복
    	print(i, end=' ') #띄어쓰기 구분

• 시간 복잡도와 정렬 복잡도 모두 O(N+k)입니다.
• 계수 정렬은 심각한 비효율성을 초래할 수 있습니다. 0과 999,999의 2개만 존재하는 리스트를 정렬한다면 비효율적입니다.
• 계수 정렬은 동일한 값을 가지는 데이터가 여러 개 등장할 때 효과적입니다.

정렬 알고리즘 총 정리

+) 참고 : python의 기본 라이브러리 sort는 병합 정렬을 기반으로 하는 하이브리드 정렬 방식을 사용합니다. 그래서 최악의 경우에도 O(Nlogn)의 시간이 걸립니다.

6. 대표 문제 풀이

1. 두 배열의 원소 교체 : 문제 설명

유진이는 두 개의 배열 A와 B를 가지고 있습니다. 두 배열은 N개의 원소로 구성되어 있으며, 배열의 원소는 모두 자연수입니다.
유진이는 최대 K번의 바꿔치기 연산을 수행할 수 있는데 바꿔치기 연산이란 배열 A에 있는 원소 하나와 배열 B에 있는 원소 하나를 골라서 두 원소를 서로 바꾸는 것을 말합니다.
유진이의 최종 목표는 배열 A의 모든 원소의 합이 최대가 되도록 하는 것입니다.
N, K 그리고 배열 A와 B의 정보가 주어졌을 때, 최대 K번의 바꿔치기 연산을 수행하여 만들 수 있는 배열 A의 모든 원소의 합의 최댓값을 출력해 주세요.

• 시간 제한 : 2초, 메모리는 128MB
• 입력 조건 : 첫번째 줄에 N, K 가 공백을 기준으로 구분되어 입력된다. (1 <= N <= 100,000, 0<= K <= N) 두번째 줄에 배열 A의 원소들이 공백을 기준으로 구분되어 입력된다. 모든 원소는 10,000,000보다 작은 자연수. 세 번째 줄에 배열 B의 원소들이 공백을 기준으로 구분되어 입력된다.
• 출력 조건 : 최대 K번의 바꿔치기 연산을 수행하여 만들 수 있는 배열 A의 모든 원소의 합의 최댓값
  -핵심 아이디어 : 매번 배열 A에서 가장 작은 원소를 골라서, 배열 B에서 가장 큰 원소와 교체합니다. -> 배열 A에 대해서는 오름차순 정리, 배열 B에 대해서는 내림차순 정렬합니다.
• 이 문제에서는 두 배열의 원소가 최대 100,000개까지 입력될 수 있으니 최악의 경우를 O(NlogN)을 보장하는 정렬 알고리즘을 이용해야 합니다.

2. 코드

n, k = map(int, input().split()) #N과 K 입력받음
a = list(map(int, input().split()) #배열 A의 모든 원소 입력 받기
b = list(map(int, input().split()) #배열 B의 모든 원소 입력 받기

a.sort() #배열 A는 오름차순 정렬
b.sort() (reverse=True) #배열 B는 내림차순 정렬 수행

for i in range(k):
	# A의 원소가 B의 원소보다 작은 경우
    if a[i] < b[i]:
    	a[i], b[i] = b[i], a[i]
    else: #A의 원소가 B의 원소보다 크거나 같을 때, 반복문 탈출(더이상 검사할 가치가X)
    	break
print(sum(a)) #배열 A의 모든 원소의 합을 출력