정렬알고리즘

정렬 알고리즘은 주어진 데이터 집합을 특정한 기준에 따라 순서대로 정렬하는 알고리즘이다.

어떻게 정렬할 수 있을까?

[선택정렬]

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

이 알고리즘의 핵심 아이디어는 매번 정렬되지 않은 부분에서 최소값을 찾아서 앞으로 이동시키는 것입니다. 이를 통해 배열의 가장 작은 요소가 정렬 과정 중에 제 위치를 찾아가게 되고, 나머지 요소들도 동일한 원리로 정렬됩니다.

선택 정렬 동작 예시

[Step 0] 처리되지 않은 데이터 중 가장 작은 ‘0’을 선택해 가장 앞의 ‘7’과 바꾼다.

[Step 1] 처리되지 않은 데이터 중 가장 작은 ‘1’을 선택해 가장 앞의 ‘5’와 바꾼다.

[Step 2] 처리되지 않은 데이터 중 가장 작은 ‘2’를 선택해 가장 앞의 ‘9’와 바꾼다.

[Step 3] 처리되지 않은 데이터 중 가장 작은 ‘3’을 선택해 가장 앞의 ‘7’과 바꾼다.

이러한 과정을 반복하면 다음과 같이 정렬이 완료된다.

→ 가장 작은 것을 선택해서 앞으로 보내는 과정을 반복해서 수행하다 보면, 전체 데이터의 정렬이 이루어진다.

선택정렬 소스 코드

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]

선택 정렬의 시간 복잡도

선택 정렬의 시간 복잡도는 O(n^2)로, 배열의 크기에 비례하여 비효율적입니다. 그러나 선택 정렬은 구현이 간단하고 이해하기 쉬우며, 정렬해야 할 요소의 수가 상대적으로 작을 때 유용할 수 있습니다.

선택 정렬은 N번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 한다.
구현 방식에 따라서 사소한 오차는 있을 수 있지만, 전체 연산 횟수는 다음과 같다.

이는 (*N^*2+N+2)/2로 표현할 수 있는데, 빅오 표현법에 따라서 O(*N^*2)이라고 작성한다.

[삽입정렬]

삽입 정렬의 핵심 아이디어는 정렬된 부분 배열에 새로운 원소를 삽입하는 동안 정렬된 순서를 유지한다는 것입니다. 따라서, 배열이 이미 거의 정렬되어 있는 경우에는 효율적으로 동작하며, 작은 규모의 입력에 대해서도 성능이 좋습니다.

처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입한다.
선택 정렬에 비해 구현 난이도가 높은 편이지만, 일반적으로 더 효율적으로 동작한다.

삽입 정렬 동작 예시

[Step 0] 첫 번째 데이터 ‘7’은 그 자체로 정렬이 되어 있다고 판단하고, 두 번째 데이터인 ‘5’가 어떤 위치로 들어갈지 판단한다. ‘7’의 왼쪽으로 들어가거나 오른쪽으로 들어가거나 두 경우만 존재한다.

[Step 1] 이어서 ‘9’가 어떤 위치로 들어갈지 판단한다.

‘9’는 차례대로 왼쪽에 있는 데이터와 비교해서 왼쪽 데이터보다 더 작다면 위치를 바꿔 주고 그렇지 않다면 그냥 그 자리에 머물러 있도록 한다. ‘9’는 ‘7’보다 더 크기 때문에 현재 위치 그대로 내버려 둔다.

[Step 2] 이어서 ‘0’이 어떤 위치로 들어갈지 판단한다.

‘0’은 ‘9’, ‘7’, ‘5’와 비교했을 때 모두 작기 때문에 ‘5’의 왼쪽에 위치한다.

이러한 과정을 반복하면 다음과 같이 정렬이 완성된다.

삽입 정렬 소스코드

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):
			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)입니다. 여기서 n은 배열의 크기를 나타냅니다. 또한, 삽입 정렬은 제자리 정렬(in-place sorting) 알고리즘이므로, 추가적인 메모리 공간을 필요로 하지 않습니다.

삽입 정렬의 시간 복잡도는 O(*N^*2)이며, 선택 정렬과 마찬가지로 반복문이 두 번 중첩되어 사용된다.
삽입 정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다.최선의 경우 O(N)의 시간 복잡도를 가진다.

[퀵정렬]

기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법이다.
일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나이다.
병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘이다.
가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(pivot)로 설정한다.

퀵 정렬 동작 예시

[Step 0] 현재 피벗의 값은 ‘5’이다. 왼쪽에서부터 ‘5’보다 큰 데이터를 선택하므로 ‘7’이 선택되고, 오른쪽에서부터 ‘5’보다 작은 데이터를 선택하므로 ‘4’가 선택된다.

[Step 1] 현재 피벗의 값은 ‘5’이다. 왼쪽에서부터 ‘5’보다 큰 데이터를 선택하므로 ‘9’가 선택되고, 오른쪽에서부터 ‘5’보다 작은 데이터를 선택하므로 ‘2’가 선택된다. 이제 이 두 데이터의 위치를 서로 변경한다.

[Step 0]현재 피벗의 값은 ‘5’이다. 왼쪽에서부터 ‘5’보다 큰 데이터를 선택하므로 ‘6’이 선택되고, 오른쪽에서부터 ‘5’보다 작은 데이터를 선택하므로 ‘1’이 선택된다. 단, 이처럼

위치가 엇갈리는 경우 ‘피벗’과 작은 데이터의 위치를 서로 변경한다.

[분할완료]이제 ‘5’의 왼쪽에 있는 데이터는 모두 5보다 작고, 오른쪽에 있는 데이터는 모두 ‘5’보다 크다는 특징이 있다. 이렇게 피벗을 기준으로 데이터 묶음을 나누는 작업을 분할(Divide)이라고 한다.

[왼쪽 데이터 묶음 정렬]왼쪽에 있는 데이터에 대해서 마찬가지로 정렬을 수행한다.

[오른쪽 데이터 묶음 정렬]오른쪽에 있는 데이터에 대해서 마찬가지로 정렬을 수행한다.

이러한 과정을 반복하면 전체 데이터에 대해서 정렬이 수행된다.

퀵 정렬이 빠른 이유: 직관적인 이해

이상적인 경우 분할이 절반씩 일어난다면 전체 연산 횟수로 O(NlogN)를 기대할 수 있다.
너비 X 높이 = N X logN = NlogN

퀵 정렬의 시간 복잡도

퀵정렬은 평균적으로 O(n log n)의 시간 복잡도를 가지지만, 최악의 경우에는 O(n^2)의 시간 복잡도를 가질 수 있습니다. 최악의 경우는 피벗이 항상 최솟값 또는 최댓값으로 선택되는 경우에 발생합니다. 이러한 경우를 피하기 위해 피벗을 랜덤하게 선택하거나 중간값을 선택하는 방법 등을 사용할 수 있습니다.

퀵 정렬은 평균의 경우 O(NlogN)의 시간 복잡도를 가진다.
하지만 최악의 경우 O(N2)의 시간 복잡도를 가진다.

첫 번째 원소를 피벗으로 삼을 때, 이미 정렬된 배열에 대해서 퀵 정렬을 수행할 경우 최악의 경우이다.

표준 라이브러리를 사용하는 경우, 기본적으로 O(NlogN)을 보장한다.

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

def quick_sort(array, start, end):
	if start >= end:
		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)

[실행 결과]

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

문제 - 두 배열의 원소 교체

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

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

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

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

예를 들어 N = 5, K = 3이고, 배열 A와 B가 다음과 같다고 해보자

배열 A = [1, 2, 5, 4, 3]

배열 B = [5, 5, 6, 6, 5]이 경우, 다음과 같이 세 번의 연산을 수행할 수 있다

연산 1) 배열 A의 원소 ‘1’과 배열 B의 원소 ‘6’을 바꾸기

연산 2) 배열 A의 원소 ‘2’와 배열 B의 원소 ‘6’을 바꾸기

연산 3) 배열 A의 원소 ‘3’과 배열 B의 원소 ‘5’를 바꾸기세 번의 연산 이후 배열 A와 배열 B의 상태는 다음과 같이 구성될 것이다

배열 A = [6, 6, 5, 4, 5]

배열 B = [3, 5, 1, 2, 5]이때 배열 A의 모든 원소의 합은 26이 되며, 이보다 더 합을 크게 만들 수는 없다

입력

첫 번째 줄: N, K 가 공백으로 구분되어 입력 (1 <= N <= 100,000, 0 <= K <= N)
두 번째 줄: 배열 A의 원소들이 공백으로 구분되어 입력 (원소 a < 10,000,000인 자연수)
세 번째 줄: 배열 B의 원소들이 공백으로 구분되어 입력 (원소 b < 10,000,000인 자연수)

출력

최대 K번 바꿔치기 연산을 수행해서 가장 최대의 합을 갖는 A의 모든 원소 값의 합을 출력

입력 예시

5 3
1 2 5 4 3
5 5 6 6 5

출력 예시

코드 구현

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[i], b[i] = b[i], a[i]
  else:
    break

print(sum(a))

실행 결과