[algorithm][python] 정렬

Selection Sort

매번 ‘가장 작은 것’을 선택해 앞으로 보낸다

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[i], array[min_index] = array[min_index], array[i]
    
print(array)

시간 복잡도: O(N^2)

Insertion Sort

특정한 데이터를 적절한 위치에 ‘삽입’한다.

삽입 정렬은 필요할 때만 위치를 바꾸므로 ‘데이터가 거의 정렬되어 있을 때’ 효율적이다.

삽입 정렬은 첫 번째 데이터는 그 자체로 정렬되어 있다고 판단하기 때문에 두 번째 데이터부터 시작한다.

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)

선택 정렬과 흡사한 시간이 소요되나 리스트가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다.

최선의 경우 O(N)의 시간 복잡도를 가진다.

보통은 삽입 정렬이 비효율적이나 거의 정렬된 상황에서는 퀵 알고리즘보다 효율적이다.

Quick Sort

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

merge sort와 함께 빠른 정렬 알고리즘으로 많이 사용된다.

피벗(pivot): 큰 숫자와 작은 숫자를 교환하기 위한 기준

피벗 설정 기준에 따라 퀵 정렬이 여러 방식으로 구분되는데, 호어 분할(Hoare Partition)을 기준으로 설명함.

(리스트에서 첫 번째 데이터를 피벗으로 정한다.)

왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다. 그 다음 서로 교환해준다.

1. 피벗보다 작은 데이터와 큰 데이터를 찾아 서로의 위치를 교환하는 것을 반복
2. 왼쪽에서부터 찾는 값과 오른쪽에서부터 찾는 값의 위치가 서로 엇갈리면 ‘작은 데이터’와 ‘피벗’의 위치를 서로 변경한다.
3. 피벗의 왼쪽에는 피벗보다 작은 데이터가 위치하고, 피벗의 오른쪽에는 피벗보다 큰 데이터가 위치하게 된다.

재귀함수로 구현, 종료조건은 리스트 길이가 1일 때

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

def quick_sort(array, start, end):
    if start >= end: # 원소가 1개인 경우 종료
        return
    pivot = start
    left = start + 1
    right = end
    while left <= right:
        # 피벗보다 큰 데이터를 찾을 때까지 반복
        while left <= end and array[left] <= array[pivot]:
            left += 1
        # 피벗보다 작은 데이터를 찾을 때까지 반복
        while right > start and array[right] >= array[pivot]:
            right -= 1
        if left > right: # 엇갈렸다면 작은 데이터와 피벗을 교체
            array[right], array[pivot] = array[pivot], array[right]
        else: # 엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체
            array[left], array[right] = array[right], array[left]
    # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
    quick_sort(array, start, right-1)
    quick_sort(array, right + 1, end)
    
quick_sort(array, 0, len(array)-1)
print(array)

array = [7,5,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))

파이썬의 장점을 살려 짧게 작성한 퀵 정렬 소스코드.

피벗과 데이터를 비교하는 비교 연산 횟수가 증가해 시간 면에서 조금 비효율적이다.

평균 시간 복잡도: O(Nlog(N))

최악의 경우: O(N^2)

퀵 정렬은 데이터가 무작위로 입력된 경우 빠르게 동작할 확률이 높고, ‘이미 데이터가 정렬되어 있는 경우’ 매우 느리게 동작한다(삽입 정렬과 반대).

(C++, 파이썬 등의 기본 정렬 라이브러리에서는 최악의 경우에도 Nlog(N)을 보장하기 위한 추가적인 피벗 설정 알고리즘이 있어 크게 걱정하지 않아도 됨)

Count Sort

계수 정렬 알고리즘은 특정 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘이다.

모든 데이터가 양의 정수일 때, 데이터 개수 N 최댓값 K에 대하여 최악의 경우에도 수행시간 O(N+K)를 보장한다.

조건: 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때

일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적

→ 모든 범위를 담을 수 있는 크기의 리스트를 선언해야 하기 때문

위 처럼 비교 기반의 정렬 알고리즘이 아님

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

#모든 원소의 값이 0보다 크거나 같다고 가정
array = [7,5,9,0,3,1,6,2,9,1,4,8,0,5,2]
#모든 범위를 포함하는 리스트 선언(모든 값은 0으로 초기화)
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=' ') #띄어쓰기를 구분으로 등장한 횟수만큼 인덱스 출력

계수 정렬은 데이터의 크기가 한정되어 있고, 데이터의 크기가 많이 중복되어 있을수록 유리하며 항상 사용할 수는 없다.

파이썬의 정렬 라이브러리

파이썬은 기본 정렬 라이브러리인 sorted() 함수를 제공하는데, 이는 퀵 정렬과 동작 방식이 비슷한 병합 정렬을 기반으로 만들어졌다.

병합 정렬은 일반적으로 퀵 정렬보다 느리지만 최악의 경우에도 시간 복잡도 O(N*logN)을 보장한다는 특징이 있다.

1. 정렬 라이브러리로 풀 수 있는 문제

단순히 정렬 기법을 알고 있는지 물어보는 문제로 기본 정렬 라이브러리의 사용 방법을 숙지하고 있으면 된다.

1. 정렬 알고리즘의 원리에 대해서 물어보는 문제

선택, 삽입, 퀵 정렬 등의 원리를 알고 있어야 문제를 풀 수 있다.

1. 더 빠른 정렬이 필요한 문제

퀵 정렬 기반의 정렬 기법으로 풀 수 없으며 계수 정렬 등의 다른 정렬 알고리즘을 이용하거나 문제에서 기존에 알려진 알고리즘의 구조적인 개선을 거쳐야 문제를 풀 수 있다.