정처기 #12 정렬

1 ) 정렬의 시간 복잡도

 

2 ) 선택 정렬(Selection Sort)

• 오름차순으로 정렬하였을 때 가장 작은 값을 찾아 선택된 위치 자료와 교환하는 정렬 방법
• 가장 작은 값을 먼저 결정하는 경우, 가장 작은 값이 1번 채로 결정되며, 2번째, 3번째 작은 값 순으로 결정

3 ) 버블 정렬(Bubble Sort)

• 주어진 파일에서 인접한 두 개의 레코드 키 값을 비교하며 그 크기에 따라 레코드 위치를 서로 교환하는 정렬 방법
• 1번째, 2번재와 비교, 2번째와 3번째와 비교, 3번째와 4번째와 비교하면서 자료를 정렬

4 ) 삽입 정렬(Insertion Sort)

• 첫 번째 자료를 기준으로 두 번째부터 차례로 비교하여 자기 위치 찾아 삽입하면서 정렬 방법으로 정렬할 자료 일부가 정렬되어 있는 경우에 유리한 방법

5 ) 쉘 정렬(Shell Sort)

• 삽입 정렬의 단점을 보완하여 확장한 개념으로 간격을 정하고, 점차 줄이면서 삽입 정렬하는 방법
• 임의의 레코드 키와 매개변수(H) 값만큼 떨어진 곳의 레코드 키를 비교하여 순서화되어 있지 않으면 서로 교환하는 것을 반복하는 정렬

6 ) 힙 정렬(Heap Sort)

• 임의의 자료에서 최솟값 도는 최댓값을 구할 경우 가장 적합한 정렬 방법
• 자료를 순서적으로 완전  이진 트리 형태로 만들어 정렬하는 방법

7 ) 이진 병합 정렬(2-Way Merge Sort)

• 정렬 대상의 자료들을 그룹별로 정렬하여 병합하면서 정렬하는 방법

8 ) 버킷 정렬(Bucket Sort)

• Stack을 이용하여 정렬하는 방법
• 레코드의 키 값을 분석하여 같은 값끼리 그 순서에 맞는 버킷에 분배하였다가 버킷의 순서대로 레코드를 꺼내어 정렬

9 ) 퀵 정렬(Quick Sort)

레코드의 많은 자료 이동을 없애고 하나의 파일을 부분적으로 나누어 가면서 정렬하는 방법

레코드의 키를 기준으로 작은 값은 왼쪽에 큰 값은 오른쪽 서브 파일로 분해하여 정렬

정렬 방식 중에서는 가장 빠른 방식이며,프로그램에서 Recursion(재귀적) 함수를 이용하기 때문에 스택이 필요

 

출처 이기적 정보처리기사