쉽게 배우는 알고리즘-04정렬

정렬 알고리즘 

-대부분 O(n^2) ~ O(nlogn)

-기초 정렬 알고리즘 → 평균적으로 O(n^2) ; 선택, 버블, 삽입 정렬(이미 정렬된 상태일때는 삽입 O(n))

-고급 정렬 알고리즘 → 평균적으로 O(nlogn) : 퀵, 힙, 병합 정렬(퀵은 worst case일때 O(n^2))

-input이 특수한 성질을 만족하는 경우에는 O(n) sorting도 가능

 

Ⅰ. 기초 정렬 알고리즘 

1) 선택정렬

-최대원소 찾기 → 최대원소와 맨 오른 쪽 원소 교환 → 맨 오른쪽 원소 제외

-하나의 원소만 남을 때 까지 반복

선택 정렬

 

2) 버블 정렬

- 인접한 두 원소를 비교하면서 제일 큰 원소를 끝자리로 옮김

버블 정렬 

3) 삽입 정렬

-이미 정렬되어 있는 i개 짜리 배열에 하나의 원소를 더 더하여 i+1개 짜리 배열을 만드는 과정 반복

-이미 모두 정렬되어 있는 배열이라면 O(n)

삽입 정렬

Ⅱ. 고급 정렬 알고리즘 

1) 병합 정렬 

병합 정렬

 

2) 퀵정렬 

 ①기준원소를 선택

 ② 기준원소를 중심으로 더 작거나 같은 수는 왼쪽에 배치

     기준원소를 중심으로 큰 수는 오른쪽으로 재배치

 ③ 분할된 왼쪽 부분 배열을 따로 퀵정렬 분할된 오른쪽 부분 배열을 따로 퀵정렬

 

Best: 분할이 항상 반반씩 균등하게 될 때

           T(n) = 2 T(n/2) + n → Θ (n log n)

Worst: 한쪽은 하나도 없고 다른쪽에 다 몰리게 분할 될 때

            T(n) = T(n-1) + n → Θ (n^2 )

Average: T(n) = T(i-1) + T(n-i) + n → Θ (n log n)

 

3)힙정렬

- 각 노드의 값은 자신의 children의 값보다 크지않다.

- 주어진 배열을 힙으로 만든 다음, 차례로 하니씩 힙에서 제거함으로써 정렬한다

- 제거할 때는 가장 마지막 원소를 위로 올림

힙 정렬

Ⅲ. 특수 정렬

▶ Θ (n) 정렬

- 두 원소를 비교하는 것을 기본 연산으로 하는 정 렬의 하한선은 Ω (nlogn)이다.

- 그러나 원소들이 특수한 성질을 만족하면 Θ(n) 정렬도 가능하다 

    ① 계수정렬Counting Sort

        :원소들의 크기가 모두 –O(n) ~ O(n) 범위에 있을 때

    ② 기수정렬Radix Sort

         :원소들이 모두 k 이하의 자릿수를 가졌을 때 (k: 상수

 

1) 기수 정렬

- 입력이 모두 k 자리수 이하의 자연수인 특수한 경우에 사용 가능한 방법

- 안정성 정렬(Stable Sort)

   : 같은 값을 가진 원소들은 정렬 후에도 원래의 순서가 유지되는 성질을 가진 정렬

 

2) 계수 정렬 

- 정렬하고자 하는 원소들의 값이 O(n)을 넘지 않는 경우에 사용

   예) 배열 A[1..n]의 원소들이 k를 넘지 않는 자연수의 경우

- 음수값은 처리하지 못하나 중복된 값에 대해서도 잘 처리할 수 있음

 

알고리즘 효율성 비교