[알고리즘] 정렬 알고리즘 간단 정리

Selection Sort

O(n^2), min 값을 순차적으로 비교하면서 min값 찾고 min 값을 맨 앞으로 고정시키며 n-1 줄여가면서 반복

---

Bubble Sort

바로 옆에 있는 숫자와 비교하여 순차적으로 비교 후, ascending, desending 에 따라 swapping

부등호를 바꿔 ascending, decending 를 바꿀 수 있음

 

from random import shuffle

def bubble(list):
	tmp = 0
	for i in range(len(list)):
		for j in range(len(list)-i-1):
			if ( list[j]>list[j+1] ):
				tmp = list[j+1]
				list[j+1] = list[j]
				list[j] = tmp


list = list(range(10))
shuffle(list)
print (list)
bubble(list)
print (list)

'''
[1, 7, 9, 6, 4, 5, 8, 2, 0, 3]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[Finished in 0.4s]
'''

Bubble은 Selection Array보다 더 비효율적. 바로 옆에 값과 비교하기 때문에 계속해서 자리를 바꾸는 연산을 수행함

⇒ 즉, 적은 수를 찾아 마지막에만 Swapping 하는게 아니고 매번 바꿔줘야 하므로 선택정렬보다 수행시간이 훨씬 더 크다.

---

Insertion Sort → Best O(N)

O(n^2)의 정렬 중 그나마 효율적, 내 자리가 어디인지 찾아가는 것

ex) 1,10,2,6 일 때, [1, 2, 10, 6] → [1, 2, 6, 10] 등 최선의 경우 O(n) 까지 나올 수 있음

ex) 2, 3, 4, 5, 6, 7, 8, 9, 10, 1 인 경우는 10까지 사실상 거의 어떤 연산도 수행하지 않고 지나가기 때문에, O(N)의 시간복잡도가 나올 수 있음

---

Quick Sort

from random import shuffle

def quickSort(arr):
	if( len(arr)<=1 ):
		return arr
	else:
		pivot = arr[0] 
		low = [ x for x in arr[1:] if pivot>x ]
		high = [ x for x in arr[1:] if pivot<x ]
		return quickSort(low) + [pivot] + quickSort(high)

arr = list(range(1000000))
shuffle(arr)
print quickSort(arr)

3, 7, 8, 1, 5, 9, 6, 10, 2, 4

3, 2, 8, 1, 5, 9, 6, 10, 7, 4

3, 2, 1, 8, 5, 9, 6, 10, 7, 4

1, 2, 3, 8, 5, 9, 6, 10, 7, 4 (pivot <-> min)

1, 2, 3, 8, 5, 9, 6, 10, 7, 4 (분할의 기준 = 3)

1, 2, 3, 8, 5, 4, 6, 10, 7, 9

1, 2, 3, 8, 5, 4, 6, 7, 10, 9

1, 2, 3, 7, 5, 4, 6, 8, 10, 9 (pivot <-> min)

1, 2, 3, 7, 5, 4, 6, 8, 10, 9

1 2 3 7 5 4 6 8 9 10

1 2 3 7 5 4 6 8 9 10

1 2 3 4 7 5 6 8 9 10 (분할기준4)

1 3 2 4 5 9 6 8 7

1 2 3 4 5 6 7 8 9

3 1 5 4 2 6

3 1 2 4 5 6

2 1 3 4 5 6

1 2 3 4 5 6 (2=분할기준 pivot이 제일 작으면 본인이 분할기준이 됨)

1 2 3 4 5 6

1 2 3 4 5 6

작으면 본인이 분할 기준

---

Merge Sort

Quick sort와는 다르게 편향으로 분할할 가능성이 없어 O(n*log_2N)을 보장함

사전에 묶인것은 이미 정렬되어있다고 가정(!)

---

Heap Sort

전제조건 : 완전 이진 트리 유지 및 최대 힙 구조 가져야함

빨간색 박스 → 최대 힙 구조가 아님

따라서 자식 노드 중 루트보다 큰 걸 바꿔줘야 함(heapify ⇒ 부모는 자식보다 커야한다)

 

Heapify 시간복잡도는 트리의 높이로 결정됨. 즉, n이 5개라면, 대략 시간복잡도는 log25 = 약 3 정도이며, 이는 트리의 높이와 거의 유사함.

 

N=1024이라고 해도 log21024 = 10 정도이므로, 시간복잡도는 상당히 짧음.

아래처럼, 5개 n에 대해 각각 log2N만큼 시간을 사용하므로, 힙정렬의 시간복잡도 또한 앞서 퀵정렬 병 합정렬과 같이 nlog2n이 됨.

여기에서, 트리의 구조상 실제로는, 5개의 데이터가 있는 트리의 ½만 Heapify를 수행하면 됨. 그러므로 실제 시간복잡도는 ½ * n * log2n임. 결과적으로 시간복잡도는 **O(n)**이 됨.

• 1/2 개만 보면 되는 인 이유 → leaf 볼 필요 X

 

• 인덱스 0부터 시작하는 경우
  • 왼쪽 자식 노드 = 2 * 부모 노드 + 1
  • 오른쪽 자식 노드 = 2 * 부모 노드 + 2
• 인덱스 1부터 시작하는 경우
  • 왼쪽 자식 노드 = 2 * 부모 노드
  • 오른쪽 자식 노드 = 2 * 부모 노드 + 1