정렬 알고리즘

정렬이란 데이터를 특정한 기준에 따라 순서대로 나열하는 것을 말한다.

데이터를 가공할 때 오름차순이나 내림차순 등 정렬해서 사용하는 경우가 많다.
때문에, 가장 많이 사용되는 알고리즘이다.

문제의 요구에 따라 적절한 정렬 알고리즘을 사용해야 하므로,
알고리즘 효율의 중요성을 느끼는 알고리즘이기도 하다.

현대의 정렬 알고리즘은 정립되어 있기 때문에, 외워서 잘 풀어낼 수 있다.

밑에 다룰 정렬 알고리즘은 오름차순 정렬을 기준으로 설명한다.
내림차순을 한다면, 조건의 부등식만 바꾸거나, reverse()등의 함수를 활용한다.

선택 정렬

컴퓨터로 데이터를 정렬 시킬 때, 어떻게 할지 생각해보자.

데이터에서 가장 작은 데이터를 선택해 맨 앞에 데이터와 바꾸고,
그 다음 작은 데이터를 두번째와 바꾸는 것을 반복하면, 정렬이 될것이다.

이처럼 가장 작은 것을 선택 한다는 의미에서 선택정렬 알고리즘이라 한다.

무작위 데이터에서 가장 작은 수를 찾아 맨 앞으로,
나머지 수 중 가장 작은 수를 두 번째로, 이를 반복한다.

코드

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

python의 스왑
스왑이란 특정한 리스트가 주어질 때, 두 변수의 위치를 변경하는 작업을 의미한다.
보통 임시 저장용 변수를 통해 값을 변경하나, python에서는 간단히 변경할 수 있다.

시간 복잡도

시간복잡도는 N-1번 가장 작은 수를 찾아야 하는데, 간단히 O(N^2)이다.
간단하게, 반복문의 중첩을 보고 판단할 수도 있다.
파이썬의 기본 정렬 라이브러리를 포함하여, 다른 알고리즘과 비교하여 매우 비효율적이다.

삽입 정렬

데이터를 하나씩 확인하여 적절한 위치에 삽입하는 알고리즘이다.
선택정렬에 비해 효율적이며, 필요할 때만 위치를 바꾸기 때문에,
데이터가 거의 정렬되어 있을 때, 더 효율적이다.

정렬되어 있는 데이터 리스트에서, 적절한 위치를 찾고 그 위치에 삽입된다.

삽입정렬은 두 번째 데이터부터 시작하는데, 첫 번째 데이터는 정렬되어 있다고 판단한다.
(어차피 하나이기 때문)

삽입할 데이터를(첫 단계엔 두 번째 데이터), 정렬된 데이터와 비교하여,
어떤 위치로 들어갈지 판단한다.

정렬된 데이터가 삽입할 데이터보다 크다면, 삽입할 데이터를 앞으로 보내고 다음 데이터와 반복한다.
작다면, 해당 위치에서 멈춘다.
(삽입할 데이터 왼쪽의 데이터는, 정렬되어 있기 때문에 작다면 그 자리에 삽입하면 된다.)

코드

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): # range(start, end, step)
        if array[j] < array[j-1]:
            array[j],array[j-1] = array[j-1],array[j]
        else:
            break
  

시간 복잡도

삽입정렬도 시간 복잡도는 O(N^2)이다. 선택정렬과 마찬가지로 반복이 2번 중첩되었다.
실제 실행 시간 역시 선택정렬과 비슷하다.

다만, 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작하기에,
최선의 경우 O(N)의 시간 복잡도를 가진다.
이런 상황에서는 퀵 정렬보다도 유리하다.

따라서, 거의 정렬이 되어있는 상태에서 새 입력이 있는 경우 삽입정렬을 이용하는 것이 좋다.

퀵 정렬

퀵 정렬은 앞서 배운 알고리즘 중 가장 많이 사용되는 알고리즘이다.
또한, 병합정렬과 함께 프로그래밍 언어에서 정렬 라이브러리의 근간이 되는 알고리즘이다.

기준 데이터를 설정하고, 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 알고리즘이다.
기준을 설정하고, 큰 수와 작은 수를 교환한 후 반으로 나누는 방식으로 동작한다.

위에서 설명한 기준 값을 피벗pivot이라 하는데,
이를 어떻게 설정하고 분할 하느냐에 따라 여러 방식으로 퀵정렬을 구분한다.

그 중 대표적인 분할 방식인 호어 분할Hoare Partition 방식을 설명한다.
호어 분할 방식은 리스트의 첫번째 데이터를 피벗으로 설정한다.

피벗을 설정하면, 왼쪽에서 부터 피벗보다 큰 데이터를 찾고,
오른쪽에서부터 작은 데이터를 찾는다. 두 값을 서로 교환해주고, 이를 반복한다.

단, 왼쪽에서 찾는 값과 오른쪽에서 찾는 값의 위치가 엇갈렸을 때,

작은 데이터와 피벗의 위치를 서로 변경하여, 분할을 수행한다.

이렇게 하면, 피벗보다 왼쪽의 데이터는 피벗보다 작고,
피벗보다 오른쪽의 데이터는 피벗보다 크다.
이 작업을 분할 혹은 파티션이라 한다.

이처럼, 피벗을 설정하고 작은 값 큰 값으로 분할한다.
그 후, 왼쪽 리스트와 오른쪽 리스트를에서 각각 정렬을 수행한다.

이는, 재귀함수로 구현할 수 있다. 종료 조건은 리스트의 원소가 1개일 때 이다.
(1개는 이미 정렬이며, 분할이 불가능하다)

코드

2가지 방법이 있다.
위에 설명과 그대로 전통 퀵정렬 분할 방식을 구현하는 것과,
python의 장점을 살려 pivot보다 큰 값, 작은 값을 구분하고 짧게 정렬을 구현하는 코드가 있다.

다만, 후자는 모든 데이터에 대해 큰지 작은지 비교하기 때문에, 연산 횟수가 증가한다.

전통 퀵정렬 분할방식

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

def quick_sort(arr,start,end):
    if start>=end : return

    pivot = start
    left = start+1
    right = end

    while left<=right:
        while left <= end and arr[left] <= arr[pivot]:
            left += 1
        while right >= start and arr[right] >= arr[pivot]:
            right -= 1
        if left>right:
            arr[right],arr[pivot] = arr[pivot], arr[right]
        else:
            arr[right],arr[left] = arr[left],arr[right]
  
    quick_sort(arr,start,right-1)
    quick_sort(arr,right+1,end)

quick_sort(arr,1,len(arr)-1)
print(arr)

작은 값, 큰 값 필터 방식

def quick_sort(arr):
    if len(arr) <= 1:
        return array
    
    pivot = arr[0]
    tail = arr[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)

시간 복잡도

퀵 정렬의 평균 시간 복잡도는 O(NlogN)이다 앞서 다룬 두 알고리즘에 비해 매우 빠르다.
참고로, 컴퓨터 과학의 log는 밑이 2인 로그이다.

정확한 증명은 어렵지만, 최선의 경우를 생각해보자.
데이터의 개수가 8개 일 때, 피벗 값의 위치가 변경되어, 왼쪽과 오른쪽을 절반씩 분할한다면,
높이는 logN이 된다.

다만, 퀵 정렬은 평균 시간복잡도가 O(NlogN)이지만, 최악의 경우 O(N^2)이 된다.
삽입정렬과 반대로, 이미 데이터가 정렬되어 있는 경우에는 매우 느리게 동작한다.

데이터가 무작위로 입력되는 경우 퀵정렬을 빠르게 동작할 가능성이 높다.

계수 정렬

계수 정렬 알고리즘은 특정한 조건이 부합할 때만 사용할 수 있자만 매우 빠른 정렬 알고리즘이다.
데이터 개수가 N, 최댓값이 K일 때 최악의 경우에도 O(N+K)를 보장한다.

다만, 계수정렬은 '데이터 크기가 제한되어 정수 형태로 표현할 수 있을 때'만 사용할 수 있다.
또한, 가장 큰 데이터와 가장 작은 데이터의 차이가 크지 않은 것이 좋다.

계수 정렬은 앞서 다룬 3가지 알고리즘 처럼, 직접 데이터의 값을 비교하고 위치를 변경하는 방식이 아니다.

정렬방식
계수 정렬은 우선 가장 큰 데이터와, 가장 작은 데이터의 범위가 모두 담길 수 있도록 하나의 리스트를 생성한다.

데이터의 범위가 0부터 9까지 라면, 크기가 10인 리스트를 선언하면 된다.
처음엔 모든 값을 0으로 초기화한다.

그 다음 데이터를 하나 씩 확인하며, 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시킨다.

초기데이터 : 7 5 9 0 3 1 6 2 9 0 5 2

결과적으로, 각각의 데이터가 몇번 등장했는지 그 횟수가 기록된다.
5 인덱스의 값이 2라면, '5'는 2번 등장한 것이다.

정렬한 데이터를 보고싶다면, 리스트의 처음 인덱스 부터, 인덱스를 그 값 만큼 출력하면 된다.
최솟값 부터 등장한 횟수만큼 출력하면, 정렬한 데이터가 된다.

0 => 2회 출력
1 => 1회 출력
2 => 2회 출력
. . .

코드

arr = [7,5,9,0,3,1,6,2,9,0,5,2]

count = [0]*(max(arr)+1)

for i in arr:
    count[arr[i]] += 1

# 출력
for i in range(len(count)):
    for j in count[i]:
         print(i);
        

시간 복잡도

모든 데이터가 양의 정수인 상황에서, O(N+K)가 된다.
데이터의 개수인 N만큼 확인하여, 해당 인덱스의 값을 증가시키고,
최대 값인 K만큼 반복을 수행해야 하기 때문이다.

데이터의 범위만 한정되어 있다면 효과적이고, 정렬 알고리즘 중에서 기수 정렬과 더불어 가장 빠르다고 할 수 있다.

공간 복잡도

만약 데이터의 크기는 2이지만, 둘의 차이가 999,999라고 한다면,
2개의 데이터를 위해 1,000,000 크기의 리스트를 만들어야한다.
따라서, 항상 사용하기보다, 동일한 값을 가지는 데이터가 여러 개 등장할 때 적합하다.

즉, 데이터의 개수가 많더라도, 중복이 많고 범위가 한정되어 있다면 효과적이다.

파이썬의 정렬 라이브러리

파이썬은 기본 정렬 라이브러리인 sorted() 함수를 제공한다.
퀵 정렬과 비슷한 병합 정렬을 기반으로 만들어졌는데, 병합정렬은 퀵 정렬보다 느리지만,
최악의 경우에도 O(NlogN)을 보장한다.

정렬 라이브러리는 데이터를 받아서, 정렬된 결과를 출력할 수 있다.
반환되는 결과는 항상 리스트이다.

arr = [7,5,9,0,3,1]
result = sorted(arr)
print(result) # sort data

리스트 객체의 내장 함수인 sort()를 이용해 반환하지 않고, 내부 원소를 바로 정렬할 수 있다.

arr = [7,5,9,0,3,1]
arr.sort()
print(arr) # sort data

또한, sorted나 sort 함수는 key 매개변수를 입력으로 받을 수 있다.
key의 값으로는 함수가 들어가야 하며, 이는 정렬의 기준이된다.
추가로, 람다 함수를 활용하여 소스코드를 간결하게 할 수 있다.

arr = [('바나나',1),('사과',5),('당근',3)]

def setting(data): return data[1]

arr.sort(key=setting)
print(arr)

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

정렬 라이브러리는 최악의 경우에도 O(NlogN)을 보장한다.
이미 잘 작성된 함수이므로, 직접 퀵 정렬을 구현할 때보다 더욱 효과적이다.

만약, 문제에서 별도의 요구가 없이 단순히 정렬하는 상황에서는, 기본 정렬 라이브러리를 사용하고, 범위가 한정되어있다면, 더 빠른 계수 정렬을 사용하면 효과적이다.