[Algorithm] - 정렬

알고리즘이란?

---

가정 : 정렬할 데이터가 담긴 배열(리스트)의 각 원소를 O(1) 시간에 접근 가능한가?

 

결과 : C , Python과 같은 배열인 경우 가능

하지만, 그렇지 않은 경우가 있다.

데이터가 HDD 에 있다면 ? 메인 메모리에 올라와 있어야만 이 가정이 통한다.

 

정렬

---

1. 버블 정렬 

• 시간 복잡도 : O(N^2)
• Stable Sort ( 같은 값이라 하여도 순서를 보장 )

맨 왼쪽 원소부터 바로 이웃한 원소와 비교해 가면서, 큰 수가 오른쪽으로 가도록 교환
이 과정을 다시 나머지 n-1개 수에 대해서 반복

버블 정렬

 

2. 삽입 정렬

• 시간 복잡도 최악의 경우 : O(N^2) , 최상 O(N)
• Stable Sort ( 같은 값이라 하여도 순서를 보장 )

정렬 대상이 될 원소를 두 부분으로 나눔
앞은 '이미 정렬이 된 부분' / 뒤는 '정렬할 부분'

삽입 정렬

 

분할 정복 기법 ( Devide and conquer )

---

3. 병합 정렬 ( Merge Sort )

• 시간 복잡도 O(NlogN)
• 나누는 경우 N -> 1 O(N) / 병합하는 경우 1 -> N O(NK) = O(NlogN)
• 공간 복잡도 = O(N)

오름차순으로 정렬된 두 리스트 A, B의 병합

• 입력의 형태에 상관없이 언제나 같은 시간 복잡도 보장
• 언제나 문제의 크기가 1/2로 줄어듬
• Stable Sort ( 같은 값이라 하여도 순서를 보장 )
• Comparsion sort (값을 비교 )

 

알고리즘

1) A가 비어 있다면 B를, B가 비어 있다면 A를 리턴

2) 그렇지 않다면, 맨 처음 원소를 비교하고 작은 쪽을 리스트에 넣는다.

3) 이 원소를 제거하고 재귀적으로 진행

Merge Sort

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)
 	else:
 		return [B[0]] + merge(A, B[1:])

def mergesort(L): # 재귀
	 if (len(L) == 1): 종료 조건
 		return L
 	return merge(mergesort(L[:int(len(L)/2)]), mergesort(L[int(len(L)/2):]))

 

4. 퀵 정렬 ( Quick Sort )

• 시간 복잡도 : O(n log n) 
• 기준을 첫 번째 원소가 아니라 랜덤
• T(n) = T(99n/100) + T(n/100) + n
• T(n) = T(99n/100) + T(n/100) + n ≤ 99cn/100 log (99n/100) + cn/100 log (n/100) + n = cn log n + 99cn / 100 log (99/100) + cn/100 log (1/100) + n ≤ cn log n
• 정렬 기준이 맨 처음 원소라면 Stable Sort

가장 널리 쓰이는 정렬 알고리즘
핵심 아이디어: 특정 원소를 중심으로 “작은 것” 왼쪽, “큰것” 오른쪽

QuickSort

import random
def randomizedquicksort(L):
 	if (len(L) == 1) or (len(L) == 0):
 		return L
 	pivot = int(random.random() * len(L))
 	left = []
 	right = []
 	for x in L[:pivot]+L[pivot+1:]:
 	if (x < L[pivot]):
 		left.append(x)
 	else:
 		right.append(x)
 	return randomizedquicksort(left) + [L[pivot]] + randomizedquicksort(right)

 

5. Heap Sort

• 시간 복잡도 : O(NlogN)
• Heap 원소 삽입 : log 1 + log 2 + … + log n = O(n log n)
• 병합 : T(n) = 2T(n/2) + log n = O(n)
• Not Stable Sort ( 순서 정보가 힙에 들어가는 과정에서 파괴됨 )

1등을 뽑아내고, 나머지 원소에서 1등을 계속 뽑아내면 정렬 ( 버블 정렬과 차이 : 나머지 원소에서 1등을 뽑을때 다시 비교할 필요 없이 2등이 자동으로 1등이 된다.  )

 

비교에 기반한 정렬들의 한계

트리는 이진트리 -> 두 원소의 비교에 기반한 정렬 알고리즘은 O(n log n)보다 빠르게 동작할 수 없다.

 

6. Bucket Sort

• 시간 복잡도
• 효율적인 경우 -> c개의 버킷으로 모든 원소가 균등하게 배분되어 각각 n/c개가 들어갔을 때 -> n/c개를 O(n/c log (n/c)) = n(log n - log c)
• 몰렸을 경우 -> 하나의 버킷으로 몰렸을 경우

정렬될 데이터가 자릿수라는 개념이 있다면 이를 이용한다.
예를 들어, 정렬될 데이터가 택배 주소라면, 전체를 다 보지 않더라도 처음 위치를 보고 데이터를 분류할 수 있다.

고양시 덕양구 화전동

수원시 영통구 매탄동

인천시 남동구 구월동

서울시 중림구 중림동

 

7. Radix Sort ( 기수 정렬 )

• 시간 복잡도 : O(rn) r은 숫자의 자릿수, n은 정렬될 수
• Stable Sort 

완전히 비교를 제외한 정렬 방법
낮은 자리에서 높은 자리로 기준을 바꾸어 가면서 정렬

import math
def radixsort(L):
 temp = list(L)
 bucket = [[] for _ in range(10)]
 for x in range(int(math.log(max(L), 10))+1):
 bucket = [[] for _ in range(10)]
 for l in temp:
 digit = (l % int(math.pow(10, x+1))) / int(math.pow(10,x))
 bucket[digit].append(l)
 temp = []
 for i in range(len(bucket)):
 temp = temp + bucket[i]
 bucket[i] = []
 return temp
>>> X = [153, 262, 37, 598, 433, 855]

 

8. Counting Sort

• 시간 복잡도 : O(N)
• S가 숫자가 나온 횟수를 세는 테이블이라고 하면, 이 테이블을 다시 읽어야 하기 때문에 정확한 시간 복잡도는 O(n + |S|)

범위가 작은 수들을 빠르게 정렬

알고리즘

1. 각 수가 나온 횟수를 센다.

2. 1의 결과를 이용하여 각 수보다 작은 숫자가 몇 개 있는지 센다.

3. 2의 결과를 이용하면, 특정한 수가 시작하는 위치를 알 수 있다.

Counting Sort