[Algorithm] 정렬 (Sorting) : 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬 파이썬 정렬 라이브러리 예제 코드 및 시간 복잡도

 

정렬(Sorting) 이란?

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

 

 

 

 

선택 정렬 (Selection Sort)

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

 

> Steps

< 중략 >

 

> Code with Python

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] 	# swap

 

> 시간 복잡도

- (N - 1)번 가장 작은 수를 찾아 맨 앞으로 보내야 한다

- 매번 가장 작은 수를 찾기 위한 비교 연산이 필요하다

- 연산 횟수는 N + (N - 1) + (N - 2) + ··· + 2 

                ≒  N * (N + 1) / 2 

                =  (N^2 + N) / 2

- 따라서 빅오 표기법으로 간단히 O(N^2)

- 선택 정렬은 매우 비효율적

 

 

 

 

삽입 정렬 (Insertion Srot)

특정 데이터 앞까지의 데이터는 이미 정렬되어 있다고 가정하고, 특정한 데이터에 대해 정렬된 데이터 리스트에서 적절한 위치를 찾아 그 위치에 삽입하는 방식의 정렬

 

> Steps

< 중략 >

 

> Code with Python

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

 

> 시간 복잡도

- 시간 복잡도 O(N^2), 최선의 경우 O(N)

- 현재 리스트의 데이터가 거의 정렬되어 있는 경우에는 매우 빠르게 동작

 

 

 

 

퀵 정렬 (Quick Sort)

기준을 설정하고, 기준보다 큰 수와 기준보다 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 정렬

피벗(Pivot) : 큰 숫자와 작은 숫자를 교환하기 위한 '기준', 설정하는 방법에는 여러 가지가 있지만, 여기서는 가장 대표적인 첫 번째 데이터를 피벗으로 설정하는 방식을 사용할 것이다

 

> 분할 단계

 

> 전체 분할 과정

 

> Code with Python

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


def quick_sort(array, start, end):
    if start >= end:
        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)

 

> 시간 복잡도

- 평균 : O(NlogN)

    * 최선의 경우 : 분할이 일어날 때마다 왼쪽 / 오른쪽 리스트가 전체 리스트의 절반씩 분할한다면 ? 높이는 약 logN이 된다

- 최악 : O(N^2)

    * 리스트의 가장 왼쪽 데이터를 피벗으로 할 때, 이미 데이터가 정렬된 경우에는 매우 느리게 동작한다

 

 

 

 

계수 정렬 (Count Sort)

'데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때'만 사용할 수 있으며, 별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담는 정렬 방식

 

> Steps

< 중략 >

 

> Code with Python

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

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

 

> 시간 복잡도

- 데이터 개수 N, 최대값 K일 때, 시간 복잡도는 O(N + K)

    * 데이터를 하나씩 확인하면서 인덱스 1씩 증가시킨다

    * 추후에 각 인덱스 해당하는 값 확인할 때 데이터 최댓값 크기만큼 반복을 수행해야 한다

 

> 공간 복잡도

- O(N + K)

- 데이터의 크기가 한정되어 있고, 데이터가 많이 중복되어 있을수록 유리하지만, 항상 사용할 수는 없다

 

 

 

 

파이썬의 정렬 라이브러리

> sorted() 함수

- 기본 정렬 라이브러리의 함수

- 병합 정렬 기반으로 만들어졌다

- 결과로 리스트 자료형을 반환

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

result = sorted(array)

 

> sort() 함수

- 리스트 객체의 내장 함수

- 정렬된 리스트가 반환되는 것이 아니라 내부 원소가 바로 정렬된다

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

array.sort()

 

> key값

- sorted()나 sort()를 이용할 때 key 매개변수를 입력받을 수 있다

- 하나의 함수가 들어가야 하며 정렬의 기준이 된다

- 람다 함수를 사용할 수도 있다

array = [('바나나', 2),('사과',5),('당근',3)]

def setting(data):
    return data[1]

result = sorted(array, key=setting)

print(result)
# [('바나나', 2), ('당근', 3), ('사과', 5)]

 

> 시간 복잡도

- 최악의 경우에도 시간 복잡도 O(NlogN)을 보장한다

- 파이썬은 병합 정렬과 삽입 정렬의 아이디어를 더한 하이브리드 방식 정렬 알고리즘을 사용한다

 

> 코딩 테스트에서 정렬 알고리즘 사용 유형

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

2. 정렬 알고리즘의 원리에 대해 묻는 문제 : 선택 / 삽입 / 퀵 정렬 등의 원리를 알 수 있어야 한다

3. 더 빠른 정렬이 필요한 문제 : 계수 정렬 등을 이용하거나 기존 알고리즘의 구조적 개선을 거쳐야 한다

 

 

 

 

 

 

 

 

📚 참고서적 : 이것이 코딩테스트다 with 파이썬