[Algorithm] 정렬

1. 정렬 알고리즘이란? 

데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다. (정렬 알고리즘은 이진 탐색의 전처리 과정이기도하니 제대로 알고 넘어가자.)

파이썬에서는 내림차순 리스트를 제공하고, 이는 O(N) 복잡도로 수행가능하니, 오름차순만 우선 공부해보자.

 

2. 선택 정렬

선택정렬의 아이디어는 매번 ' 가장 작은 것을 선택한다. ' 이다.

데이터가 무작위로 여러 개 있을 때, 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복한다. 

가장 작은 데이터를 N - 1번 반복하면 정렬이 완료되는 것을 알 수 있다. 

 

array = [7,5,9,0,3,1,6,2,4,8]

for i in range(len(array)):
    min_index=i
    for j in range(i+1, len(array)):
        if array[min_index] > array[j]:
            min_index=j
        array[min_index], array[i] = array[i], array[min_index]

print(array)

 

- 시간 복잡도 

선택정렬은 N - 1 만큼 가장 작은 수롤 찾아서 맨 앞으로 보내야하고, 매번 작은 수를 찾기 위해서 비교 연산이 필요하다. 

연산 횟수는 (N) + (N-1) + (N-2) + (N-3) .. +2 로 볼 수 있다. 이는 N(N-1)/2 로 표현할 수 있으므로 빅오 표현법으로 O(N^2)이다. 

(간단히 생각하면 이중 반복문을 사용하고 있기 때문이다.)

 

결론적으로 시간 복잡도는 기본 정렬 라이브러리를 포함하여 뒤에서 다룰 알고리즘과 비교해보면 비효율적이다. 다만 리스트에서 가장 작은 데이터를 찾는 일이 코딩 테스트에서 잦으므로 소스에 익숙해지자. 

 

3. 삽입 정렬

삽입 정렬의 기본 아이디어는 ' 데이터를 하나씩 확인하여, 각 데이터를 적절한 위치에 삽입하자. ' 이다. 이는 구현 난이도는 높지만 효율적이다. 그리고 이는 필요할 때만 위치를 바꾸므로 데이터가 거의 정렬되었을 때 효율적이다.

 

두번째 데이터부터 마지막까지 반복하여 자신이 들어가야 할 적절한 위치를 찾아 삽입한다. 

적절한 위치를 찾는 방법은 이미 정렬이 된 그룹의 오른쪽에서 시작해서 왼쪽으로 가면서 자신보다 작은 데이터를 만나면 멈추면 된다. (이미 정렬이 되어있는 상태기 때문에 문제가 없다. )

 

array = [7,5,9,0,3,1,6,2,4,8]
for i in range(1,len(array)):
    for j in range(i, 0, -1):
        if array[j]<array[j-1]:
            array[j], array[j-1] = array[j-1], array[j]
        else:
            break

print(array)

 

- 시간 복잡도 

삽입 정렬도 이중 반복문을 사용하기 때문에 시간 복잡도가 O(N^2)이다.

하지만 삽입 정렬은 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작하기 때문에 이런 상황에서 유용하게 사용할 수 있다. 

 

4. 퀵 정렬

퀵 정렬은 가장 많이 사용되는 알고리즘으로 아이디어는 ' 기준 데이터를 정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸면 어떨까? '이다. 퀵 정렬에서는 피벗이 사용된다. 큰 수와 작은 수를 교환할 때, 교환하기 위한 '기준'으로 피벗이라고한다. 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작한다.

 

조금 더 구체적으로 설명하면, 피벗은 리스트의 가장 첫번째 데이터로 설정한다. 피벗을 설정한 뒤에는 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다. 그 다음 큰 데이터와 작은 데이터의 위치를 교환해준다. 

 

종료 조건은 왼쪽에서 찾는 값과 오른쪽에서 찾는 값의 위치가 엇갈렸을 때이다. 이 경우 작은 데이터와 피벗의 위치를 서로 변경한다. 이 경우 분할이 완료된 것이다. 

 

그 다음부터는 분할된 리스트에서 각각 같은 과정을 반복한다. 퀵 정렬이 끝나는 경우는 현재 리스트의 데이터 개수가 1개인 경우이다. 

 

array= [5,7,9,0,3,1,6,2,4,8]

def quick_sort(array):
    if len(array) <= 1:
        return array

    pivot = array[0]
    tail = array[1:]
    left_side = [x for x in tail if x <= pivot]
    right_side = [x for x in tail if x > pivot]
    return quick_sort(left_side) + [pivot] + quick_sort(right_side)

print(quick_sort(array))

 

* [x for x in tail if x < = pivot] 은 리스트 컴프리헨션 문법이다.  맨 앞에 x에 반복문을 통해 들어온 x를 append 해준다고 생각하면 된다. 

참고) https://semo-na.tistory.com/26

 

- 시간 복잡도 

퀵 정렬의 시간 복잡도는 O(NlogN)이다.  증명은 어려우니 pass 

다만, 평균적으로 O(NlonN)이지만 최악의 경우 O(N^2)이다. 무작위로 입력되는 경우 빠르게 동작하지만, 가장 왼쪽 데이터를 피벗으로 삼을 때, '이미 데이터가 정렬되어 있는 경우' 매우 느리게 동작한다. 

 

5. 계수 정렬

특정한 조건이 부합할 때만 사용할 수 있지만, 매우 빠른 정렬 알고리즘이다. 계수 정렬은 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을때만 사용할 수 있다. (일반적으로 가장 큰 데이터와 작은 데이터의 차이가 1,000,000을 넘지 않을 때 사용하자.)

 

계수 정렬은, 먼저 가장 큰 데이터와 작은 데이터의 범위가 모두 담길 수 있도록 하나의 리스트를 생성한다. ex) 우리가 정렬할 데이터의 범위가 0부터 9까지라면 크기가 10인 리스트를 선언하면 된다. 

처음에는 리스트의 모든 데이터가 0이 되도록 초기화하고, 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1 증가시킨다. 

 

array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]
count = [0] * (max(array)+1)

for i in range(len(array)):
    count[array[i]]+=1

for i in range(len(count)):
    for j in range(count[i]):
        print(i, end='')

 

- 시간 복잡도

데이터가 양의 정수인 상황에서 데이터의 개수를 N, 데이터 중 최대값의 크기를 K라고 할 때, 계수 정렬의 시간 복잡도는 O(N+K)이다. 

리스트에서 적절한 인덱스의 값을 1씩 증가하고, 추후에 리스트의 각 인덱스에 해당하는 값들을 확인할 때 데이터 중 최댓값의 크기만큼 반복하기 때문이다. 

따라서 데이터의 범위만 한정되어 있다면 가장 빨리 동작하는 알고리즘이다. 

 

- 문제 

https://www.acmicpc.net/problem/10989

10989번: 수 정렬하기 3

import sys
n=int(sys.stdin.readline())
array=[0]*10001
for i in range(n):
    array[int(sys.stdin.readline())] += 1

for i in range(len(array)):
          for j in range(array[i]):
              print(i)

위 문제에서

n의 최댓값은 10,000,000 이므로 1천만 개의 데이터를 메모리에 저장해야 한다.  각 데이터 한 개마다 4바이트이므로 총 메모리는 4천만 바이트, 이는 40MB이다. 즉 기존 방법으로는 문제에서 요구한 8 MB안에 문제를 해결할 수 없다.

이를 해결하기 위해 메모리에 저장시킬 데이터의 수를 줄여야 한다.

 

이 문제에서는 수의 범위가 10,000밖에 되지 않기 때문에 계수 정렬로 문제를 푼다면, 소비되는 메모리는 10,000 * 4 = 40,000 byte = 0.04MB이다. 

위에서 사용한 방법보다 더 적은 메모리가 필요해서 입력 -> 정렬의 방법을 쓰지 않고 애초에 입력과 동시에 정렬하는 방법을 사용하여 해결했다.

 

4. 코딩 테스트에서 사용할 파이썬 정렬 라이브러리

파이썬에서 정렬 라이브러리는 항상 최악의 경우에도 시간 복잡도 O(NlogN)을 보장한다.

 

array = [7,5,9,0,3,1,6,2,4,8]
result = sorted(array)
print(result)

# 혹은

array.sort()
print(array)

 

결론적으로, 단순히 정렬을 해야하는 상황에서는 정렬 라이브러리를 사용하고, 데이터의 범위가 한정적이라면 더 빠르게 동작해야할 때 계수 정렬을 사용하자. (하지만 정렬 알고리즘의 원리에 대해서 물어보는 문제도 있으니 위 개념들은 다 숙지하고 구현할 수 있어야한다.)

 

* 추가로 시간 초과가 뜬다면 input 대신 sys 모듈을 import 해서 사용하자.

 

 

import sys

sys.stdin.readline()

 

이라고 입력하면 된다. 

 

참고) 책, 이것이 코딩테스트이다.