(4) 정렬 알고리즘
정렬이란 데이터를 특정한 기준에 따라 순서대로 나열하는 것을 말함
일반적으로 문제 상황에 따라 적절한 정렬 알고리즘이 공식처럼 사용됨
✔️ 알고리즘은 앞선 벨로그 정리에서 더 상세히 다루었으므로 간단히만 정리 ! !
선택 정렬
처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복
이는 이중 for문으로 구현이 가능함
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 값보다 더 작은 값이 존재한다면
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-1) + (N-2) + (N-3) ,... = (N^2 + N -2)/2
➡️ O(N^2)
삽입 정렬
처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입하는 정렬
선택 정렬에 비해 구현 난이도가 높은 편이지만, 일반적으로 더 효율적으로 동작
이중 for문으로 구현이 가능함
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): # j가 i부터 1까지 1씩 감소
if array[j] < array[j-1]: # 값이 크면 자리 스와핑
array[j], array[j-1] = array[j-1],array[j]
else:
break
print(array)실행 결과 위와 동일
시간 복잡도: O(N^2), 최선의 경우 O(N)
삽입 정렬은 현재 리스트가 거의 정렬된 상태일 경우 매우 빠르게 동작
퀵 정렬
기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법
일반적인 상황에서 가장 많이 사용되며, 병합 정렬과 더불어 대부분의 프로그래밍 언어 정렬 라이브러리의 근간이 되는 알고리즘
➡️ 표준라이브러리의 정렬 사용시 시간 복잡도가 O(NlogN) 나온다고 생각하기
가장 기본적으로 첫 번째 데이터를 기준 데이터로 설정
시간 복잡도: 분할이 절반씩 이루어진다면 전체 연산 횟수로 O(NlogN)을 기대
최악의 경우 편향된 분할을 가지므로 O(N^2)
파이썬의 경우 리스트 슬라이싱과 컴프리헨션을 이용하여 간결한 표현이 가능
array = [7, 5, 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)를 보장함
- 단 공간 복잡도도 함께 O(N+K)
- 계수 정렬은 때에 따라서 심각한 비효율성 초래 가능(데이터가 0와 99999만 존재)
- 동일한 값을 가지는 데이터가 여러 개 등장할 때 효과적
각 원소의 개수를 count한 뒤에 인덱스를 반복해 출력
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 9, 1, 4, 8, 0, 5, 2]
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 4 5 5 6 7 8 9 9
정렬 알고리즘 비교하기
문제 예시
두 배열의 원소 교체를 정렬 알고리즘의 예시로 들 수 있음
-
두 개의 배열 A와 B가 있을 때, 두 배열은 N개 원소로 이루어져 있으며 배열의 원소는 모두 자연수임
-
최대 K번의 바꾸기 연산이 가능함. 바꾸기 연산이란 배열 A에 있는 원소 하나와 배열 B에 있는 원소 하나를 골라 두 원소를 바꾸는 것
-
최종 목표는 배열 A의 모든 원소의 합이 최대가 되도록 하는 것
-
최대 K번의 바꾸기 연산을 수행하여 만들 수 있는 배열 A의 모든 원소의 합의 최댓값을 출력하는 프로그램 작성
➡️ 이 문제는 매번 배열 A에서 가장 작은 원소를 골라, 배열 B에서 가장 큰 원소와 교체. 그러려면 배열 A는 오름차순, B는 내림차순 정렬하여 첫번째 인덱스부터 차례대로 크기를 확인하면서 교체. 이때 배열 B의 원소가 A의 원소보다 클 ㄸㅐ만 교체 수행
✔️ 두 배열의 원소가 최대 100,000개 까지 입력될 수 있으므로, 최악의 경우 O(NlogN)을 보장하는 정렬 알고리즘을 사용해야 시간초과 X
n,k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a.sort() # 오름차순 정렬
b.sort(reverse=True) # 내림차순 정렬
for i in range(k):
if a[i] < b[i]: # a의 원소가 b의 원소보다 작을 경우
a[i], b[i] = b[i], a[i] # 두 원소 교체
else:
break
print(sum(a))실행 결과: 26
