[알고리즘] 정렬 알고리즘

 

 

 

이 글은 동빈나 님의 이코테 강의를 정리한 글입니다.

 

 

 

1. 선택 정렬 (Selection Sort)

✨ 정의

처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복합니다.

 

 

✨ 동작 예시

 

 

✨ 구현

 

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

 

 

✨ 시간 복잡도

• N번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 합니다.
  따라서, 전체 연산 횟수는 $N + (N - 1) + (N - 2) + \cdots + 2  = \frac{(N^2 + N - 2)}{2}$이므로 $O(N^2)$의 시간 복잡도를 가집니다.

 

 

 

2. 삽입 정렬 (Insertion Sort)

✨ 정의

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

• 선택 정렬에 비해 구현 난이도가 높은 편이지만, 일반적으로 더 효율적으로 동작합니다.

 

 

✨ 동작 예시

 

 

 

✨ 구현

 

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

 

 

✨ 시간 복잡도

• 반복문이 두 번 중첩되어 사용되므로 시간 복잡도는 $O(N^2)$ 입니다.
• 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작하므로, 최선의 경우  $O(N)$의 시간 복잡도를 가집니다.   

 

 

 

3. 퀵 정렬 (Quick Sort)

✨ 정의

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

• 일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나로, 병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘입니다.
• 가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준으로 기준 데이터(Pivot)로 설정합니다.

 

 

✨ 동작 예시

 

 

 

✨ 구현

 

array = [7, 5, 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[right] <= 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[right], array[left] = array[left], array[right]

    # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
    quick_sort(array, start, right - 1)
    quick_sort(array, right + 1, end)
    
quick_sort(array, 0, len(array) - 1)    
print(array)    # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

 

 

✨ 시간 복잡도

• 평균적인 경우에는 $$O(N \log N)의 시간 복잡도를 가지나, 최악의 경우에는 $O(N^2)$의 시간 복잡도를 가집니다.

 

 

 

4. 계수 정렬 (Counting Sort)

✨ 정의

특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작하는 정렬 알고리즘으로, 
데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능합니다.

 

 

✨ 동작 예시

 

 

 

✨ 구현

 

# 모든 원소의 값이 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= " ")  # 띄어쓰기를 구분으로 등장한 횟수만큼 인텍스 출력 
                            # 0 0 1 1 2 2 3 4 5 5 6 7 8 9 9

 

 

✨ 복잡도

• 시간 복잡도와 공간 복잡도 모두$O(N + K)$입니다.
• 경우에 따라서 심각한 비효율성을 초래할 수 있습니다. → 데이터가 0과 999,999로 단 2개만 존재하는 상황
• 동일한 값을 가지는 데이터가 여러 개 등장할 때 효과적으로 사용할 수 있습니다. 

 

 

 

5. 정렬 알고리즘 비교

 

 

 

 

6. 문제

✨ 두 배열의 원소 교체

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

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

동빈이의 최종 목표는 배열 A의 모든 원소의 합이 최대가 되도록 하는 것이며, 여러분은 동빈이를 도와야 합니다.

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

 

• 아이디어: 매번 배열 A에서 가장 작은 원소를 골라서 배열 B에서 가장 큰 원소와 교체한다.
  
  • 배열 A에 대해 오름차순 정렬하고, 배열 B에 대해 내림차순 정렬한다.
  • 이후 두 배열의 원소를 첫 번째 인덱스부터 차례로 확인하면서 A의 원소가 B의 원소보다 작을 때에만 교체를 수행한다.

 

• 답안

 

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