정렬 문제
n개의 서로 다른 수가 주어졌을 때, 이들을 이동하여 점점 커지게, 또는 점점 작아지게 만드는 문제.
-> 한 문제를 풀기 위해서 여러가지 방법이 가능
-> 방법마다 특징이 다름
-> 기본적인 문제이면서, 실생활에 자주 쓰임
-> 시간 복잡도, 최적성에 대해서 증명이 쉬움(당장은 이해가 제대로 안되도 괜찮음)
-> 이후 예제에서는, 정수를 오름차순으로 정렬하는 문제를 풀기로 함.
반론
-> 정렬은 다 남들이 짜놓은 코드가 있는데?
대응
-> 자동차 운전 면허에서 법규 구조는 왜 배우나?
-> 컴퓨터의 구조, 문제 해결의 원리를 이해하는 것은 중요하며, 정렬이라는 문제의 예를 통해서 이를 배운다.
-> 원리를 이해하면 풀고자 하는 문제에 적합한 답을 낼 수 있다.
-> 그렇지만, 남이 짜 놓은 코드를 정확하게 이용할 수 있는 것도 중요하다!
가정
- 정렬할 데이터가 담긴 배열의 각 원소를 O(1) 시간에 접근 가능하다.
당연한거 아닌가요?
-> C에서 배열이라면 당연함.
-> 당연하지 않은 경우가 있음. 만약 데이터가 HDD에 있다면? 메인메모리에 비해 HDD, SSD는 느림.
-> 어떤 데이터를 가져오는데는 시간이 거의 안걸리지만, 또 다른 데이터를 가져오는데는 엄청난 시간이 걸릴 수 있다.
-> Big Data에서는 당연한 가정이 안통한다.
-> 앞으로 알고리즘에서 다루는 모든 문제는, 데이터가 메인 메모리에 저장되어 있다고 가정함.
버블 정렬
- 맨 왼쪽 원소부터 바로 이웃한 원소와 비교해 가면서, 큰 수가 오른쪽으로 가도록 교환함.
- 맨 끝까지 가면 가장 큰 원소를 찾은 것이므로, 이 과정을 다시 나머지 n-1개 수에 대해서 반복.
버블 정렬의 정확성
-
정확성은 보이기 쉽다.
-> 제일 큰 원소가 제일 뒤.
-> 그 다음 큰 원소가 그 앞 -
시간 복잡도
-> 처음 가장 큰 원소를 구할 때 n-1번 비교
-> 두번째 큰 원소를 구할 때 n-2번 비교
-> (n-1) + (n-2) + … + 1 = n(n-1)/2 = Θ(n2)
-> 입력과 무관하게, n개의 값을 정렬할 때 항상 똑같은 횟수의 비교를 수행함
def bubblesort(L):
result = list(L)
for x in range(len(result)-1):
for y in range(len(result)-x-1):
if (result[y] > result[y+1]):
result[y], result[y+1] = result[y+1], result[y]
return result
>>> A = list(range(20))
>>> import random
>>> random.shuffle(A)
>>> bubblesort(A)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]삽입 정렬(insertion sort)
- 정렬 대상이 될 원소를 두 부분으로 나눔
-> 앞은 '이미 정렬이 된 부분' : 정렬이 이 자체로 끝났다는 뜻이 아니고, 앞 부분에 있는 원소는 오름차순을 만족한다는 뜻임
-> 뒤는 '정렬할 부분'
-> 매번 정렬할 부분의 가장 첫번째 원소를 정렬이 된 부분에 삽입을 한다.
-> 삽입은 정렬된 부분의 가장 큰 원소부터 오른쪽으로 비교해나가면서 진행한다.
-> 포커를 칠 때, 보통 카드를 쭉 훑어보고 순서대로 정렬한다.
삽입 정렬의 정확성
- 이미 정렬된 부분은 항상 정렬이 되어 있다.
- 처음에는 정렬된 부분에 원소 1개
-> 1개의 원소는 그 자체가 정렬되어 있다. - 매번, 정렬할 부분의 원소 1개를 이미 정렬된 부분으로 옮긴다.
-> 정렬할 부분은 처음 n-1개의 원소를 갖고 있다.
-> 매번 1개씩 감소하므로, 최종적으로는 정렬된 부분에 n개, 정렬할 부분에 0개의 원소가 있다.
-> 정렬된 부분은 정렬이 되어 있으므로 최종적인 정답은 정렬된 상태임.
def insertsort(L):
temp = list(L)
result = []
while (len(temp) > 0):
m = temp.pop(0)
result.append(m)
for i in range(1,len(result))[::-1]:
#포문에서 i를 거꾸로 세주는 것.
if (result[i] < result[i-1]):
result[i], result[i-1] = result[i-1], result[i]
else:
break
return result
>>> A = range(20)
>>> import random
>>> random.shuffle(A)
>>> insertsort(A)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]삽입 정렬의 시간 복잡도
-
가장 좋을 때: 이미 오른차순으로 정렬되어 있을 때
-> 정렬된부분에 원소를 넣을 때마다, 비교를 한번만 하면 됨.
-> 총 n-1번 = Θ(n) -
최악의 경우: 역순으로 정렬된 수들을 정렬할 때
-
i번째 위치의 원소를 정렬된 부분에 추가할 때 (즉, 이미 정렬된 부분에 i-1개의 원소가 있을 때) i-1개의 원소와 모두 비교
-
i=2, 3, ... , n이므로 1 + 2 + ... + n-1 = n(n-1)/2 = Θ(n2)
삽입 정렬의 평균 시간 복잡도
- i개의 정렬된 부분에 i+1 번째 원소를 삽입할 때
-> 정렬된 부분이 1개일때부터, i개일때까지 계속 넣을것임.
-> i+1 등할 확률은 1/(i+1) 이고, 비교는 1번
-> 1등할 확률은 1/(i+1) 비교는 i번
-> n^2/4 ≤ n(n-1)/4 + (n-1) - {1/2 + 1/3 + … + 1/n} ≤ 5n^2/4
O(n^2) 보다 빠르게 정렬할 수 있는가?
- 인접한 두 원소를 교환하는 방식의 정렬 알고리즘은 O(n^2)보다 빨리 정렬할 수 없다.(=최적이다)
-증명
-> 바로 인접한 두 원소를 교환하는게 아니라, 서로 떨어져있는 원소를 교환할 경우가 아니고서는 O(n^2)가 최선이다.(분할 정복 기법)\
분할 정복 기법(Divide-and-Conquer)
- 착안점: 문제의 크기가 커지면 더 풀기가 어렵다.
병합 정렬(Mergesort)
- 알고리즘의 기본 아이디어
-> 정렬할 리스트를 앞 뒤로 쪼개어 나눈뒤, 따로따로 정렬하여 합친다. 약간 재귀식으로다가..? 계속 쪼개서 정렬하고 합치고, 정렬하고 합치고를 반복
def merge(A, B):
if (len(A) == 0):
return B
if (len(B) == 0):
return A
if (A[0] < B[0]):
return [A[0]] + merge(A[1:], B)
#A[1:] 이거 때문에 A가 하나씩 계속 감소하는 것을 알 수 있음
else:
return [B[0]] + merge(A, B[1:])병합의 정확성
- 병합 과정이 정확하게 두 리스트를 정렬하는지에 대한 정확성 증명
- 기본 경우
-> A,B 둘 중 하나가 비어 있는 경우
-> 나머지 하나는 이미 정렬되어 있으므로 병합 결과는 그 자신. - 알고리즘의 진행
-> 전체 리스트의 앞의 반, 뒤의 반을 병합 정렬을 통해서 정렬
def mergesort(L):
if (len(L) == 1):
return L
return merge(mergesort(L[:int(len(L)/2)]), mergesort(L[int(len(L)/2):]))병합 정렬의 시간 복잡도
- 실제 정렬은
-> 맨 마지막에는 원소 하나를 가지는 리스트 (이미 정렬됨)
-> 정렬된 리스트를 연속으로 병합, 최종 단계에서 정렬 완료 - 점화식
-> T(n) = 2T(n/2) + n, T(n) = Θ(n log n)
-> n/2개의 리스트 2개를 정렬하고, 이를 합치는데 n번 비교 - 특징
-> 입력의 형태에 상관없이 언제나 같은 시간 복잡도 보장
-> 언제나 문제의 크기가 1/2로 줄어듬. (참고: 퀵 정렬)
-> 실제로는 원소들이 더 자주 움직이므로 시간이 더 많이 걸림
-> 퀵 정렬의 경우, 일단 순서가 정해진 원소는 움직이지 않는다.
퀵 정렬(Quciksort)
- 가장 널리 쓰이는 정렬 알고리즘
- 핵심 아이디어
-> 특정 원소를 중심으로 "작은 것" 왼쪽, "큰 것" 오른쪽
-> "왼쪽" 과 "오른쪽" 의 순서와 무관하게, 이 원소의 순서는 결정된다.
