[알고리즘] 3-4. 분할 정복을 이용한 정렬 (3)

비교 정렬

1. 데이터 간 상대적 크기 관계를 이용해 정렬

2. 데이터 간 크기 관계가 정의되어 있을 경우 적용 가능

3. 버블정렬, 삽입정렬, 합병정렬, 퀵정렬, 힙정렬

 

논-비교 정렬

1. 정렬할 데이터에 대한 사전지식 이용

2. Bucket Sort (버킷 정렬)

3. Radix Sort (기수 정렬)

 

하한

1. 입력된 데이터 한번씩 보기 위해 O(n) 시간복잡도 필요

2. 합병정렬과 힙정렬 알고리즘 시간복잡도 : O(nlog2n)

3. O(nlog2n)이 가장 빠른 비교정렬

 

결정 트리

1. Leaf 노드 수 : n!개

2. 최악의 경우 시간복잡도 (트리의 높이)

 :height >=log2n!=O(nlog2n)

 

선형 시간 정렬 알고리즘

 

Counting Sort (세는 정렬)

-> 배열의 각 정수의 개수 카운트

 

COUNTING-SORT (A, B, k)
 for i <- 0 to k
  do C[i] <- 0
 for j <- 1 to length[A]
  do C[A[j]] <- C[A[j]] +1
  //C[i] now contains the number of elements equal to i
  
 for i <- 1 to k
  do C[i] <- C[i] + C[i01]
  //C[i] now contains the number of elements less than or equal to i
  
  for j <- length[A] downto 1
   do B[C[A[j]]] <- A[j]
    C[A[j]] <- C[A[j]] -1

 

기수 정렬

: n개의 d자리 정수들을 가장 낮은 자리수 부터 정렬

[일의 자리 부터 정렬하고, 십의 자리, 백의 자리 순으로 정렬]

 

RADIX-SORT (A,d)
 for i <- 1 to d
  do use a stable sort to sort array A to digit i

버블 정렬 삽입 정렬 선택 정렬	O(n^2)
퀵 정렬	최악 : O(n^2), 평균 : O(nlog2n)
합병 정렬	O(nlog2n)
힙 정렬	O(nlog2n)
세는 정렬 기수 정렬	O(n+k) O(d(n+k))