[07강] 정렬 알고리즘

---

안녕하세요 Gliver 입니다.

이번 글에서는 정렬 알고리즘에 대해 알아보겠습니다.

 

목차

1. 정렬 알고리즘
2. 정렬 알고리즘 종류
3. 실제 문제에서 정렬 알고리즘

 

 

1. 정렬 알고리즘

정렬 알고리즘(Sorting Algorithm)은 어떤 기준에 대해 원소들을 정렬하는 알고리즘입니다.

여기서 "어떤 기준" 이라는 것은 오름차순, 내림차순 등을 의미함.

 

기본적으로 프로그래밍 언어에서 지원하는 sort() 함수는 오름차순을 기준으로 구현돼 있고,

내림차순으로 하려면 sort() 함수 입력 부분에 less<>()를 넣어주면 됩니다. (C++ 기준)

자세한 사용법은 구글에 "내림차순 sort" 라고 검색하면 됨.

 

오름차순, 내림차순 말고 사용자가 원하는 기준에 맞게 정렬을 하고 싶다면,

compare 함수를 만들어서 sort() 함수 입력 부분에 넣으시면 됩니다. (C++ 기준)

이에 대한 내용은 구글에 "compare 함수" 라고 검색하면 됨.

 

 

 

2. 정렬 알고리즘 종류

효율적인 정렬 알고리즘(퀵 정렬, 병합 정렬)이 이미 프로그래밍 언어 내에 함수로 존재하기 때문에,

정렬 알고리즘의 종류에 대해서는 간단하게만 짚고 넘어가겠습니다.

 

대표적인 정렬의 종류는

선택 정렬, 삽입 정렬, 버블 정렬, 병합 정렬, 퀵 정렬 등이 있고,

이에 대해 간략하게 정리하면 다음과 같습니다.

 

[선택 정렬]

추가적인 공간 복잡도: O(1)

시간 복잡도: O(N²)

 

[삽입 정렬]

추가적인 공간 복잡도: O(N)

시간 복잡도: O(N²)

 

[버블 정렬]

추가적인 공간 복잡도: O(1)

시간 복잡도: O(N²)

 

[병합 정렬]

추가적인 공간 복잡도: O(N)

시간 복잡도: O(N logN)

 

[퀵 정렬]

추가적인 공간 복잡도: 필요 없음

시간 복잡도: O(N logN)

퀵 정렬의 경우, 최악의 시간 복잡도는 O(N²) 이지만 평균적으로 가장 효율적인 알고리즘임.

 

추가적으로 계수 정렬(Counting Sort) 을 자세히 알아보겠습니다.

[계수 정렬]

계수 정렬은 원소가 N개 존재하고 배열의 모든 원소가 0 부터 k 범위의 정수이면,

O(N+k) 시간 복잡도로 정렬을 할 수 있다.

k ≤ N 인 경우에 시간 복잡도는 O(N) 으로 표현 가능함.

 

계수 정렬 알고리즘은 크기가 k인 배열(count 배열)을 만들고,

정렬되지 않은 원소가 N개 들어있는 배열(list 배열)을 탐색하며

원소들의 개수를 세서 count 배열에 저장하면 됩니다.

 

다음은 계수 정렬을 이용하여 정렬하고 결과를 출력하는 코드입니다.

list 배열은 원소가 N(10) 개 들어있고, 모든 원소가 0 부터 k(7) 범위의 정수인 경우임.

 

 

 

위 코드에서 정렬을 하기 전, 정렬을 한 후, 출력을 한 후 에서의 count 배열의 상태는 다음과 같습니다.

 

[정렬을 하기 전]

count 배열

index	0	1	2	3	4	5	6	7
value	0	0	0	0	0	0	0	0

 

[정렬을 한 후]

count 배열

index	0	1	2	3	4	5	6	7
value	0	2	1	1	2	1	2	1

 

[출력을 한 후]

count 배열

index	0	1	2	3	4	5	6	7
value	0	0	0	0	0	0	0	0

 

계수 정렬은 배열의 원소를 직접 비교하는 대신에 다른 정보를 이용하는 알고리즘으로

시간 복잡도는 O(N+k), 공간 복잡도도 O(N+k)입니다.

배열의 원소를 직접 비교하여 정렬하는 알고리즘의 경우 가장 빠른 시간 복잡도는 O(N logN) 임.

 

따라서, 원소의 범위를 나타내는 k가 원소의 개수인 N에 비해 작은 경우에,

시간 복잡도는 O(N), 공간 복잡도는 O(N)으로 나타낼 수 있습니다.

 

계수 정렬(Counting Sort)에 대해 자세하게 설명한 이유는

원소들의 특징을 파악하고 그 특징에 맞는 새로운 자료형을 만들어서 처리하는 과정이

실제 문제에서 자주 쓰이기 때문입니다.

계수 정렬은 원소들의 빈도수라는 특징을 파악하고, 빈도수를 저장하는 배열을 새롭게 만들어서 처리한 것임.

 

 

 

3. 실제 문제에서 정렬 알고리즘

실제 문제에서 정렬 알고리즘은 정렬을 해야 할 때 쓰면 됩니다.

 

정렬 알고리즘은 실제 문제에서 굉장히 중요합니다.

왜냐하면, 단독으로도 많이 쓰이고 보조적으로도 많이 쓰이기 때문입니다.

보조적으로 쓰일 때, 정렬만 했는데 문제가 쉬워지는 경우가 많음.

 

정렬 알고리즘이 쓰이는 용도에 따라

다음과 같이 2가지로 나누어 설명드리겠습니다.

 

ㆍ 핵심 알고리즘

ㆍ 보조적인 알고리즘

[핵심 알고리즘]

문제에서 정렬 알고리즘이 핵심 알고리즘으로 쓰이는 경우입니다.

 

따라서, 간단한 사고과정을 통해 문제를 이해하고

정렬을 하면 문제가 해결됩니다.

 

[관련 문제]

백준 : 수 정렬하기 (2750번)

백준 : 좌표 정렬하기 (11650번)

백준 : 보물 (1026번)

[보조적인 알고리즘]

문제에서 정렬 알고리즘이 보조적인 알고리즘으로 쓰이는 경우입니다.

 

보조적으로 정렬이 쓰이는 경우는 난이도가 꽤 있는 편입니다.

따라서, 정렬을 자세히 이해할 필요가 있습니다.

 

정렬은 어떤 기준에 대해 원소들을 나열하는 것이고,

따라서 원소들을 나열할 자료형은 순서라는 개념이 존재하는 선형 구조여야 합니다.

리스트의 경우에 index가 작을수록 앞, 클수록 뒤라는 순서라는 개념이 존재하므로 선형 구조에 속하지만,

그래프의 경우는 노드(원소) 간의 순서라는 개념이 존재하지 않으므로 비선형 구조에 속함.

 

따라서, 제가 추천드리는 방식은

문제가 선형 구조로 표현이 되면 정렬의 사용을 고려하는 것입니다.

선형 구조로 표현이 안 되면,
정렬을 사용할 수 없으니 그 문제는 정렬을 사용하는 문제가 아님.

 

선형 구조로 표현이 되면 정렬을 사용할 수 있지만,

문제의 조건에 따라 기존의 배열의 순서를 건드리면 안 되는 경우가 있기 때문에

문제의 조건을 보고 배열의 순서가 바뀌어도 상관없으면 정렬을 사용합시다.

 

정리하자면, 정렬을 할 수 있는지 파악하고 정렬을 할 수 있으면 해 보는 것입니다.

 

물론, 정렬을 한다고 해서 문제가 바로 풀리는 것은 아닙니다.

하지만, 보통의 경우에 정렬을 함으로써 문제의 핵심 아이디어를 더 잘 파악할 수 있습니다.

 

[관련 문제]

백준 : 도서관 (1461번)

백준 : 전화번호 목록 (5052번)

 

 

실제 문제에서 정렬 알고리즘의 자세한 내용은 정렬의 이해 글을 참고하시기 바랍니다.

정렬의 이해 글은 추후에 작성하여 올리겠습니다.

 

 

 

 

---

궁금한 점이나 코멘트는 댓글로 남겨주세요!

 

• 알고리즘 공부법 : https://gliver.tistory.com/6
• 알고리즘 목차 : https://gliver.tistory.com/7