-
[알고리즘] 정렬 정리알고리즘 2022. 9. 16. 15:01728x90
정렬 → 이보다 표준 정렬 라이브러리 사용 ( 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))
'알고리즘' 카테고리의 다른 글
[알고리즘] 최단경로 정리 (1) 2022.09.26 [알고리즘] 이진 탐색 정리 (1) 2022.09.16 [알고리즘] 구현 정리 (0) 2022.09.16 [알고리즘] dfs / bfs 정리 (0) 2022.09.16 [알고리즘] 그리디 정리 (0) 2022.09.16