_12_ 정렬(Sorting)

MJ Studio
알고리즘은 미친짓이다
7 min readMay 31, 2022

정렬들의 종류와 가장 쉬운 느린 정렬부터 알아봅시다.

정렬에 대하여 알아보지만, c++의 STL의 구현과 자세한 코드레벨까지는 다루지 않습니다.

이 글의 목적은 각 언어의 내장 정렬 함수를 잘 활용하고 정렬의 시간복잡도에 대한 학습, 그리고 문제를 해결하는 데 정렬이 쓰이는 활용법들을 소개하는 것입니다.

그런 부분이 궁금하다면 다음과 같은 목차의 글들을 추천합니다.

또한 정렬에대한 전반적인 얘기를 진한님께서 잘 정리해두신 다음과 같은 글도 있습니다.

정렬(Sorting)

정렬은 데이터들을 정해진 우선순위에 맞게 재배열하는 것을 의미합니다.

보통 1차원적인 의미에서 사용되며 흔히 알려진 정렬 기준으로는 오름차순(ascending)과 내림차순(descending)이 있습니다.

물론 오름차순, 내림차순이란 개념은 크기의 대소를 비교할 수 있는 숫자같은 데이터에서 사용되는 개념이지만, 중요한 것은 어떤 데이터든 대소를 비교할 수 있는 방법만 제공될 수 있다면(두 데이터간의 우선순위를 매길 수 있다면), 정렬이 가능하다는 점입니다.

정렬은 활용이 무궁무진합니다. 어떤 데이터들이 우선순위에 맞게 정렬이 되어있냐 아니냐는 정말 중요한 성질입니다.

예를 들어, 항상 숫자값이 증가하는 순서대로 정렬이 되어있다면 특정 숫자를 볼 때, 왼쪽에 있는 숫자들은 현재 보고 있는 숫자 이하이고, 오른쪽엔 현재 보고 있는 숫자 이상이라는 것을 알 수 있죠.

물론 이건 당연한 얘기지만, 특정 문제의 경우 입력이 정렬되어 주어지느냐 아니냐에 따라서 난이도가 아예 달라지기도 하고 정렬되어 주어지지 않더라도 먼저 입력을 정렬하고 문제를 해결해야하는 경우도 부지기수입니다.

정렬의 종류

정렬은 다양한 종류가 있습니다만, 크게 세 가지로 분류할 수 있습니다.

1. 느린 정렬 O(N²)

흔히 O(N²) 정렬이라고 불리기도 합니다.

사실상 정렬이 정말 필요한 상황이라면 쓰잘데기 없습니다. 왜냐면 데이터가 10만개만 되어도 O(100,000²) 는 시간초과가 나기 딱 좋기 때문입니다.

하지만 이 기본적인 정렬들을 이해하는 것은 중요하며 특히 버블정렬 같은 경우 버블정렬의 성질을 이용해서 해결해야하는 특이한 문제들도 있지만 어려워서 다루지 않습니다.

흔한 예시로는 버블 정렬(Bubble sort), 삽입 정렬(Insertion sort), 선택 정렬(Selection sort)이 있습니다.

2. 빠른 정렬 O(NlogN)

흔히 O(NlogN) 정렬이라고 불리기도 합니다.

보통 언어에서 내장함수로 지원해주는 정렬들이 O(NlogN)을 지원하며 최적의 시간복잡도 보장을 위해 내부적으로 상황에 맞게 여러 정렬 알고리즘들을 섞어서 구현되어 있는 경우가 있습니다.

흔한 예시로는 병합 정렬(Merge sort), 퀵 정렬(Quick sort), 힙 정렬(Heap sort) 등이 있습니다.

3. 특이한 정렬

기수 정렬(Radix sort)계수 정렬(Counting sort)같이 특정한 경우에만 쓰일 수 있는 정렬들을 의미하고 보통 자료들의 대소관계를 비교하여 정렬하는 것이 아닌 특이한 방법으로(뭐 어디에 어떤 순서대로 다 넣었다 빼면 정렬이 되어있다든지) 정렬합니다.

정렬 사용법 #1. 정수 정렬하기 — 오름차순, 내림차순

내장 함수를 사용해서 풀 수 있는 가장 간단한 문제를 보겠습니다.

단순히 입력받은 정수들을 오름차순으로 출력하는 문제입니다.

C++ 코드부터 보겠습니다.

stl에 있는 std::sort 함수를 사용할 수 있습니다. 정렬하기 원하는 범위를 iterator로 각각 전달해주면 정렬이 되고, 기본 동작은 오름차순 정렬입니다.

내림차순을 정렬하려면 다음과 같이 비교 함수를 greater 를 전달해줄 수 있습니다.

Python 코드를 보겠습니다.

단순히 리스트 타입인 arr에서 sort 함수를 호출해주면 됩니다. 기본 동작은 오름차순 정렬입니다.

내림차순은 다음과 같이 sort함수에 reversedTrue로 설정해주면 됩니다.

Java 코드를 보겠습니다.

자바는 정렬이 컬렉션에 따라 조금 다른데, int[] 형으로 int 배열을 썼으므로 Arrays 에서 sort 함수를 이용해 정렬하면 됩니다.

혹은 ArrayList<T> 같은 컬렉션 인터페이스를 구현한 자료구조를 사용하려면 Collections 에서 sort 함수를 이용해 정렬하면 됩니다.

내림차순을 사용하려면 List<T> 의 함수인 sort를 사용하고(Collectionssort의 두 번째 인자에 그대로 Comparator.reverseOrder()를 넣어도 됩니다), Comparator.reverseOrder() 를 전달하면 됩니다.

정렬 사용법 #2. 아무 자료형이나 커스텀 우선순위로 정렬하기

물론 아무 자료형이나 정렬할 수 있는건 아니고 특정 자료형을 가진 두 데이터간의 우선순위를 명백히 정의할 수 있는 경우에만 사용 가능합니다.

이 경우, 다음과 같은 네 가지 성질이 성립하여야 합니다.

1. 비반사성(irreflexivity) : F(a, a)는 항상 거짓

2. 비대칭성(asymmetry) : F(a, b)가 참이라면 F(b, a)는 항상 거짓

3. 추이성(transitivity) : F(a, b)가 참이고 F(b, c)가 참이라면 F(a, c)는 항상 참

4. 비비교성의 추이성(transitivity of incomparability) : F(a, b), F(b, a)가 거짓이고 F(b, c), F(c, b)가 거짓이면 F(a, c), F(c, a)는 항상 거짓

(참고 : https://panty.run/strict-weak-ordering/)

따라서 우리는 예를 들어 정수형인 ab를 비교할 때 비교 함수를 작성해주는 과정에서 a ≤ b 가 아닌 a < b를 사용해주어야 한다는 것을 의미합니다.

a ≤ b 를 사용해버리면 ab가 같은 경우 1. 비반사성과 2. 비대칭성을 만족하지 못하기 때문입니다.

이제 문제를 풀며 사용법을 익혀봅시다.

c++의 STL에서 전달되는 비교 함수들은 인자 두 개를 받습니다.

여기서 참을 반환하면 첫 번째 인자가 더 정렬 순서에서 앞으로 갑니다.

거짓을 반환하면 반대입니다.

따라서 aby좌표를 먼저 비교하고 같지 않다면 a.second < b.second 를 반환해주고, 만약 같다면 a.first < b.firstx 좌표를 오름차순 정렬해주듯이 해주면 됩니다.

파이썬은 위와 같은 정수형 튜플같은 경우 쉽게 lambda 를 써서 정렬할 수도 있지만 좀 더 커스터마이징을 쉽게 하기 위해 functools의 cmp_to_key 를 사용해줄 수 있습니다.

이 함수는 인자로 함수를 받는데, 인자로 주는 함수는 두 인자(a, b)를 받습니다.

여기서 반환하는 값에 따라

0 : a와 b가 완전히 동일하다

음수 : a가 b보다 앞에와야 한다.

양수 : a가 b보다 뒤에와야 한다.

를 의미합니다.

다음과 같은 예시를 보시면 쉽게 아실 수 있습니다.

자바는 다음과 같습니다.

--

--