[이코테] 정렬 알고리즘

선택정렬

가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 다음으로 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복한다. 2중 반복문을 사용하기 때문에 O(N**2)의 시간복잡도를 갖고 다른 정렬 알고리즘에 비해 다소 비효율적이다.

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[j]

 

삽입정렬

데이터를 하나씩 순회하며, 각 데이터를 적절한 위치에 삽입. 선택정렬에 비해 효율적인 구조이며, 데이터가 거의 정렬된 상태일 때는 훨씬 더 좋은 성능을 보여준다. 앞의 수와 비교하여 자신이 더 작다면 더 앞으로 이동하는 과정을 반복한다. 삽입정렬도 선택정렬과 마찬가지로 O(N**2)의 시간 복잡도를 가진다. 그러나 앞서 말했듯 리스트가 거의 정렬된 상태라면 O(N)의 시간 복잡도를 갖기도 한다.

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)

 

퀵 정렬

가장 범용적으로 사용되는 정렬 알고리즘으로, 기준(피벗)을 설정한 다음 기준보다 작은 값은 왼쪽으로, 큰 값은 오른쪽으로 정렬한다. 그렇게 나뉘어진 두 구역에서 같은 과정을 반복하여 정렬한다. 재귀 함수를 사용하여 구현하며, 리스트의 데이터 개수가 1인 경우 종료하는 조건을 설정한다.

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)

퀵 정렬의 시간 복잡도는 평균적으로 O(NlogN)이며, 앞에서 언급한 두 정렬 알고리즘에 비해 굉장히 빠른 편이다. 그러나 삽입정렬과는 반대로, 리스트가 무작위인 경우 빠르게 동작한다는 특성이 있다.

 

계수정렬

매우 빠르지만, 사용 가능한 조건이 제한적인 알고리즘이다. 계수 정렬은 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을때만 사용하며, 데이터의 편차가 1,000,000을 넘지 않을 때 효과적으로 사용할 수 있다.

모든 범위를 담을 수 있는 빈 리스트를 생성하여, 정렬할 리스트의 값에 해당하는 빈 리스트 인덱스에 1을 더해준다. 영상처리에서의 히스토그램을 만드는 방식과 유사한 듯 하다. 값이 곧 인덱스가 되고, 그 인덱스가 곧 정렬이 완료된 값이 되는 것이다.

 

파이썬의 정렬 라이브러리

코딩 테스트에서 알고리즘 문제를 풀 때, 직접 코드를 구현하는 경우도 있지만 파이썬에 내장된 기본 정렬 라이브러리를 사용하는 경우가 더 많다고 한다. sorted()함수인데, 퀵정렬과 동작 방식이 유사하다. 키-값 쌍을 통한 정렬도 가능하다. sorted(array)나 array.sort() 를 사용한다.

 

코딩 테스트에서의 정렬 라이브러리

일반적으로 3가지 유형이 존재한다.

1. 정렬 라이브러리를 이용하는 문제

2. 정렬 알고리즘의 원리에 대해 물어보는 문제 : 각 정렬의 특성과 원리를 알고 있어야 하며, 구조적인 개선을 통해 문제에 맞게 수정할 수 있는 능력을 요한다.

3. 더 빠른 정렬이 필요한 문제 : 퀵 정렬 기반의 정렬 기법으로는 풀 수 없으며 계수 정렬 등의 다른 정렬 알고리즘을 이용하거나, 기존 알고리즘을 개선하여야 풀 수 있는 문제들이다.

 

이코테 교재에는 소개되지 않았지만, 저번 학기 알고리즘 강의에서 배운 버블정렬 등의 방법들도 많이 사용된다고 들었다. 원리와 구현 방법은 많이 익혀둘수록 좋을 듯 하다.