정렬 기법

1. 선택 정렬 :: selection sort
2. 삽입 정렬 :: insertion sort
3. 퀵 정렬 :: quick sort
4. 병합 정렬 :: merge sort
5. 계수 정렬 :: count sort
6. ...

 

# 1. 선택 정렬 :: Selection Sort  - O(N^2)

- 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 
   그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾼다. 

- 가장 원시적인 방법으로 매번 '가장 작은 것을 선택' 한다는 의미에서 선택 정렬 알고리즘이라 한다.

 

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

for i in range(len(arr)):
    min_index = i

    for j in range(i+1, len(arr)):
        if arr[min_index] > arr[j]:
            min_index = j

    arr[i], arr[min_index] = arr[min_index], arr[i]

 

 

 

# 2. 삽입 정렬 :: Insertion Sort  -  기본 O(N^2),  최선 O(N)

'데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입한다.'

- 필요할 떄만 위치를 바꾸므로 '데이터가 거의 정렬되어 있을 때' 훨씬 효율적이다. 

 

- 선택 정렬은 현재 데이터의 상태와 상관없이 무조건 모든 원소를 비교하고 위치를 바꾸는 반면 삽입 정렬은 그렇지 않다. 

- 특정한 데이터를 적절한 위치에 '삽입' 한다는 의미에서 '삽입 정렬'이라 한다. 

 

- 특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정한다. 

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

 

- 재미있는 특징은, 정렬이 이루어진 원소는 항상 오름차순을 유지하고 있다는 점이다. 

- 따라서 위 특징 덕분에, 삽입될 위치를 찾기 위해 왼쪽으로 한 칸씩 이동할 때, 자신보다 작은 데이터를 만나면 거기서 멈추면 된다.

 

- 보통은 삽입 정렬이 비효율적이지만, 정렬이 거의 되어 있는 상황에서는 퀵 정렬 알고리즘보다 더 강력하다. 

- 따라서 거의 정렬되어 있는 상태로 입력이 주어지는 문제라면 삽입 정렬을 이용하는 것이 정답 확률을 높일 수 있다. 

 

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

for i in range(1, len(arr)):
    for j in range(i, 0, -1):       # 인덱스 i부터 1까지 감소하며 반복
        if arr[j-1] > arr[j]:           # 앞에야 나보다 크면 자리 바꾸자
            arr[j-1], arr[j] = arr[j], arr[j-1]
        else:                       # 앞에야 나보다 작네 거기 있어라
            break

 

 

# 3. 퀵 정렬

'기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸자'

 

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

- 원리를 이해하면 병합 정렬, 힙 정렬 등 다른 고급 정렬 기법에 비해 쉽게 소스코드를 작성할 수 있다.

 

- 퀵 정렬에서는 피벗(pivot)이 사용된다. 교환하기 위한 '기준'을 피벗이라고 표현한다.

 

- 피벗을 설정하고 리스트를 분할하는 방법에 따라 여러가지 방식으로 퀵 정렬을 구분한다.

- 대표적인 분할 방식은 Hoare Partition 이다. 

- Hoare Partition : 리스트에서 첫 번째 데이터를 피벗으로 정한다.

 

- 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다. 

- 그 다음 큰 데이터와 작은 데이터를 서로 교환한다. 

- 진행 방향이 서로 만나 엇갈리면, '피벗'과 '작은 데이터'의 위치를 서로 변경한다.

- 이러한 과정을 거치면 '피벗'에 대하여 정렬이 수행된다.  

 

- 퀵 정렬에서는 특정한 리스트에서 피벗을 설정하여 정렬을 수행한 이후에, 피벗을 기준으로 왼쪽 리스트와 오른쪽 리스트에서 각각 다시 정렬을 수행한다.

- 퀵 정렬은 '재귀 함수' 형태로 작성했을 때 구현이 매우 간결해진다. 그렇다면 '종료 조건'은?

- 재귀함수의 종료 조건 : 현재 리스트의 데이터 개수가 1개인 경우 

 

* 시간복잡도

1. 최선의 경우 : O(N log N)

- 피벗 값의 위치가 변경되어 분할이 일어날 때마다 정확히 왼쪽 리스트와 오른쪽 리스트가 절반씩 분할 될 때

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

- 이미 데이터가 정렬되어 있는 경우

 

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

def quick_sort(arr, start, end):
    if start >= end:    # 원소가 1개인 경우 종료
        return

    pivot = start       # 일단 피벗은 첫번째 원소 (by Hoare Partition)
    left, right = start+1, end

    while left <= right:
        while left <= end and arr[left] <= arr[pivot]:  # 피벗보다 큰 데이터를 찾을 때 까지 반복
            left += 1
        while right > start and arr[right] >= arr[pivot]:
            right -= 1

        if left > right:            # 엇갈렸다면 작은 데이터와 피벗을 교체
            arr[right], arr[pivot] = arr[pivot], arr[right]
        else:                       # 엇갈리지 않았다면 작은 데이터와 피벗을 교체
            arr[left], arr[right] = arr[right], arr[left]

    # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
    quick_sort(arr, start, right-1)
    quick_sort(arr, right+1, end)


quick_sort(arr, 0, len(arr)-1)

 

 

# 4. 합병 정렬

'하나의 리스트를 2개의 균등한 크기로 분할하고, 분할된 부분 리스트를 정렬한 다음, 2개의 정렬된 부분 리스트를 다시 합병'

 

- 추가적인 리스트 필요

- 각 부분 배열을 정렬할 때도 합병 정렬을 재귀적으로 호출

 

- 일반적으로 퀵 정렬보다 느리지만 최악의 경우에도 O(N log N)을 보장한다. 

 

def merge(left, right):
    res = []

    while len(left) > 0 or len(right) > 0:
        if len(left) > 0 and len(right) > 0:
            if left[0] < right[0]:
                res.append(left[0])
                left = left[1:]

            else:
                res.append(right[0])
                right = right[1:]

        elif len(left) > 0:
            res.append(left[0])
            left = left[1:]

        elif len(right) > 0:
            res.append(right[0])
            right = right[1:]

    return res


def merge_sort(arr):
    n = len(arr)

    if n <= 1:
        return arr

    mid = n // 2

    left_list = merge_sort(arr[:mid])
    right_list = merge_sort(arr[mid:])

    return merge(left_list, right_list)

arr = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
arr = merge_sort(arr)

 

 

# 5. 계수 정렬 :: count sort

- 데이터의 개수가 N, 데이터 중 최댓값이 K 일 때, 계수 정렬은 최악의 경우에도 수행 시간 O(N+K)를 보장한다. 

 

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

    - 보통은 문제에서 입력 조건에 1 <= N <= 1,000,000 처럼 값의 범위를 제한할 것이다. 

 

- int형 변수 1백만개는 4MB 밖에 되지 않으니, 메모리 걱정을 하지 말자. 

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

 

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

# 모든 범위를 포함하는 리스트를 선언한다.
count = [0] * (max(arr) + 1)

for i in range(len(arr)):
    count[arr[i]] += 1      # 각 데이터에 해당하는 인덱스의 값 증가

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