[이것이코딩테스트다] chap06 정렬 - 이론

정렬 - 데이터를 특정한 기준에 따라서 순서대로 나열하는 것

---

 

선택 정렬

 

가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정. 즉 '가장 작은 것을 선택'한다는 의미에서 선택 정렬(Selection Sort)

위와 같이 바꿀 데이터를 제외하고 뒤에 있는 데이터 중에서 가장 작은 하나를 골라, 바꾼 데이터와 교환하는 형식이다.

 

위와 같이 현재 값을 min_index로 초기화하고, 그 뒤 값들과 비교해가며 min_index값보다 작으면 교환해주는 형태이다.

시간복잡도는 N-1번만큼 가장 작은 수를 찾아 맨 앞으로 보낸다. 또한 매번 가장 작은 수를 찾기 위해 비교 연산을 수행하는데, n + (n-1) + (n-2) + ... + 2로 볼 수 있다. 따라서 N X (N+1) / 2번의 연산을 수행하고, 이를 빅오 표기법으로 O(N^2)로 표현할 수 있다.

 

---

삽입 정렬(Insertion Sort)

 

'데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입하면 어떨까?'로 시작하여 선택 정렬보다 시간적으로 더 효율적이다. 특히 필요할 때만 위치를 바꾸기 때문에 배열이 정렬되어있을 때 훨씬 효율적이다.

위 그림처럼 첫 번째 위치는 정렬되어 있다고 판단하고 다음 값을 앞의 값들과 비교하여 적절한 위치에 삽입하는 형식이다. 9를 5,7과 비교했을 때 7보다 크기 때문에 그 자리 그대로 정렬하는 형태이다.

그림과 같이 값을 비교하여 연산을 수행하고 앞의 값이 더 크면 스왑, 아니면 그 자리에서 멈춘다.

시간복잡도는 N^2으로 반복문이 2번 중첩되어 사용되었다. 여기서 삽입 정렬을 특히 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다.

---

퀵 정렬

 

'기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸면 어떨까"로 시작했다. 기준을 설정한 다음 큰 수와 작은 수를 교환한 후, 리스트를 반으로 나누는 방식으로 동작한다. 퀵 정렬에서는 피벗(pivot)이 사용되는데, 큰 숫자와 작은 순자를 교환할 때 기준을 바로 피벗이라고 한다. 리스트를 분할하는 방식을 책에서는 호어 분할 방식을 통해 설명하고 있다.

동작 방식은 그림과 같이 5를 피벗으로 설정하고 왼쪽에서부터는 5보다 큰 데이터를 선택, 오른쪽에서부터는 5보다 작은 데이터를 선택하여 두 데이터 위치를 변경한다.

이후 9,2를 변경하고 다시 수행했을 때 1,6이 나오는데 이는 서로 엇갈린 것을 볼 수 있다. 이 때 작은 데이터인 1과 피벗인 5의 위치를 변경하여 분할을 수행한다.

최종적으로는 위 그림과 같이 5보다 작은 배열과 큰 배열이 분할된 것을 볼 수 있다.

퀵 소트 코드

위는 퀵 정렬을 파이썬 코드로 구현한 코드이다. 직관적이고 기억하기 쉽다는 장점이 있지만 시간 면에서 비효율적이라는 단점이 있다.

다음은 파이썬의 장점을 살린 퀵 정렬 코드이다.

 

퀵 정렬의 시간 복잡도는 평균적으로 O(NlogN)으로 앞선 두 정렬 알고리즘에 비해 매우 빠른 편이다.

직관적으로 데이터가 N개 있고, 안에서 분할이 logN만큼 일어난다고 가정하면 평균적으로 N X log N이 되어 O(NlogN)이 되는 것이다.

---

계수 정렬

 

계수 정렬은 특정 조건이 부합할 때만 사용할 수 있지만, 매우 빠른 정렬 알고리즘으로 최악의 경우에도 수행시간 O(N+K)를 보장한다.

다음과 같이 특정 값들이 여러 개 있을 때 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시키면 계수 정렬이 완료된다.

코드로 구현할 때 위와 같이 구현할 수 있다. 계수 정렬의 시간 복잡도는 데이터 개수 N, 데이터 중 최대값의 크기를 K라고 할 때 O(N+K)가 된다. 공간 복잡도 또한 같다.

 

python의 정렬 라이브러리로 sorted()와 sort()가 있는데, 이는 앞에서 말한 정렬 알고리즘보다 기본적으로 빠르다. O(NlogN)

또한 sorted함수에는 key를 지정할 수 있는데, 이와 같이 함수를 선언하고 정렬할 수 있다.