정렬 알고리즘

Ⅰ. 정렬 알고리즘

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

① 선택 정렬

• 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸기

• 선택 정렬은 N번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 합니다.

• 전체 연산 수 = $N + (N-1) + (N-2) + ... + 2$

• $(N^2 + N -2) / 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[i] 

print(array)

② 삽입 정렬

• 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입

• 선택 정렬에 비해 구현이 어렵지만 더 효율적으로 동작

• 삽입 정렬의 시간 복잡도는 $O(N^2)$ 이다. (반복문 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): # 인덱스 i부터 1까지 1씩 감소하며 반복하는 문법
        if array[j] < array[j - 1]: # 한 칸씩 왼쪽으로 이동
            array[j], array[j - 1] = array[j - 1], array[j]
        else: # 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
            break

print(array)

③ 퀵 정렬

• 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾼다.

• 일반적인 상황에서 많이 사용되는 정렬 알고리즘

• 병합 정렬과 더불어 정렬 라이브러리의 근간이 되는 알고리즘

• 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(Pivot)로 설정

• 퀵 정렬의 평균적인 시간 복잡도는 $O(NlogN)$

• 최악의 경우 $O(N^2)$

파이썬 구현

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

④ 계수 정렬

• 특정한 조건을 만족할 때만 사용할 수 있지만 매우 빠르게 동작하는 정렬 알고리즘

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

• 데이터 개수가 $N$, 양수 데이터 중 최대값이 $K$일때 최악의 경우에 시간 복잡도와 공간 복잡도는 모두 $O(N+K)$

• 동일한 값을 가지는 데이터가 여러 개 등장할 때 효과적으로 사용 가능

파이썬 구현

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

위의 선택정렬 등의 코드를 작성해서 사용하기보다 파이썬에서 기본으로 제공하는 표준 라이브러리 list.sort( ) 등을 사용하는 것이 보통 빠르고 효율적입니다.

Ⅱ. 예제

① 두 배열의 원소 교체

❔ 문제 설명

두 개의 배열 A, B를 가지고 있습니다. 두 배열은 N개의 원소로 구성되어 있으며 배열의 원소는 모두 자연수입니다.

동빈이는 최대 K번의 바꿔치기 연산을 수행할 수 있는데, 바꿔치기 연산이란 배열 A에 있는 원소 하나와 배열 B에 있는 원소 하나를 골라서 두 원소를 서로 바꾸는 것을 말합니다.

최종 목표는 배열 A의 모든 원소의 합이 최대가 되도록 하는 것입니다.

N,K 그리고 배열 A, B가 주어졌을 때, 최대 K번의 바꿔치기 연산을 수행하여 만들수 있는 배열 A의 모든 원소의 합의 최대값을 출력하는 프로그램을 작성하세요.

💡 문제 해결 아이디어

• 매번 배열 A에서 가장 작은 원소를 골라서, 배열 B에서 가장 큰 원소와 교체합니다.

• 가장 먼저 배열 A, B가 주어지면 A에 대하여 오름차순 정렬하고, B에 대하여 내림차순 정렬합니다.

• 이후에 두 배열의 원소를 첫 번째 인덱스부터 차례로 확인하면서 A의 원소가 B의 원소보다 작을 때에만 교체를 수행합니다.

• 이 문제에서는 두 배열의 원소가 최대 100,000개까지 입력될 수 있으므로, 최악의 경우 $O(NlogN)$을 보장하는 정렬 알고리즘을 이용해야 합니다.

✔️ 풀이

Python

n, k = map(int, input().split()) # N과 K를 입력 받기
a = list(map(int, input().split())) # 배열 A의 모든 원소를 입력받기
b = list(map(int, input().split())) # 배열 B의 모든 원소를 입력받기

a.sort() # 배열 A는 오름차순 정렬 수행
b.sort(reverse=True) # 배열 B는 내림차순 정렬 수행

# 첫 번째 인덱스부터 확인하며, 두 배열의 원소를 최대 K번 비교
for i in range(k):
    # A의 원소가 B의 원소보다 작은 경우
    if a[i] < b[i]:
        # 두 원소를 교체
        a[i], b[i] = b[i], a[i]
    else: # A의 원소가 B의 원소보다 크거나 같을 때, 반복문을 탈출
        break

print(sum(a)) # 배열 A의 모든 원소의 합을 출력