[정보처리기사] 정렬 알고리즘(Sorting Algorithm)

삽입 정렬(Insertion Sort)

삽입 정렬은 두 번째 원소부터 시작하여 그 앞의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입하여 정렬하는 알고리즘이다.

 

 

선택 정렬(Selection Sort)

선택 정렬은 정렬되지 않은 데이터들에 대해 가장 작은 데이터를 찾아 가장 앞의 데이터와 교환해 나가는 방식이다.

 

 

버블 정렬(Bubble Sort)

서로 인접한 두 원소를 검사하여 정렬하는 알고리즘 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환한다. 선택 정렬과 기본 개념이 유사하다.

 

 

퀵 정렬(Quick Sort)

퀵 정렬은 레코드의 많은 자료 이동을 없애고 하나의 파일을 부분적으로 나누어 가면서 정렬하는 방법으로 키를 기 준으로 작은 값은 왼쪽에, 큰 값은 오른쪽 서브파일로 분 해시키는 방식으로 정렬한다.

• 분할(Divide)과 정복(Conquer)을 통해 자료를 정렬한다.
• 평균 수행 시간 복잡도는 O(nlog2n)이고, 최악의 수행 시간 복잡도는 O(n2)이다.

 

힙 정렬(Heap Sort)

힙 정렬은 전이진 트리(Complete Binary Tree)를 이용한 정렬 방식이다.

• 구성된 전이진 트리를 Heap Tree로 변환하여 정렬한다.
• 평균과 최악 모두 시간 복잡도는 O(nlog2n)이다.

 

2-Way 합병 정렬 (Merge Sort)

2-Way 합병 정렬은 이미 정렬되어 있는 두 개의 파일을 한 개의 파일로 합병하는 정렬 방식이다.

• 평균과 최악 모두 시간 복잡도는 O(nlog2n)이다.

 

이분 검색

이분 검색(이진 검색, Binary Search)은 전체 파일을 두 개의 서브파일로 분리해 가면서 Key 레코드를 검색하는 방식이다.

• 이분 검색은 반드시 순서화된 파일이어야 검색할 수 있다.
• 찾고자 하는 Key 값을 파일의 중간 레코드 Key 값과 비교하면서 검색한다.
• 비교 횟수를 거듭할 때마다 검색 대상이 되는 데이터의 수가 절반으로 줄어듦으로 탐색 효율이 좋고 탐색 시간 이 적게 소요된다.
• 중간 레코드 번호 M = (F+L) / 2 (단, F:첫 번째 레코드 2 번호, L : 마지막 레코드 번호)