Ch 06. 정렬 알고리즘 (1)

정렬 알고리즘

기본적

• 버블 정렬
• 선택 정렬
• 삽입 정렬

효율적

• 쉘 정렬
• 힙 정렬
• 합병 정렬
• 퀵 정렬

입력 크기 제한 시

• 기수 정렬

내부정렬 VS. 외부정렬

• 내부정렬: 입력의 크기가 주기억 장치 공간보다 크지 않은 경우
• 외부정렬: 입력의 크기가 주기억 장치 공간보다 커서 입력을 여러 번 나누어 주기억 장치에 읽어들인 후 정렬하여 보조기억장치에 다시 저장

6.1 버블 정렬

개념

• 이웃하는 숫자 비교하여 작은 수를 앞쪽으로 이동
• 입력을 전체적으로 한 번 처리하는 것 = 패스(pass)
• 패스 하나 완료 시 큰 값이 먼저 정렬된다.

구현

• Pseudo code
  입력: 크기 n인 배열 A
  출력: 정렬된 배열 A

BubbleSort(A):
	for i in range(n-1, 0, -1):
    	for j in range(0, i):
        	if (A[j] > A[j+1]):
            	A[j], A[j+1] = A[j+1], A[j]
    return A

시간복잡도

$O(n^2)$

---

6.2 선택 정렬

개념

• 입력 배열 전체에서 최솟값 선택하여 배열 0번 원소와 자리 교환
• 다음에는 0번 원소 제외, 나머지 원소에서 최솟값 선택 후 배열 1번 원소와 자리 교환

구현

• Pseudocode
  입력: 크기 n인 배열 A
  출력: 정렬된 배열 A

	SelectionSort(A):
    	for i in range(0, n-1):
        	min = i
            for j in range(i+1, n):
            	if A[j] < A[min]:
                	min = j
            A[i], A[min] = A[min], A[i]
        return A

시간복잡도

$O(n^2)$

• 항상 일정한 시간복잡도
• 입력에 민감하지 않은 알고리즘
• 입력이 거의 정렬되어 있든, 역으로 정렬되어 있든, 랜덤하게 되어 있든 일정하다.
  
  

---

6.3 삽입 정렬

개념

• 배열을 정렬된 부분과 정렬 안 된 부분으로 나누고, 정렬 안 된 부분 최좌측 원소를 정렬된 부분의 적절한 위치에 삽입하여 정렬되도록 하는 과정 반복
• 삽입되면, 정렬된 부분은 +1, 정렬 안 된 부분은 -1
• 첫번째 요소는 정렬되었다고 가정한 뒤 시작한다.

구현

• Pseudocode
  입력: 크기 n인 배열 A
  출력: 정렬된 배열 A

	InsertionSort(A):
    	for i in range(1, n):
        	key = A[i]
            
            j = i-1
            while (j >= 0 and A[j] > key):
            	A[j+1] = A[j]
                j -= 1
            A[j+1] = key
        return A

시간복잡도

• 최악/평균
  $O(n^2)$
• 최선
  $O(n)$
  • 거의 정렬된 입력에 대해서는 다른 알고리즘보다 빠르다.(n-1 번의 비교만 하면 되기 때문에)

6.4 쉘 정렬

개념

• 삽입 정렬 이용, 배열 뒷부분의 작은 숫자를 앞으로 빠르게 이동, 앞부분의 큰 숫자는 뒤로 이동
• 마지막에는 삽입 정렬 수행
• 간격이 중요 - 미리 정해져야 함
  • 가장 큰 간격부터 수행
  • 간격이 1일 경우 일반 삽입 정렬과 같음

과정

시간복잡도

• 최악
  $O(n^2)$
• 히바드 간격 $2^k-1$
  $O(n^{1.5})$
• 간격 선정에 따라 수행속도 좌우
• 입력 크기가 매우 크지 않은 경우에 좋은 성능

6.5 힙 정렬

개념

• (최대)힙 조건: 각 노드의 값이 자식 노드의 값보다 커야 한다.

구현

• Pseudocode
  입력: 입력이 A[1]부터 A[n]까지 저장된 배열 A
  출력: 정렬된 배열 A

	HeapSort(A):
    	배열 A -> 힙 자료구조 만들기
        heapSize = n
        for i in range(1, n):
        	# 루트, 마지막 노드 교환
        	A[1], A[heapSize] = A[heapSize], A[1]
            heapSize -= 1
            DownHeap() #최대힙 재정렬(힙 조건 만족)
        return A

시간복잡도

$O(nlogn)$

6.6 정렬 문제 하한

개념

• k개 단말노드가 있는 이진트리 높이는 $log k$보다 크다.
• $n!$개의 단말노드 가진 결정트리 높이는 $log(n!)$보다 크다.
• $log(n!) = O(nlogn)$이므로, 비교정렬의 하한은 O(nlogn)