정렬(Sort)

각 정렬 방식의 주요 특징. 정렬 방식 이해

 

 

1. 삽입정렬(Insertion Sort)

- 가장 간단한 정렬

- n번째 키를 앞의 n-1개의 키와 비교하여 알맞은 순서에 삽입하여 정렬한다.

ex) 3번째 키를 앞의 2개의 키와 비교해 알맞은 순서에 삽입한다.

 

- 평균, 최악 모두 수행 시간 복잡도는: O(n²)

 

 

2.  셸 정렬(Shell Sort)

- 삽입 정렬을 확장한 개념이다. (정렬된 배열에서 삽입정렬은 빠르다.)

- 어떤 매개변수=간격을 기준으로 해당 간격 만큼 떨어져 있는 수와 서로 비교하여 교환을 반복

- 부분적으로 정렬되어 있는 경우에 유리

- 평균: O(n^1.5) / 최악: O(n²)

 

3.  선택 정렬(Selection Sort)

- n개의 레코드 중 최소값을 찾아 첫 번째 레코드 위치에 놓고 (n-1)개 중에서 다시 최소값을 찾아 두 번째에 두는 것을 반복

- 평균 최악 모두: O(n²)

 

4.  버블 정렬(Bubble Sort)

- 인접한 두 개의 레코드 키 값을 비교해 교환함.

- 평균 최악 모두: O(n²)

 

5.  퀵 정렬(Quick Sort)

- 정렬 방식 중에 가장 빠르다.

- 되부름을 이용하기 때문에 스택이 필요

- 분할과 정복을 통해 자료 정렬

- 키값을 기준으로 하나의 파일을 부분적으로 나누어 가며 정렬한다. (키를 기준 작은 값을 왼쪽 큰 값을 오른쪽 파일로)

- 평균: O(nlog₂n) / 최악: O(n²)

 

6.  힙 정렬(Heap Sort)

- 전이진 트리(Complete Binary Tree)를 이용한 정렬 방식

- 전이진 트리를 Heap Tree 로 변환하여 정렬

- 평균 최악 모두: O(nlog₂n)

 

7.  2-way 합병 정렬(Merge Sort)

- 이미 정렬되어 있는 두 개의 파일을 한 개의 파일로 합병하는 것.

- 묶음끼리 정렬

- 평균 최악 모두: O(nlog₂n)

 

7.  기수 정렬(Radix Sort / Bucket Sort)

- 레코드의 키 값을 분석, 같은 수 or 같은 문자끼리

그 순서에 맞는 "버킷"에 분배 하였다가 버킷 순서대로 레코드를 꺼내어 정렬

- 평균 최악 모두: O(dn)

ex)

85

61

77

33

31

8

11

62

최솟값: 8

최댓값: 85

총 데이터 개수: 8

 

예시로 10 단위로 버킷 구성 및 분배

8~18: 8, 11

19~29: x

30~40: 33, 31

41~51: x

52~62: 61, 62

63~74: x

75~85: 85, 77   

각 버킷별로 정렬