정렬 알고리즘
정렬(Sorting)이란 데이터를 특정한 기준에 따라 순서대로 나열한 것을 말한다.
이 포스트 에선 선택 정렬, 삽입 정렬, 큐 정렬, 계수 정렬에 대해 정리하였다.
선택 정렬
처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에있는 데이터의 위치와 바꿔주는 정렬이다.
이런 식으로 반복하면 아래와 같이 정렬이 완료된다.
위 동작을 구현한 코드이다.
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
for i in range(len(array)):
min_index = i # n 번
for j in range(i + 1, len(array)):
if array[min_index] > array[j]:
min_index = j # n - 1
array[i], array[min_index] = array[min_index], array[i] # n - 1 번
print(array)
n(2n-2)
# 결과 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]선택 정렬은 N번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 한다.
만약 위와같인 10개의 정수를 정렬한다고 가정하면 9번만큼 숫자의 위치를 바꿔줘야한다.
처음엔 처음부터 끝까지 10개중 가장 작은걸 찾아야 하기 때문에 10번 확인하고 제일 작은 숫자를 앞으로 보낸 후에는 9번 확인하게 된다. 전체 연산을 수식으로 나타내면 n + (n-1) + (n-2) + ... + 2가 될것이다.
마지막원소는 확인하지 않아도 되기 떄문에 2까지만 확인한다.
마지막 원소를 제외해야 하기 때문에 -> n(n+1)-2/2
첫째항 a = n
마지막항 I = 2
제 n-1까지의 합
n-1(n+2)/2
n^2+n-2/2를 빅오 표기법으로 표현하면 O(N^2)이다.
삽입 정렬
삽입 정렬이란 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입하는 정렬방법이다. 선택정렬에 비해 구현 낭이도가 높은 편이지만, 일반적으로 더 효율적으로 동작한다. 왼쪽의 데이터와 비교해 작으면 왼쪽, 크다면 오른쪽으로 위치를 바꿔주면 된다.
이 동작을 반복하면...
위 동작을 구현한 코드는 아래와 같다.
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):
# 인덱스 i부터 1까지 1씩 감소하며 반복하는 문법
if array[j] < array[j-1]:
array[j], array[j-1] = array[j-1], array[j]
print("if문 에서의 array:",array)
else: #자신보다 작은 데이터를 만나면 그 위치에서 멈춘다.
break
print(array)
#if문 에서의 array: [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]
if문 에서의 array: [5, 7, 0, 9, 3, 1, 6, 2, 4, 8]
if문 에서의 array: [5, 0, 7, 9, 3, 1, 6, 2, 4, 8]
if문 에서의 array: [0, 5, 7, 9, 3, 1, 6, 2, 4, 8]
if문 에서의 array: [0, 5, 7, 3, 9, 1, 6, 2, 4, 8]
if문 에서의 array: [0, 5, 3, 7, 9, 1, 6, 2, 4, 8]
if문 에서의 array: [0, 3, 5, 7, 9, 1, 6, 2, 4, 8]
if문 에서의 array: [0, 3, 5, 7, 1, 9, 6, 2, 4, 8]
if문 에서의 array: [0, 3, 5, 1, 7, 9, 6, 2, 4, 8]
if문 에서의 array: [0, 3, 1, 5, 7, 9, 6, 2, 4, 8]
if문 에서의 array: [0, 1, 3, 5, 7, 9, 6, 2, 4, 8]
if문 에서의 array: [0, 1, 3, 5, 7, 6, 9, 2, 4, 8]
if문 에서의 array: [0, 1, 3, 5, 6, 7, 9, 2, 4, 8]
if문 에서의 array: [0, 1, 3, 5, 6, 7, 2, 9, 4, 8]
if문 에서의 array: [0, 1, 3, 5, 6, 2, 7, 9, 4, 8]
if문 에서의 array: [0, 1, 3, 5, 2, 6, 7, 9, 4, 8]
if문 에서의 array: [0, 1, 3, 2, 5, 6, 7, 9, 4, 8]
if문 에서의 array: [0, 1, 2, 3, 5, 6, 7, 9, 4, 8]
if문 에서의 array: [0, 1, 2, 3, 5, 6, 7, 4, 9, 8]
if문 에서의 array: [0, 1, 2, 3, 5, 6, 4, 7, 9, 8]
if문 에서의 array: [0, 1, 2, 3, 5, 4, 6, 7, 9, 8]
if문 에서의 array: [0, 1, 2, 3, 4, 5, 6, 7, 9, 8]
if문 에서의 array: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
# 결과 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]삽입 정렬의 시간 복잡도는 O(N^2)이다. 선택 정렬과 마찬가지로 반복문이 두번 중첩되어 사용한다.
삽입 정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다.
최선의 경우는 O(N)의 시간 복잡도를 가진다.
퀵 정렬
퀵 정렬은 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법이다. 일반적인 상황에서 가장 많이 사용하는 정렬 알고리즘중 하나로 병합 정렬과 더불어 대두분 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘이다. 
위 과정으로 분할 된 데이터를 보면 왼쪽은 기준이었던 5보다 작은 값으로 이루어져 있고 오른쪽은 모두 5보다 큰 값으로 구성되었다.
이렇게 나누어진 데이터를 재귀를 통해 다시 퀵정렬을 진행한다.
위 과정을 재귀적으로 계속 반복해 정렬을 완료한다.
퀵 정렬이 빠른 이유
이상적인 경우로 예를 들어보면 데이터가 분할될때 마다 데이터의 범위를 절반에 가깝게 분할시킬 수 있다면 퀵정렬의 시간복잡도는 O(NlogN)을 기대할 수 있다.
단순하게 생각해 전체 데이터를 반반씩 분할된다고 생각해보자.
이상적인 경우 데이터의 범위가 절반씩 줄어드게 되기때문에 전체 높이를 확이했을때는 logN이라고 볼 수있다.
또한 데이터의 범위가 절반씩 줄어들기 때문에 logN에서 log는 밑이 2인 logN이라고 할 수 있다.
구현 코드는 아래와 같다.
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)재귀함수가 어떻게 동작하고 어떤식으로 정렬이 이루어 지는지 한줄 한줄 살펴보면서 이해했다.
pivot: 0 left: 1 right: 9
left <= right : True
.........................
처음 들어온 l,r: 1 9
while 이후 l, r : 1 8
else 문에서 array: [5, 4, 9, 0, 3, 1, 6, 2, 7, 8]
left <= right : True
.........................
처음 들어온 l,r: 1 8
while 이후 l, r : 2 7
else 문에서 array: [5, 4, 2, 0, 3, 1, 6, 9, 7, 8]
left <= right : True
.........................
처음 들어온 l,r: 2 7
while 이후 l, r : 6 5
if 문에서 array: [1, 4, 2, 0, 3, 5, 6, 9, 7, 8]
재귀1 quick_sort(array, 0, 4)시작
pivot: 0 left: 1 right: 4
left <= right : True
.........................
처음 들어온 l,r: 1 4
while 이후 l, r : 1 3
else 문에서 array: [1, 0, 2, 4, 3, 5, 6, 9, 7, 8]
left <= right : True
.........................
처음 들어온 l,r: 1 3
while 이후 l, r : 2 1
if 문에서 array: [0, 1, 2, 4, 3, 5, 6, 9, 7, 8]
재귀1 quick_sort(array, 0, 0)시작
재귀1 quick_sort(array, 0, 0)종료
재귀2 quick_sort(array, 2, 4)시작
pivot: 2 left: 3 right: 4
left <= right : True
.........................
처음 들어온 l,r: 3 4
while 이후 l, r : 3 2
if 문에서 array: [0, 1, 2, 4, 3, 5, 6, 9, 7, 8]
재귀1 quick_sort(array, 2, 1)시작
재귀1 quick_sort(array, 2, 1)종료
재귀2 quick_sort(array, 3, 4)시작
pivot: 3 left: 4 right: 4
left <= right : True
.........................
처음 들어온 l,r: 4 4
while 이후 l, r : 5 4
if 문에서 array: [0, 1, 2, 3, 4, 5, 6, 9, 7, 8]
재귀1 quick_sort(array, 3, 3)시작
재귀1 quick_sort(array, 3, 3)종료
재귀2 quick_sort(array, 5, 4)시작
재귀2 quick_sort(array, 5, 4)종료
________________________
재귀2 quick_sort(array, 3, 4)종료
________________________
재귀2 quick_sort(array, 2, 4)종료
________________________
재귀1 quick_sort(array, 0, 4)종료
재귀2 quick_sort(array, 6, 9)시작
pivot: 6 left: 7 right: 9
left <= right : True
.........................
처음 들어온 l,r: 7 9
while 이후 l, r : 7 6
if 문에서 array: [0, 1, 2, 3, 4, 5, 6, 9, 7, 8]
재귀1 quick_sort(array, 6, 5)시작
재귀1 quick_sort(array, 6, 5)종료
재귀2 quick_sort(array, 7, 9)시작
pivot: 7 left: 8 right: 9
left <= right : True
.........................
처음 들어온 l,r: 8 9
while 이후 l, r : 10 9
if 문에서 array: [0, 1, 2, 3, 4, 5, 6, 8, 7, 9]
재귀1 quick_sort(array, 7, 8)시작
pivot: 7 left: 8 right: 8
left <= right : True
.........................
처음 들어온 l,r: 8 8
while 이후 l, r : 9 8
if 문에서 array: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
재귀1 quick_sort(array, 7, 7)시작
재귀1 quick_sort(array, 7, 7)종료
재귀2 quick_sort(array, 9, 8)시작
재귀2 quick_sort(array, 9, 8)종료
________________________
재귀1 quick_sort(array, 7, 8)종료
재귀2 quick_sort(array, 10, 9)시작
재귀2 quick_sort(array, 10, 9)종료
________________________
재귀2 quick_sort(array, 7, 9)종료
________________________
재귀2 quick_sort(array, 6, 9)종료
________________________
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]계수 정렬
계수 정렬은 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작하는 정렬 알고리즘으로 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능하다. 조건으로 데이터의 개수가 N, 데이터(양수)중 최댓값이 K일 때 최악의 경우에도 수행 시간 O(N + K)를 보장한다.
계수 정렬에 대한 설명은 위 그림에 잘 설명되어있다.
# 모든 원소의 값이 0보다 크거나 같다고 가정
array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]
# 모든 범위를 포함하는 리스트 선언(모든 값은 0으로 초기화)
count = [0] * (max(array) + 1)
for i in range(len(array)):
count[array[i]] += 1 # 각 데이터에 해당하는 인덱스의 값 증가
for i in range(len(count)): # 리스트에 기록된 정렬 정보 확인
for _ in range(count[i]):
print(i, end='')문제 : 두 배열의 원소 교체
문제의 조건중 원소가 최대 100,000개 까지 입력될 수 있다고 했음으로, 최악의 경우 O(NlogN)을 보장하는 정렬 알고리즘을 이용해야 한다.
n,k = map(int, input().split())
print(n, k)
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a.sort()
b.sort(reverse=True)
# 내가 푼 방법
# a[0:k] = b[0:k]
# print(sum(a))
#아래는 해설 강의
for i in range(k):
if a[i] < b[i]:
a[i],b[i] = b[i], a[i]
print(sum(a))