[알고리즘] 정렬 알고리즘 개념 총정리(선택 정렬/삽입 정렬/퀵 정렬/계수 정렬)

정렬 알고리즘은 이진탐색의 전처리 과정이기도 하다.

 

정렬 알고리즘의 종류

 

- 선택 정렬

- 삽입 정렬

- 퀵 정렬

- 계수 정렬

 

[선택 정렬]

 

데이터가 무작위로 여러개 있을 때, 가장 작은 데이터를 선택하는 가장 원시적인 방법

무작위로 나열된 데이터 N개가 있을 때, 선택 정렬은 가장 작은 데이터를 맨 앞으로 보내는 행위를 N-1번 반복하면 정렬이 완료된다.

 

/*선택 정렬*/
array = [7, 5, 9, 0, 3, 1, 6, 2, 4]

for i in range(len(array)):
	min_index = i
    for j in range(i+1, len(array)):
    	if array[j] < array[min_index]:
        	min_index = j
   array[i], array[min_index] = array[min_index], array[i] #스와프
   
print(array)
/*
결과
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
로 오름차순 정렬
*/

위의 선택정렬 코드 중 인상깊은 부분은 스와프 부분이다.

보통 C언어에서 스와프를 할 땐 temp 변수를 만들어 아래와 같이 스와프를 해주었다.

 

/* 스와프 C언어 구현 */
int a = 1;
int b = 2;
int temp;  //스와프를 위한 변수 생성

//a와 b의 값을 스와프
temp = a;
a= b;
b= temp;

 

하지만 파이썬의 경우 간단하게 리스트의 원소값을 스와프할 수 있다. 

 

선택 정렬은 N-1번의 '작은 데이터를 앞으로 보내는 행위'를 수행해야 한다. 이를 위한 연산 횟수는 N + (N-1) + (N-2) + ... = N*(N+1)/2번을 수행한다.

즉 선택 정렬의 시간 복잡도는 O(N^2)이다. 수학적으로 계산해서 구할 수도 있지만 선택정렬 구현 코드를 보면 2중 For문이 사용되었기 때문이기도 하다.

 

*선택 정렬은 파이썬의 기본 정렬 라이브러리를 포함하여 뒤에 나올 다른 정렬 알고리즘에 비해 시간적으로 비효율적이지만, 특정 리스트에서 가장 작은 데이터를 찾는 일이 코딩테스트에서는 많으므로 개념과 소스코드는 알아둘 필요 있다.

 

[삽입 정렬]

삽입정렬은 특정한 데이터를 적절한 위치에 '삽입'한다는 의미에서 삽입정렬이라고 부른다. 필요할 때만 위치를 바꾸므로 데이터가 거의 정렬된 상태일 때 효율적이다. 

 

삽입정렬의 경우 두번째부터 시작하며, 정렬이 이루어진 원소들은 항상 오름차순을 유지하고 있다. 그렇기에 삽입할 적절한 위치를 찾을 때 삽입될 데이터보다 작은 데이터를 만나면 그 위치에서 멈추고 삽입하면 된다.

 

/*삽입 정렬*/
array = [7, 5, 9, 0, 3, 1, 6, 2, 4]

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)

/*
결과로 
오름차순 정렬된 array값 출력
*/

 

위 문법 중 for문이 살짝 생소했다. range의 매개변수는 range(start, end, step)으로 세 번째 매개변수는 step이다. step 자리에 -1이 있는 것은 1씩 감소하며 반복하겠다는 의미이다.

 

삽입 정렬의 시간 복잡도는 O(N^2)이다. 실제 수행시간을 측정해보면 선택 정렬과 비슷하다. 하지만 만약 주어진 데이터가 '거의 정렬된 상태'일 경우 선택 정렬보다 삽입 정렬이 훨씬 빠르게 동작하다. Best Case의 경우 O(N)의 시간 복잡도를 가진다. 

보통은 삽입 정렬이 비효율적이지만 거의 정렬된 데이터에서는 어떤 정렬 알고리즘보다도 삽입 정렬이 강력하다. 그러므로 거의 정렬된 데이터가 입력으로 들어오면 삽입 정렬을 이용하는 것이 좋다. 

 

[퀵 정렬]

퀵 정렬은 여태까지 다룬 정렬 알고리즘 중 가장 많이 사용되는 알고리즘으로 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾼 후 리스트를 반으로 나누는 방식으로 동작한다.

 

여기서 기준이 되는 데이터를 '피벗(pivot)'이라고 한다. 퀵 정렬을 수행하기 전에는 피벗을 어떻게 설정할 것인지 미리 명시해야 한다. 피벗을 설정한 뒤 리스트를 분할하는 방법에 따라 퀵 정렬을 여러 방식으로 구분한다. 가장 대표적인 분할 방식은 호어 분할(Hoare Partition) 방식이다.

 

[호어 분할 방식]

리스트에서 첫 번째 데이터를 피벗으로 설정. 피벗을 설정 뒤 왼쪽에서부터 피벗보다 큰 데이터를 찾고 오른쪽에서부터 피벗보다 작은 데이터를 찾는다. 그 다음 작은 데이터와 큰 데이터의 위치를 서로 교환해준다. 이런 과정을 반복하면 피벗에 대해 정렬이 수행된다. 그러다 왼쪽에서부터 찾는 값과 오른쪽에서부터 찾는 값의 위치가 서로 엇갈릴 때 '작은 데이터'와 '피벗'의 위치를 바꿔준다. 그 후 피벗을 기준으로 왼쪽 리스트(전부 피벗보다 작음)와 오른쪽 리스트(전부 피벗보다 큼)를 분할하여 앞의 과정을 다시 각 리스트에 대해 수행해준다. 

 

퀵 정렬에서는 이처럼 피벗을 설정 후 정렬을 수행한 뒤, 피벗을 기준으로 왼쪽 오른쪽 리스트에서 다시 각각 정렬을 수행한다. 그리하여 퀵 정렬은 재귀함수 형태로 구현하면 간결해진다. 재귀함수의 종료 조건은 현재 리스트의 데이터 개수가 1개일 경우이다. 

 

 

/* 퀵 정렬 */
array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]

def quick_sort(array, start, end):
	if start >= end: #원소가 1개인 경우 종료
    	return
    pivot = start # 피벗은 첫 번째 원소
    left = start + 1
    right = end
    while left <= right:
    	# 피벗보다 큰 데이터를 찾을 때까지 반복
        while left <= end and array[pivot] <= array[left]:
        	left = left + 1
        # 피벗보다 작은 데이터를 찾을 때까지 반복
        while right > start and array[pivot] > array[right]:
        	right = right + 1
        if left > right : # 엇갈렸을 경우
        	array[right], array[pivot] = array[pivot], array[right] # 작은 데이터와 피벗 교체
        else: # 엇갈리지 않았을 경우
        	array[right], array[left] = array[left], array[right] # 작은 데이터와 큰 데이터 교체
        # 분할 이후 왼쪽 리스트와 오른쪽 리스트에 각각 정렬 수행
        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: # 리스트가 1개 이하의 원소일 경우 종료
    	return array
    pivot = array[0] # 피벗은 첫 번째 원소
    tail = array[1:] # 피벗을 제외한 리스트
    
    left_side = [x for in tail if x <= pivot] # 피벗보다 작은 데이터 -> 왼쪽으로 분할
    right_side = [x for in tail if x > pivot] # 피벗보다 큰 데이터 -> 오른쪽으로 분할
    
    # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 퀵 정렬 수행하고 전체 리스트 반환
    
    return quick_sort(left_side) + [pivot] + quick_sort(right_side)
    
print(quick_sort(array))

 

앞에서 다룬 선택 정렬과 삽입 정렬의 시간 복잡도는 O(N^2)이다. 선택 정렬과 삽입 정렬은 Worst Case에도 시간 복잡도는 O(N^2)을 보장하고, 삽입 정렬의 경우 Best Case(데이터가 잘 정렬된 경우)에는 O(N)의 시간 복잡도를 가진다.

 

퀵 정렬의 경우 평균 시간 복잡도는 O(NlogN)이다. 앞에서 다룬 두 정렬 알고리즘에 비해 빠른 편이다. 하지만 Worst Case의 경우 퀵정렬의 시간 복잡도는 O(N^2)이다. 데이터가 무작위일 경우에는 퀵 정렬이 빠르게 동작할 확률이 높지만, 만약 데이터가 이미 정렬되어 있는 경우에는 매우 느리게 동작한다.(가장 맨 왼쪽을 피벗으로 삼기 떄문에) 하지만 파이썬의 경우 기본 정렬 라이브러리를 이용하면 O(NlogN)을 보장해주기 때문에 크게 걱정하지 않아도 된다.

 

[계수 정렬]

계수 정렬 알고리즘은 특정 조건에 맞을 때만 사용할 수 있지만 그 조건에 부합하면 매우 빠른 정렬 알고리즘이다. 

여기서 말하는 특정 조건은 '데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때'로 무한한 범위를 가질 수 있는 실수형 데이터같은 경우엔 계수 정렬을 사용하기 어렵다. 또한 가장 큰 데이터와 가장 작은 데이터가 일반적으로 1,000,000 이상 차이 나지 않을 때 효과적으로 사용할 수 있다.

 

계수정렬이 이런 특징을 갖는 이유는 계수 정렬은 모든 범위를 담을 수 있는 크기의 리스트를 선언해야 하기 때문이다. 또한 계수 정렬은 앞에 다룬 정렬 알고리즘과 같이 데이터의 값을 직접 비교해가며 위치를 바꾸는 알고리즘이 아니다. 

 

/* 계수 정렬 */

# 모든 원소의 값이 0보다 크거나 같고 정수형태
array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]

count = [0] * (max(array)+1) 

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=' ') # 띄어쓰기를 구분으로 등장한 횟수만큼 인덱스 출력
        
        
        
/* 실행 결과

0 0 1 1 2 2 3 4 5 5 6 7 8 9 9

*/

 

계수 정렬의 시간 복잡도는 모든 데이터가 양의 정수인 상황에서 데이터의 개수가 N, 데이터의 최대값 크기 K일 때 O(N+K)이다. 

하지만 계수 정렬은 (데이터의 최댓값 - 최솟값 + 1) 크기만한 리스트를 생성해야 하므로 공간 복잡도 측면에서는 심각한 비효율성을 초래할 수 있다. 계수 정렬의 공간복잡도는 O(N+K)이다.

 

즉 정리하면 계수 정렬은 동일한 값을 가지는 데이터가 여러개 등장할 때 (e.g. 기말고사 성적 - 80점을 맞은 학생이 여러명일 수 있음) 효과적으로 사용할 수 있으며 항상 사용할 수 있는 것은 아니다. 그렇기에 일반적으로 데이터의 특성을 파악하기 어려우면 퀵 정렬을 이용하는 것이 유리하다.  

 

 

 

[파이썬의 정렬 라이브러리]

 

위에서 언급한 정렬 알고리즘 외에도 다양한 알고리즘이 존재한다. 알고리즘 문제를 풀 때 앞서 다룬 것처럼 직접 코드를 구현하여 작성할 수도 있지만 미리 만들어진 라이브러리를 이용하는 것이 더 효과적인 경우가 많다. 파이썬은 기본 정렬 라이브러리인 sorted() 함수를 제공한다. sorted() 함수는 병합 정렬을 기반으로 만들어졌다. (퀵 정렬을 기반으로 만들어진 것도 있으며 최악의 경우에 O(NlogN)의 시간 복잡도를 보장하도록 구현되어 있음)병합 정렬은 퀵 정렬과 동작 방식이 유사하지만 최악의 경우 O(N^2)의 시간 복잡도를 가졌던 퀵 정렬과 달리 병합 정렬은 최악의 상황에도 O(NlogN)의 시간 복잡도를 보장하는 특징이 있다.

 

/* 파이썬에서 제공하는 정렬 라이브러리 */

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

# 방법 1
result = sorted(array)

# 방법 2
array.sort()

 

 

코딩 테스트에서 정렬 알고리즘이 사용되는 경우를 일반적으로 3가지 문제 유형으로 나타낼 수 있다.

 

1. 정렬 라이브러리 폴 수 있는 문제 - 단순히 정렬 기법을 알고 있는지 물어보는 문제로 기본 정렬 라이브러리의 사용 방법을 숙지하고 있으면 어렵지 않게 풀 수 있다.

 

2. 정렬 알고리즘의 원리에 대해 물어보는 문제 - 선택 정렬, 삽입 정렬, 퀵 정렬 등의 원리를 알고 있어야 문제를 풀 수 있다.

 

3. 더 빠른 정렬이 필요한 문제 - 퀵 정렬 기반으로 풀 수 없으며 계수 정렬 등의 다른 정렬 알고리즘을 이용하거나 문제에서 기존에 알려진 알고리즘의 구조적인 개선을 거쳐야 풀 수 있다.