[Algorithm] 정렬(Sort)

정렬 (sorting)이란 , 데이터를 특정한 기준에 따라 순서대로 나열하는 것을 말한다. 

데이터의 개수가 적을 때, 많을 때, 데이터의 범위가 특정 범위로 한정되어 있을때, 거의 정렬되어 있을 때,,, 등

과 같은 문제 상황에 따라 적절한 정렬 알고리즘이 공식처럼 사용된다.

1-1. 선택 정렬(Selection Sort)

처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복한다.

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

 

1-2. 선택 정렬 시간복잡도

구현 방식에 따라 사소한 오차는 있지만, 전체 연산 횟수는 다음과 같다. 

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

이는 (N^2+ N-2)/2로 표현 할 수 있는데, 빅오 표기법에 따라서 O(N^2)라고 작성한다. 

 

2-1. 버블 정렬(Bubble Sort)

옆에 있는 값과 비교하여 더 작은 값을 반복적으로 앞으로 보내는 정렬 방법을 말한다. 

각 사이클 마다 가장 큰 값이 맨 뒤로 보내지게 된다. 

버블 정렬은 정렬 알고리즘 중에서 구현은 가장 쉬우나, 가장 비효율적인 알고리즘이다. 

 

2-2. 버블 정렬 시간복잡도

컴퓨터 내부적인 연산이 가장 비효율적으로 일어나게 되어 실제 수행시간이 가장 느린 안좋은 알고리즘으로 불린다. 

버블 정렬의 시간 복잡도는 O(N^2)이다.

 

 

3-1. 삽입 정렬 (Insection Sort)

처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입한다. 

선택 정렬에 비해 구현 난이도가 높은 편이지만, 일반적으로 더 효율적으로 동작한다. 

 

3-2. 삽입 정렬 시간복잡도

삽입 정렬의 시간 복잡도는 O(n^2)이며, 선택 정렬과 마찬가지로 반복문이 두 번 중첩되어 사용된다. 

삽입 정렬은 현재 리스트가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다. 

이미 정렬되어 있는 상태에서 다시 삽입 정렬을 수행하면 최선의 경우  O(N)의 시간 복잡도를 가진다. 

 

4-1. 퀵 정렬 (Quick Sort)

기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법이다.

일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나이다. 

병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘이다. 

가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(Pivot)로 설정한다. 

 

4-2. 퀵 정렬 시간 복잡도 

퀵 정렬은 평균의 경우 O(NlogN) 의 시간 복잡도를 가진다. 

하지만 최악의 경우 O(N^2)의 시간 복잡도를 가진다. (Pivot 값에 따라 편향된 분할이 발생할 수 있음)

첫 번째 원소를 피벗으로 삼을 때, 이미 정렬된 배열에 대해서 퀵 정렬을 수행하면 편향된 분할이 발생한다.

 

 5-1 . 병합 정렬(Merge Sort)

퀵정렬과 마찬가지로 대표적인 분할정복 방법을 채택한 알고리즘이다. 

병합 정렬은 일단, 반으로 나누고 합치는 순간에 정렬을 수행한다. 

 

5-2. 병합 정렬 시간 복잡도 

결과적으로는 퀵 정렬과 동일하게  O(NlogN) 의 시간복잡도를 가지지만, 

병합 정렬은 정확히 반절씩 나눈다는 점에서 최악의 경우에도  O(NlogN)을 보장한다. 

 

6-1. 계수 정렬 (Counting Sort)

 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작하는 정렬 알고리즘이다. 

계수 정렬은 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용이 가능하다. 

데이터의 개수가 N, 데이터(양수) 중 최댓값이 K일 때, 최악의 경우에도 수행 시간 O(N+K)를 보장한다. 

1. 가장 작은 데이터부터 가장 큰 데이터까지의 범위가 모두 담길 수 있도록 리스트를 생성한다.
2. 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시킨다( 데이터 '7' 일 때, 인덱스 7의 count값을 1 증가).
3. 결과적으로 최종 리스트에는 각 데이터가 몇 번씩 등장했는지 그 횟수가 기록된다. 
4. 리스트의 첫번째 데이터부터 하나씩 그 값만큼 반복하여 인덱스를 출력해 준다.

6-2. 계수 정렬의 복잡도 분석

계수 정렬의 시간 복잡도와 공간 복잡도는 모두 O(N+K)이다. 

계수정렬은 때에 따라서 심각한 비효율성을 초래할 수 있다(데이터가 0 과 999,999 개로 단 2개만 존재하는 경우 2개밖에 없는데도 불구하고 1,000,000개의 인덱스를 만들어야 한다).

계수정렬은 동일한 값을 가지는 데이터가 여러개 등장할 때 효과적으로 사용할 수 있다.

 

5. 정렬 알고리즘 비교

대부분의 프로그래밍언어에서 지원하는 표준 정렬 라이브러리는 최악의 경우에도 O(NlogN)을 보장(sort())한다.

정렬 알고리즘	평균 시간 복잡도	공간 복잡도	특징
선택 정렬	O(N^2)	O(N)	아이디어가 매우 간단하다.
삽입 정렬	O(N^2)	O(N)	데이터가 거의 정렬되어 있을때는 가장 빠르다.
퀵 정렬	O(NlogN)	O(N)	대부분의 경우에 가장 적합하며, 충분히 빠르다.
계수 정렬	O(N+K)	O(N+K)	데이터의 크기가 한정되어 있는 경우에만 사용이 가능하지만 매우 빠르게 동작한다.