꺼내먹는지식 준
정렬 본문
정렬이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것이다.
이진탐색을 위해서는 정렬 알고리즘으로 데이터를 정렬하는 것이 선 과정이다.
다음의 알고리즘을 알아보자.
- 선택 정렬
- 삽입 정렬
- 퀵 정렬
- 계수 정렬
1) 선택정렬
데이터가 무작위로 있을 때, 이 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두번째 데이터와 바꾸는 과정을 반복한다.
매번 가장 작은 것을 '선택'하므로 선택 정렬 알고리즘이라 한다.
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
def swap(x,y):
tmp = x
x = y
y = tmp
return x, y
for i in range(len(array)):
minimum = 1e9
for j in range(i, len(array)):
if array[j] < minimum:
minimum = array[j]
minv = j
array[minv], array[i] = swap(array[minv], array[i])
# array[minv], array[i] = array[i], array[minv]
print(array)사실상 swap 을 구현하지 않고 단순하게 array[minv], array[i] = array[i], array[minv] 해도 상관 없다.
그리고 minimum 을 직접 저장하지 않고 index 를 저장하면 줄을 조금 더 줄일 수 있다.
가장 작은 수를 찾는 시간: N + (N-1) + .. + 2
가장 작은 수를 앞으로 보내는 시간: N - 1
$N (N+1) / 2 - 1 + N - 1$
$= \frac{N^2+3N - 4}$
$= O(N^2)$
2) 삽입정렬
선택 정렬은 느리다. 그렇다면 데이터를 하나씩 확인하면서, 각 데이터를 적절한 위치에 삽입하면 어떨까?
array = [7,5,9,0,3,1,6,2,4,8]
for i in range(1,len(array)):
for j in range(i-1, -1, -1): #i-1 부터 0까지
if array[i] > array[j]:
tmp = array.pop(i)
array.insert(j+1, tmp)
break
elif j == 0 and array[j] > array[i]:
tmp = array.pop(i)
array.insert(0, tmp)
print(array)개념을 그대로 살려서 위치를 바로바로 바꾸지 않고 자신보다 큰 값을 만났을 때 말그대로 빼고 insert 하도록 알고리즘을 짰다.
다만 0 번째 index 까지 오면 가장 작은 것이므로 0에 insert 하고, 그때 첫 시작이라 j가 0 인 경우는 예외처리하도록 했다.
알고리즘을 짜고 보니 논리적인 듯 하나, 실제로는 훨씬 간단하게 짤 수 있다. 그냥 단순하게 더 작으면 자리를 바꾸고 작지 않으면 자리를 바꾸지 않는 것이다. 솔직히 내 알고리즘이 매번 바꾸는 과정이 빠져있어 조금 더 효율적일 듯 하다.
똑같이 $O(N^2)$ 이나 만약 거의 정렬되어 있는 상태라면 매우 빠르게 최선의 경우에는 $O(N)$ 으로 동작한다.
※(코딩 테스트에서 정렬된 list 에 원소 하나를 추가하여 정렬할때면 우리는 sort 를 쓰지 않고 앞뒤 값 비교해서 적절한 위치에 원소를 넣는다. 인지하지 않고 삽입 정렬을 수행한 것이다. )
3) 퀵 정렬
퀵 정렬과 곧 배울 병합 정렬은 프로그래밍 언어에서 정렬 라이브러리의 근간이 된다.
퀵 정렬은 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작한다.
퀵 정렬에는 피벗(pivot)이 사용된다. 큰 수와 작은 수를 교환할 때 교환에 필요한 기준을 피벗이라 한다.
피벗의 설정 방식과 리스트를 분할하는 방법에 따라서 여러 방식으로 퀵 정렬을 구분한다.
지금부터 언급할 퀵 정렬은 가장 대표적인 분할 방식인 호어 분할 반식이다.
호어분할방식
리스트에서 첫 번째 데이터를 피벗으로 정한다.
간단하게 정리해보자면,
1) 첫 element를 pivot으로 하고, pivot 다음값을 left, array의 최종 값을 right 로 한다.
2) left 와 right 를 각각 pivot 과 비교하며 left 는 pivot 보다 큰 값일 때 까지, right 는 pivot 보다 작은 값일때까지 포인트를 각각 +1, -1 즉 하나씩 움직인다.
3) 조건을 만족하는 left 와 right 는 위치를 변경해준다.
4) 그러다가 조건을 만족한 left 와 right 가 만약 교차하게 되면 작은 값 즉 right의 값과 pivot 값의 위치를 바꿔준다. (그렇게 하면 옮겨진 pivot 값을 기준으로 왼쪽은 pivot 보다 모두 작고 오른쪽은 pivot 보다 모두 크다.)
5) 재귀 함수를 2개 이용하여, 동일한 과정을 수행한다.
(pivot 을 기준으로 한 함수는 start ~ right - 1(pivot) 까지, 한 함수는 right +1(pivot) ~ end 로 설정하면 된다.)
6) 종료 조건은 재귀 함수를 돌던 array 의 수가 1 이 된 경우이다.
array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]
def qsort(start, end, array):
if len(array) == 1:
return
pivot = start
left = pivot + 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[pivot], array[right] = array[right], array[pivot]
else:
array[left], array[right] = array[right], array[left]
qsort(start ,right-1, array)
qsort(right+1, end, array)
qsort(0, len(array)-1, array)
print(array)
잘 받아들이기 어려웠던 부분이 바로 left <= right 이다.
while(left <= right)코드를 돌려본 결과 = 를 빼면
[0, 1, 2, 3, 4, 5, 6, 8, 7, 9]
정렬이 완료되지 않는다.
8,7 을 정렬하기 위해 start 는 8 의 index 인 7, end 는 8이다.
left의 index는 7+1 로 8
while 문에서 left < right 이면 left와 right 이 동일 한 지금같은 경우 문제가 발생한다. 이에 따라 등호를 넣어줘야 한다.
pivot = 8(index 7), left = 7 (index 8), right = 7 (index 8), start = 8 (index 7), end = 7 (index 8)
while left <= end and array[left] < array[pivot]:
left += 1
while right >= start and array[right] > array[pivot]:
right -= 1left += 1 즉, index 9
if left > right:
array[pivot], array[right] = array[right], array[pivot]pivot 과 right 의 위치가 잘 바뀌므로 문제 없이 종료.
퀵 정렬은 시간 복잡도가 $O(N \log N)$이다. 머지 정렬은 사실 알고보면 퀵 정렬이랑 유사하므로 생략한다.
4) 계수 정렬
계수 정렬은 특정한 조건이 부합할 때만 사용할 수 있으나 매우 빠른 정렬 알고리즘이다.
모든 데이터가 양의 정수라면, 계수 정렬은 최악의 경우에도 수행 시간 $O(N + K)$ 를 보장한다. (데이터 개수 N, 데이터 중 최댓 값 K)
계수 정렬은 '데이터의 크기 범위가 제한 되어 정수 형태로 표현할 수 있을 때' 만 사용 가능하다.
데이터 값이 무한한 범위를 가질 수 있는 실수형 데이터가 주어지는 경우 계수 정렬은 사용하기 어렵다.
또한 일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000 을 넘지 않을 때 효과적이다.
예를 들어 성적 0 ~ 100 데이터를 정렬할 때 계수 정렬이 효과적이다.
계수 정렬의 이러한 특징은 '모든 범위를 담을 수 있는 크기의 리스트를 선언' 해야 하기 때문이다.
계수정렬의 알고리즘은 굉장히 간단하다.
1) 들어온 값 가장 작은 값과 큰 값으로 범위를 지정하여 list 를 생성한다. (초기 값 0)
2) 각 element 를 돌면서 해당하는 list index 에 +1
3) list 의 value 를 확인하며 0이 아니면 value 크기만큼 순서대로 나열하면 된다.
element 를 도는 데 걸리는 시간 N
list 확인하며 나열하는 시간 K
array = [7,5,9,0,3,1,6,2,9,1,4,8,0,5,2]
#실제로는 이미 min 과 max 를 알고있는 경우일 수도 있다.
#그리고 연속적인 값일 수도 있다.
#상황에 따라 조금 씩 다를듯 하다.
lst = [0] * (max(array) + 1 )
for i in array:
lst[i] += 1
ans = ''
for i,c in enumerate(lst):
ans += str(i) * c
파이썬 정렬 LIBARAY
파이썬 기본 정렬 라이브러리 sorted() 함수는 병합 정렬 기반이다. 병합 정렬은 일반적으로 퀵 정렬보다 느림에도 최악의 경우에도 $O(N\log N)$ 을 보장한다는 장점이 있다.
sort 는 따로 반환하는 값 없이 inplace 로 적용된다.
sorted, sort 모두 key 를 매개변수로 입력받는다.
key 를 통해 (바나나, 2) 이러한 형태의 원소에서 어떤 값을 기준으로 정렬을 해야 하는지 정해줄 수 있다.
reverse 를 매개변수로 오름 내림 차순도 가능하다.
또한 key 에 lambda 적용도 가능하다.
예제
1) 성적이 낮은 순서로 학생 출력하기
(강호동, 99) 왼쪽과 같은 형태로 이름과 점수가 들어온다.
점수가 낮은 순으로 이름을 나열하라.
import sys
input = sys.stdin.readline
N = int(input())
lst = []
for i in range(N):
name, score = input().split()
lst.append((name,int(score)))
ans = sorted(lst, key = lambda x: x[1])
for i in ans:
print(i[0], end = ' ')2) 두 배열의 원소 교체
배열 A,B 가 주어진다. 최대 K 번의 원소 바꿔치기를 통해 A 배열의 최대 합을 구하여라.
import sys
input = sys.stdin.readline
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):
A[i] = B[i]
print(sum(A))'코딩테스트총정리' 카테고리의 다른 글
| 다이나믹 프로그래밍 (0) | 2022.08.10 |
|---|---|
| 탐색 (순차, 이진) (0) | 2022.08.06 |
| DFS, BFS (0) | 2022.08.03 |
| 구현 (0) | 2022.08.02 |
| 그리디 (0) | 2022.07.29 |
