[알고리즘] 정렬 정리

정렬 → 이보다 표준 정렬 라이브러리 사용 ( sort() )

1. 선택정렬 - 가장 작은 데이터를 선택해 맨앞의 데이터와 바꾸는 것을 반복

• 탐색 범위는 반복할때마다 줄어듬 ( 2중 for문 ) → 시간 복잡도 O(N^2)

array = [7,5,9,0,1,3,6,2,4,8]
for i in range(len(array)):
# i는 가장 작은 idx-> 맨 앞으로 보낼 것
	min_idx = i # 가장 작은 워소 = i, i의 idx의미
	for j in range(i+1, len(array)):
		if array[min_idx] > array[j]:
			min_idx = j
	
	array[i],array[min_idx] = array[min_idx],array[i]
print(array)

2. 삽입정렬 - 데이터를 골라 적절할 위치에 삽입

• 시간 복잡도 O(N^2) , 최선의 경우 O(N) - 이미 오름차순이 되어 있을때

array = [7,5,9,0,1,3,6,2,4,8]
# 2번째 데이터부터 확인
for i in range(1,len(array)):
	for j in range(i,0,-1): # idx = i ~ 1까지 1씩 감소하며 반복
		#j는 삽입하고자 하는 원소
		if array[j] < array[j-1]: # 한칸씩 왼쪽으로 이동
			array[i],array[j-1] = array[j-1],array[i]
		else: # 자기보다 작은데이터 만나면 그 위치에서 멈춤
			break 
	
print(array)

3. 퀵 정렬 - 기준 데이터를 정하고, 그 기준보다 큰 데이터와 작은 데이터 위치 교환

• 시간 복잡도 O(NlogN), 최악 O(N^2)
• 대부분에 적합함
• 첫번째 데이터를 기준 데이터를 pivot 값으로 분할한다
• 재귀적이며, 수행을 반복할수록 범위가 줄어든다.
  • 분할을 할수록 절반으로 범위가 줄어든다

# way1) splicing과 컴프리헨션없는 버전
array = [7,5,9,0,1,3,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)

# way2 )splicing & 컴프리헨션 있음
array = [7,5,9,0,1,3,6,2,4,8]
def quick_sort(array):
	#리스트가 1개 이하 원소
	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)w
print(quick_sort(array))

4. 계수 정렬 → 동일한 값이 여러개 등장시 효과적이다

• 특정 조건 부합시 매우 빠르게 동작
• 데이터 크기 범위가 제한되어, 정수형태로 표현 가능할때 사용
• 데이터 개수 N, 최댓값 K → O(N+K)
• 각 데이터가 몇개 있는지 체크 → idx로 count 증가

array =[7,5,9,0,3,1,6,2,9,1,4,8,0,5,2]
count = [0] * (max(array)+1) # 0~9의 숫자이므로 10개의 박스 필요

for i in range(len(array)):
	count[array[i]] += i  # 각 데이터의 해당 idx 증가 -> O(N)
	# 1씩 증가

for i in range(len(count)): # O(N+K) , 리스트에 기록된 정렬 정보 확인
	for j in range(count[i]):
		print(i, end=' ')

문제1) 두 배열의 원소 교체

수행과정

• 두배열 A,B가 N개의 원소로 존재
• 두배열의 원소를 교체후, A의 원소 합을 최댓값 만들기

idea

• A의 가장 작은 원소랑 B의 가장 큰 원소를 교체

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