[이코테] chap6. 정렬

코딩테스트의 정렬 알고리즘이 사용되는 경우는 크게 3가지 유형으로 나눌 수 있다.

1. 정렬 라이브러리로 풀 수 있는 문제
2. 정렬 알고리즘의 원리에 대해 묻는 문제: 선택 정렬, 삽입 정렬, 퀵 정렬 등의 원리를 알아야 풀 수 있음.
3. 더 빠른 정렬이 필요한 문제:
퀵 정렬 기반의 정렬 기법으론 풀 수 없고, 계수 정렬 등 다른 정렬 알고리즘을 이용하거나 문제에서 기존에 알려진 알고리즘의 구조적인 개선을 거쳐야 풀 수 있는 문제.

정렬 라이브러리또한 병합 정렬과 삽입 정렬이 합해진 방식이므로, 비교하기 위해 기본 정렬 방식부터 정리하려 한다.

1. 정렬 알고리즘

정렬 정의 및 특징

• 정렬(sorting)이란 데이터를 특정한 기준에 따라 순서대로 나열한 것을 말한다.
• 정렬 알고리즘으로 데이터를 정렬하면 이진 탐색(Binary Search)이 가능해진다.
  (이진 탐색의 전처리 과정)
• 적절하지 못한 정렬 알고리즘을 이용하면 프로그램이 비효율적으로 동작하기에 알고리즘 효율성의 중요성을 깨닫게 된다.
• 정렬의 종류엔 대표적으로 선택, 삽입, 퀵, 계수 정렬이 있다.

 

1-1. 선택 정렬

가장 원시적인 방법으로, 매번 '가장 작은 것을 선택'한다는 의미에서 선택 정렬(Selection Sort)이라고 한다.

가장 작은 것을 선택해 앞으로 보내는 과정을 반복해서 수행하는 것이다.

1) 알고리즘 & 소스코드

알고리즘

1. 가장 작은 데이터를 뽑아 맨 앞에 배치한다.
2. 이후 데이터 중 가장 작은 데이터를 뽑아 처리하지 않은 데이터 목록 중 가장 앞에 데이터와 맞바꾼다.
3. 2번을 N-1번 반복하면 정렬이 완료된다.

- 소스 코드

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)

2) 시간 복잡도

연산 횟수는 N + (N-1) + (N-2) + ... + 2 로 볼 수 있다.
따라서 $(N^2 + N)/2$ 로 표현할 수 있으므로 빅오 표기법에 의해 $O(N^2)$이다.
하지만 선택 정렬 알고리즘과 퀵, 기본 정렬 라이브러리의 수행 결과를 비교하면 선택 정렬을 이용하는 경우 데이터의 개수가 10,000개 이상이면 급격히 느려지는 것이 확인된다.

그러므로 매우 비효율적이므로 특정한 리스트에서 가장 작은 데이터를 찾는 일에 관해서 선택 정렬 소스코드를 활용하는 것일뿐, 실제 정렬 문제에선 효율적이지 않다.

1-2. 삽입 정렬

특정한 데이터를 적절한 위치에 '삽입'한다는 의미에서 삽입 정렬(Insertion Sort)라고 부른다.

• 적절한 위치에 들어가기 이전에, 그 앞까지 데이터는 이미 정렬되어 있다고 가정한다.
• 정렬된 리스트에서 적절한 위치를 찾은 뒤, 그 위치에 삽입된다는 점이 특징이다.
• 첫 번째 데이터는 그 자체로 정렬되어 있다고 판단하여, 삽입 정렬은 두 번째 데이터부터 시작한다.

1) 알고리즘 & 소스코드

1. 첫 번째 데이터는 그 자체로 정렬되어 있다고 판단, 두 번째 데이터부터 삽입할 데이터로 지정한다.
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): # 인덱스 i부터 1까지 1씩 감소하며 반복하는 문법
        if array[j] < array[j - 1]: # 한 칸씩 왼쪽으로 이동
            array[j], array[j - 1] = array[j - 1], array[j]
        else: # 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
            break

print(array)

2) 시간 복잡도

• 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다. 최선의 경우 O(N)
  이런 경우 퀵 정렬 보다도 강력하다.
• 평균 시간 복잡도: $O(N^2)$, 공간 복잡도: $O(N)$

1-3. 퀵 정렬

• 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법.
• '병합 정렬'과 비슷하게 빠른 알고리즘.
• 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘.- 알고리즘 & 소스코드

1) 알고리즘 & 소스코드

1. 피벗(pivot) 이 기준이 되어 리스트의 왼쪽에서부터 피벗보다 큰 데이터, 오른쪽에서부턴 작은 데이터를 찾는다.
2. 왼쪽과 오른쪽에서 찾는 값의 index가 엇갈린 경우, '작은 데이터'와 '피벗'의 위치를 교환한다.
3. 1,2번의 과정을 파티션의 길이가 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)

2. 좀 느리지만 파이썬다운 퀵 정렬 코드

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))

 

2) 시간 복잡도

 평균 시간 복잡도: O(NlogN), 공간 복잡도: O(N)

1-4. 계수 정렬

특정한 값을 가지는 데이터의 개수를 '카운트'하는 방법.

1) 알고리즘 & 소스코드

1. 데이터의 최댓값인 K를 파악하여 K+1크기의 리스트를 만들어 탐색하는 데이터에 해당하는 리스트의 인덱스에 count 하는 방식이다.

- 소스 코드

# 모든 원소의 값이 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=' ') # 띄어쓰기를 구분으로 등장한 횟수만큼 인덱스 출력

2) 시간 복잡도

• 평균 시간 복잡도: O(N+K), 공간 복잡도: O(N+K)

정리

• 표준 라이브러리에서 기본으로 제공하는 정렬 라이브러리는 최악의 경우 시간 복잡도가 O(NlogN)을 보장하기 때문에,
  계수 정렬을 사용하는 특이케이스가 아니라면, 파이썬의 정렬 라이브러리를 사용하는 것이 바람직하다.
• 또한 정렬은 다양한 알고리즘에서 사용되는데, 대표적으로 이진탐색과 크루스칼 알고리즘에서 사용된다.