[이것이 코딩테스트다] 13일차 - 정렬

본문은 [이것이 취업을 위한 코딩테스트다 - 나동빈] 책을 공부하고 작성한 글입니다.

Chapter 6 정렬

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

데이터를 가공할때 데이터를 오름차순이나 내림차순으로 정렬하는 과정을 거치는 경우가 많아 정렬 알고리즘은 프로그램을 작성할때 가장 많이 사용되는 알고리즘 중 하나이다.  (이진 탐색의 전처리 과정이기도 함!)

 

이 책에서는 다음 네가지 정렬 알고리즘을 학습한다.

1. 선택 정렬    2. 삽입 정렬    3. 퀵 정렬    4. 계수 정렬

문제에서 요구하는 조건에 따라 적절한 정렬 알고리즘을 사용하지 않으면 프로그램이 비효율적으로 동작하게 되고 자연스럽게 정렬을 공부하다 보면 알고리즘의 효율의 중요성을 쉽게 이해할 수있다.  

 

정렬 종류 

(이번 예시에서는 오름차순 정렬만 사용하며, 내림차순 정렬은 오름차순 정렬을 반대로 뒤집는 파이썬 메소드 (reverse)를 사용하면 시간 복잡도 O(N)으로 구현가능하다)

 

선택 정렬

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

이처럼 선택 정렬은 가장 작은 데이터를 앞으로 보내는 작업을 N-1번 반복하면 정렬이 완료된다

 

선택 정렬의 시간복잡도 O(N^2)

  1. N-1번만큼 가장 작은 수를 찾아 맨앞으로 보내기

  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[min_index], array[i] = array[i], array[min_index]
    
## [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

 

삽입 정렬

데이터를 하나씩 확인하여 적절한 위치에 삽입하는 정렬 방식

삽입 정렬은 필요할 때만 위치를 변경하기때문에 선택정렬과 비교하여 더 효율적인 알고리즘이다.

	선택 정렬	삽입 정렬
구현 난이도	낮음	비교적 높음
시간 복잡도	O(N^2)	O(N)~O(N^2)

특히 데이터가 거의 정렬되어 있을때 더 효율적인 방식이다. (어느정도 정렬이 되어있다면 삽입 정렬을 사용하는 것이 정답확률을 높힐수 있는 방법이다)

step1에서 제일 처음수 4는 이미 정렬되었다고 생각하고 그 다음 수인 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):
        if array[j] < array[j-1]:
            array[j-1], array[j] = array[j], array[j-1]
        else:
            break
            
## [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

 

 

퀵 정렬

가장 많이 사용되는 정렬 알고리즘으로 실행 속도가 매우 빠르다

기준 데이터를 설정하고 이 데이터보다 큰 데이터와 작은 데이터의 위치를 서로 바꾸며 정렬하는 방식

이 기준은 pivot 이라고 하며 피벗을 설정하고 리스트를 분하라는 방법에 따라서 퀵 정렬을 여러가지로 구분하는데 

이 책에서는 호어 분할(Hoare Partition)에 대해 설명하고 있다 

 

호어 분할(Hoare Partition)

1. 리스트의 첫 번째 데이터를 피벗으로 정한다.

2. 왼쪽 -> 피벗보다 작은 데이터 찾기 // 오른쪽 -> 피벗보다 큰 데이터 찾기 --> 두 데이터 위치 교환

3. 반복

4. 왼쪽에 큰데이터, 오른쪽에 작은 데이터가 위치하게 된다면 작은 데이터와 pivot 위치 변경 (Partition)

5. 파티션 기준으로 1번부터 다시 진행

퀵 정렬은 재귀함수와 동작 원리가 같아 재귀함수로 구현이 가능한데, 이때 종료 조건은 현재 리스트의 데이터가 1이 된 지점이다.

 

다음은 널리 사용되고 있는 가장 직관적인 형태의 퀵 정렬 소스코드이다

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

퀵 정렬의 시간복잡도 O(NlogN)

피벗값의 위치가 변경되어 리스트가 절반식 분할된다고 가정한다면 정렬을 진행 할수록 분할이 이루어지는 횟수는 기하급수적으로 감소한다

최악의 경우 O(N^2)

위와 같이 pivot을 가장 왼쪽 데이터로 설정한다면, 데이터가 무작위로 입력되는 경우 매우 빠르게 동작하지만 이미 정렬되어 있는 데이터일 경우 매우 느리게 동작한다.

 

계수 정렬

별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담는 방식 

모든 범위를 담을 수 있는 크기의 리스트(배열)을 선언해야 하기때문에 특정 조건에 부합할 때만 사용

실행속도가 매우 빠른 정렬 알고리즘 - 모든 데이터가 양의 정수이고, 데이터의 개수가 N, 데이터의 최댓값이 K일 때, 계수 정렬은 최악의 경우에도 수행시간 O(N+K)를 보장한다

 

계수 정렬을 사용할 수 있는 경우

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

- 일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을때 효과적으로 사용할 수 있다. 

 

Data = 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2

0	1	2	3	4	5	6	7	8	9
2	2	2	1	1	2	1	1	1	2

데이터의 범위가 모두 담길 수 있는 하나의 리스트를 만들고 데이터르 처음부터 돌며 해당 index에 카운팅한다

정렬된 결과는 index를 카운트만큼 반복하여 print 하면 된다 ( 0을 두번, 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=' ') # 띄어쓰기를 구분으로 등장한 횟수만큼 인덱스 출력

계수 정렬의 시간복잡도 O(N+K)

데이터의 범위가 한정되어 있다면 효과적으로 사용이 가능하고, 항상 빠르게 동작하는 방식이다

 

계수 정렬의 공간복잡도 O(N+K)

때에 따라 심각한 비효율을 초래할 수 있다. ( Data = 0, 999999인 경우)

동일한 값을 여러개 가지는 데이터가 적합 (성적 등)

 

파이썬의 정렬 라이브러리

파이썬은 기본 정렬 라이브러리인 sorted()를 제공한다. 

sorted()는 퀵정렬과 동작방식이 유사한 병합 정렬을 기반으로 만들어졌는데, 병합정렬은 퀵 정렬보다는 느리지만 최악의 경우에도 시간복잡도 O(NlogN)을 보장한다는 장점을 가지고 있다. 

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

print (sorted(array))
array.sort()
print (array)
## [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

리스트 데이터가 튜플로 구성된 경우 sorted의 매개벼누인 key로 정렬 기준을 정할 수 있다.

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

def setting(data):
    return data[1]

result = sorted(array, key=setting)
print(result)

 

정렬 라이브러리의 시간복잡도 O(NlogN)

정렬 라이브러리는 최악의 경우에도 시간 복잡도 O(NlogN)를 보장한다

데이터의 개수(N)	선택 정렬	퀵 정렬	기본 정렬 라이브러리
N = 100	0.0123초	0.00156초	0.00000753초
N = 1,000	0.354초	0.00343초	0.0000365초
N = 10,000	15.475초	0.0312초	0.000248초

코딩테스트에서 정렬 알고리즘이 사용되는 경우

1. 정렬 라이브러리로 풀 수 있는 문제 : 단순히 정렬 기법을 알고 있는지 물어보는 문제 (정렬 라이브러리 사용)

2. 정렬 알고리즘의 원리에 대해 물어보는 문제 : 선택 정렬, 삽입 정렬, 퀵 정렬 등의 원리를 알아야 함

3. 더 빠른 정렬이 필요한 문제 : 퀵 정렬 기반의 정렬 기법으론 풀 수 없으며 계수 정렬 등의 다른 정렬 알고리즘을 이용하거나 기존에 알려진 알고리즘의 구조적인 개선을 거쳐야 함

 

 

예제 풀이는 다음 글에 작성하였습니다.

[이것이 코딩테스트다] 13일차 - 예제풀이