Algorithm _#7 정렬 알고리즘

정렬(sorting) 알고리즘

: 리스트(배열)의 값을 오름차순으로 재배치

• 목표: 비교 횟수 + 교환횟수 최소화
• 내장함수
  • A.sort() : 오름차순
  • A.sort(reverse = True) : 내림차순

• 성질:

  1. stable vs unstable

     • stable: 같은 숫자가 중복되어 있을 때 원본의 순서 유지

     • unstable: 같은 숫자가 중복되어 있을 때 원본의 순서 유지 X

       

  2. in-place vs not in-place

     • in-place: 추가 메모리가 O(1)정도
     • not in-place: 추가 메모리가 O(n)정도

기본 알고리즘

-> (n-1)번의 round를 가지며 매 round마다 한 숫자를 sort

selection

1. max찾기 :(n-1)번 비교
2. max를 리스트의 맨 뒤의 값과 swap

def selection_sort(A, n) #A[0]~ A[n-1]까지 insertion sort
	for i in range(1, n): # round i에 i번째 작은 수 찾음
		j = i -1
		while j >= 0 and A[j]> A[j+1]:
			A[j], A[j+1] = A[j+1], A[j]
			j = j - 1

• 비교 횟수:

​ (비교) 매 라운드마다 비교 횟수: (n-1) +(n-2) + …. + 1 = n(n-1)/2

​ +(교환) swap : (n-1) *1

​ => O(n^2)

bubble

1. 2개씩 비교

2. 더 큰 값이 뒤로 가게 swap

   => max값이 맨 뒤로 가게

def bubble_sort(A,n):
	for i in range(n): #큰 수를 차례대로 찾음
		for j in range(1,n):
			if A[j-1] > A[j] #A[n-1]~A[j] 인접한 수 비교 후 swap
				A[j-1], A[j] = A[j], A[j-1]

• 비교 횟수:

  ​ (비교) 매 라운드 마다 비교 횟수: (n-1) + (n-2) + … + 1 = n(n-1)/2

  +(교환) 최댓값이 맨 마지막 자리: (n-1) + (n-2) +…+ 1 = n(n-1)/2

  => O(n^2)

insertion

1. 리스트 맨 앞 2개와 그 다음 값을 비교하여 자리 찾기
2. 그 다음 맨 앞 3개와 다음값..

=> 점점 비교할 대상을 늘려가며 다음 수와 비교하여 자리 찾기

• 비교횟수:

  (비교) 매 라운드 마다 비교 횟수: (n-1) + (n-2) + … + 1 = n(n-1)/2

  +(교환) 최댓값이 맨 마지막 자리: (n-1) + (n-2) +…+ 1 = n(n-1)/2

  => O(n^2)

각각 stable인지 in-place한지 따져보기!

Heap 자료구조와 heap sort 알고리즘

heap sort 알고리즘

def sort(A): #n = len(A)
	for i in range(n-1, -1, -1):
		m, idx = get-max(A,i) # A[0]...A[i]최대값, 인덱스 리턴
		A[idx], A[i] = A[i], A[idx] #A[idx]와 A[i] swap

• make_heap

  

  (n-1) * heapify-down

  = O(nlogn) -> O(n)가능

• heapify-down

  def heapify_down(self, k, n):
  	# n = 힙 전체 노드 수
  	while 2*k+1 < n:
  		L, R = 2*k + 1, 2*k +2
  		if L < n and self.A[L] > self.A[k]:
  			m = L
  		else:
  			m = k
  		if R < n and self.A[R]> self.A[m]:
  			m = R
  		if m != k:
  			self.A[k], self.A[m] = self.A[m], self.A[k]
  			k = m
  		else:
  			break
  

  => 수행시간은 A[k]가 내려온 레벨 수에 비례

  : O(logn)

• deleteMax

  -> max return & delete

  A[0]와 A[n-1] swap
  n = n-1 # 또는 A.pop() 하고 m = A[n-1]식으로 저장
  heapify-down(A[0])
  return A[n-1]
  

  :O(logn)

• heap-sort

  :O(nlogn)

• 수행시간

  for (n-1)번:
  	A[0] 와 A[n-1] swap
  	heapify-down(A[0]) # O(logn)
  	n = n - 1
  

  get-max(A,i): heap 사용 => O(logi) = O(logn)*(n-1)

  =>O(nlogn)

in-place & unstable

Heap 자료구조

: 배열, 리스트를 이진트리로 생각

• 성질

  1. 왼쪽자식, 오른쪽자식, 부모를 O(1)시간 내에 찾을 수 있음

  2. 모양: 이진트리

  3. 힙성질: 부모노드 key값 >= 자식노드의 key값

     => root node: 최대값

  A[k]의 왼쪽 노드: A[2*k + 1]

  A[k]의 오른쪽 노드: A[2*k + 2]

  A[k]의 부모노드: A[(k-1) /2]