[알고리즘] 선택, 삽입, 퀵, 계수 정렬 (Selection, Insertion, Quick, Count sort)

• 정렬이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것이다.
• 선택 정렬은 매번 가장 작은 것을 '선택'하여 앞으로 보내면서 정렬하는 알고리즘이다.
• 선택 정렬의 시간 복잡도는 O(N²)이다.
• 파이썬 기본 정렬 라이브러리의 수행 시간이 상당히 빠르다.
• 삽입 정렬은 특정한 데이터를 적절한 위치에 '삽입'하며 정렬하는 알고리즘이다.
• 삽입 정렬의 시간 복잡도는 O(N²)인데 리스트의 데이터가 거의 정렬되어 있는 상태라면 최선의 경우 O(N)의 시간 복잡도를 가진다. 따라서 거의 정렬되어 있는 상태의 데이터라면 다른 알고리즘보다 삽입 정렬을 이용하는 것이 유리하다.
• 퀵 정렬은 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작한다.
• 퀵 정렬은 평균적으로 시간 복잡도가 O(logN)이지만 최악의 경우 시간 복잡도는 O(N²)이다.
• 계수 정렬은 특정한 값을 가지는 데이터의 개수를 '카운트'하는 방법이다.
• 문제에서 별도의 요구가 없다면 단순히 정렬해야 하는 상황에서는 기본 정렬 라이브러리를 사용하고, 데이터의 범위가 한정되어 있으며 더 빠르게 동작해야 할 때는 계수 정렬을 사용하자.

---

정렬 알고리즘 개요

정렬이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다. 정렬 알고리즘은 이진 탐색의 전처리 과정이기도 하니 제대로 알고 넘어가야 한다. 정렬 알고리즘은 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬 등 굉장히 다양하다.

선택 정렬

데이터가 무작위로 여러 개 있을 때, 이 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복하는 방법은 가장 원시적인 방법으로 매번 '가장 작은 것을 선택'한다는 의미에서 선택 정렬 알고리즘이라고 한다.

 

가장 작은 것을 선택해서 앞으로 보내는 과정을 반복해서 수행하다 보면, 전체 데이터의 정렬이 이루어진다.

선택 정렬의 시간 복잡도

선택 정렬은 N - 1 번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 한다. 또한 매번 가장 작은 수를 찾기 위해서 비교 연산이 필요하다. 구현 방식에 따라서 사소한 오차는 있을 수 있지만 O(N²)의 시간 복잡도를 가진다.

 

선택 정렬을 이용하는 경우 데이터의 수가 10,000개 이상이면 정렬 속도가 급격히 느려진다. 또한 파이썬에 내장된 기본 정렬 라이브러리는 내부적으로 C 언어 기반이며, 다양한 최적화 테크닉이 포함되어 더욱 빠르게 동작한다.

 

선택 정렬은 기본 라이브러리를 포함해 뒤에서 다룰 알고리즘과 비교했을 때 매우 비효율적이지만 특정한 리스트에서 가장 작은 데이터를 찾는 일이 코딩 테스트에서 잦으므로 선택 정렬 소스코드 형태에 익숙해질 필요가 있다.

삽입 정렬

삽입 정렬은 선택 정렬처럼 동작 원리를 직관적으로 이해하기 쉬운 알고리즘이다. 물론 삽입 정렬은 선택 정렬에 비해 구현 난도가 높은 편이지만 선택 정렬에 비해 실행 시간 측면에서 더 효율적인 알고리즘으로 잘 알려져 있다. 특히 삽입 정렬은 필요할 때만 위치를 바꾸므로 '데이터가 거의 정렬되어 있을 때' 훨씬 효율적이다.

 

삽입 정렬은 특정한 데이터를 적절한 위치에 '삽입'한다는 의미에서 삽입 정렬이라고 부른다. 삽입 정렬은 특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정한다. 정렬되어 있는 데이터 리스트에서 적절한 위치를 찾은 뒤에, 그 위치에 삽입된다는 점이 특징이다. 삽입 정렬은 두 번째 데이터부터 시작한다. 왜냐하면 첫 번째 데이터는 그 자체로 정렬되어 있다고 판단하기 때문이다. 삽입 정렬에서는 특정한 데이터가 삽입될 위치를 선정할 때, 삽입될 데이터보다 작은 데이터를 만나면 그 위치에서 멈추면 된다.

삽입 정렬의 시간 복잡도

삽입 정렬의 시간 복잡도는 O(N²)인데, 선택 정렬과 마찬가지로 반목문이 2번 중첩되어 사용되었다. 실제로 수행 시간을 테스트해보면 앞서 다루었던 선택 정렬과 흡사한 시간이 소요되는 것을 알 수 있다. 여기서 중요한 점은 삽입 정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다는 점이다. 최선의 경우 O(N)의 시간 복잡도를 가진다.

 

퀵 정렬 알고리즘과 비교했을 때, 보통은 삽입 정렬이 비효율적이나 정렬이 거의 되어 있는 상황에서는 퀵 정렬 알고리즘보다 더 강력하다. 따라서 거의 정렬되어 있는 상태로 입력이 주어지는 문제라면 퀵 정렬 등의 다른 정렬 알고리즘을 이용하는 것보다 삽입 정렬을 이용하는 것이 정답 확률을 높일 수 있다.

퀵 정렬

퀵 정렬은 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작한다.

 

퀵 정렬에는 피벗이 사용된다. 큰 숫자와 작은 숫자를 교환할 때, 교환하기 위한 '기준'을 바로 피벗이라고 표현한다. 피벗을 설정하고 리스트를 분할하는 방법에 따라서 여러 가지 방식으로 퀵 정렬을 구분하는데, 가장 대표적인 분할 방식인 호어 분할 방식으로 설명하겠다.

 

리스트에서 첫 번째 데이터를 피벗으로 정한 뒤에 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다. 그다음 큰 데이터와 작은 데이터의 위치를 서로 교환해준다. 이러한 과정을 반복하면 '피벗'에 대하여 정렬이 수행된다.

퀵 정렬의 시간 복잡도

퀵 정렬의 평균 시간 복잡도는 O(logN)이다. 앞서 다루었던 두 정렬 알고리즘에 비해 매우 빠른 편이다.

 

다만 평균적으로 시간 복잡도가 O(logN)이지만 최악의 경우 시간 복잡도는 O(N²)이다. 데이터가 무작위로 입력되는 경우 퀵 정렬은 빠르게 동작할 확률이 높다. 하지만 리스트의 가장 왼쪽 데이터를 피벗으로 삼을 때, '이미 데이터가 정렬되어 있는 경우'에는 매우 느리게 동작한다.

계수 정렬

계수 정렬 알고리즘은 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘이다. 다만, 계수 정렬은 '데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때'만 사용할 수 있다.

 

계수 정렬은 앞서 다루었던 3가지 정렬 알고리즘처럼 직접 데이터의 값을 비교한 뒤에 위치를 변경하며 정렬하는 방식(비교 기반의 정렬 알고리즘)이 아니다.

 

계수 정렬은 먼저 가장 큰 데이터와 가장 작은 데이터의 범위가 모두 담길 수 있도록 하나의 리스트를 생성한다. 그다음 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시키면 계수 정렬이 완료된다.

계수 정렬의 시간 복잡도

모든 데이터가 양의 정수인 상황에서 데이터의 개수를 N, 데이터 중 최댓값의 크기를 K라고 할 때, 계수 정렬의 시간 복잡도는 O(N+K)이다. 계수 정렬은 앞에서부터 데이터를 하나씩 확인하면서 리스트에서 적절한 인덱스의 값을 1씩 증가시킬 뿐만 아니라, 추후에 리스트의 각 인덱스에 해당하는 값들을 확인할 때 데이터 중 최댓값의 크기만큼 반복을 수행해야 하기 때문이다.

계수 정렬의 공간 복잡도

계수 정렬은 때에 따라서 심각한 비효율성을 초래할 수 있다. 따라서 항상 사용할 수 있는 정렬 알고리즘이 아니며, 동일한 값을 가지는 데이터가 여러 개 등장할 때 적합하다. 다시 말해 계수 정렬은 데이터의 크기가 한정되어 있고, 데이터의 크기가 많이 중복되어 있을수록 유리하며 항상 사용할 수는 없다.

파이썬의 정렬 라이브러리

파이썬은 기본 정렬 라이브러리인 sorted() 함수를 제공한다. sorted() 함수는 리스트, 딕셔너리 자료형 등을 입력받아서 정렬된 결과를 출력한다. 집합 자료형이나 딕셔너리 자료형을 입력받아도 반환되는 결과는 리스트 자료형이다.

 

리스트 객체의 내장 함수인 sort()를 이용하면 리스트 변수가 하나 있을 때 내부 원소를 바로 정렬할 수 있다. 이를 이용하면 별도의 정렬된 리스트가 반환되지 않고 내부 원소가 바로 정렬된다.

 

또한 sorted()나 sort()를 이용할 때에는 key 매개변수를 입력으로 받아 정렬 기준을 설정할 수 있다.

정렬 라이브러리의 시간 복잡도

정렬 라이브러리는 항상 최악의 경우에도 시간 복잡도 O(NlogN)을 보장한다. 정렬 라이브러리는 이미 잘 작성된 함수이므로 우리가 직접 퀵 정렬을 구현할 때보다 더욱더 효과적이다. 문제에서 별도의 요구가 없다면 단순히 정렬해야 하는 상황에서는 기본 정렬 라이브러리를 사용하고, 데이터의 범위가 한정되어 있으며 더 빠르게 동작해야 할 때는 계수 정렬을 사용하자.