정렬 편집하기

[[분류:알고리즘]][[분류:정보처리기사]]
;sort
;파일을 구성하는 각 레코드를 특정 키 항목을 기준으로 오름차순/내림차순으로 재배열하는 작업을 말한다

== 실행 방법에 따른 분류 ==
비교식 정렬(comparative sort)와 분산식 정렬(distribute sort)가 있다.

== 기억장치에 따른 분류 ==
=== 내부정렬기법 ===
;데이터량이 적을 때 주기억장치 내에서 정렬하는 방법
;속도는 빠르나 기억장치의 용량을 초과하는 대용량 자료의 정렬이 어려룸
* '''삽입 정렬(Insertion Sort)'''
** 이미 순서화된 파일에 새로운 레코드를 추가하여 순서에 맞게 배치 (2번째 값부터 시작한다)
** 시간 복잡도: O(n²)

* '''셸 정렬(Shell Sort) '''
** 시간 복잡도: O(n^1.5)

* '''선택 정렬(Select Sort)'''
** 레코드의 최소값을 찾아 첫번째 위치에 놓고 다음 최소값을 찾아 두번째 위치에 놓는 방법을 반복하여 정렬
** 시간 복잡도: O(n²)

* '''버블 정렬(Bubble Sort)'''
** 인접한 값과 비교하여 정렬하는 방식. 끝에 값부터 정해진다.
** 시간 복잡도: O(n²)

* '''퀵 정렬(Quick Sort)'''
** 시간 복잡도: O(nlog₂n)

* '''힙 정렬(Heap Sort)'''
** 시간 복잡도: O(nlog₂n)

* '''병합 정렬(Merge Sort)'''
** 시간 복잡도: O(nlog₂n)

* '''기수 정렬(Radix Sort)'''
** 시간 복잡도: O(n)

=== 외부정렬기법 ===
; 대용량의 데이터를 몇 개의 서브 파일로 나누어 각각 내부 정렬을 한 후에 테이프나 디스크 내에서 각 서브파일을 합병하는 방법
* 속도는 느리지만 자료의 대용량 자료를 정렬할 수 있음
* 진동 병합 정렬(Oscillating Merge Sort)
* 캐스케이드 병합 정렬(Cascade Merge Sort)
* 폴리파즈 병합 정렬(Polyphase Merge Sort)
* 균형 병합 정렬(Balance Merge Sort)

== 정렬 알고리즘의 선택시 고려사항 ==
# 키값들의 분포 상태
# 소요공간 및 작업시간
# 정렬에 필요한 기억공간의 크기
# 데이터의 양
# 초기 데이터의 배열상태
# 사용 컴퓨터 시스템의 특성
@@ 1번째 줄: / 1번째 줄: @@
-[[분류:알고리즘]]
+[[분류:알고리즘]][[분류:정보처리기사]]
-[[분류:정보처리기사]]
 ;sort
 ;파일을 구성하는 각 레코드를 특정 키 항목을 기준으로 오름차순/내림차순으로 재배열하는 작업을 말한다
-==실행 방법에 따른 분류==
+== 실행 방법에 따른 분류 ==
 비교식 정렬(comparative sort)와 분산식 정렬(distribute sort)가 있다.
-==기억장치에 따른 분류==
+== 기억장치에 따른 분류 ==
-===내부정렬기법===
+=== 내부정렬기법 ===
 ;데이터량이 적을 때 주기억장치 내에서 정렬하는 방법
-;속도는 빠르나 기억장치의 용량을 초과하는 대용량 자료의 정렬이 어려움
+;속도는 빠르나 기억장치의 용량을 초과하는 대용량 자료의 정렬이 어려룸
+* '''삽입 정렬(Insertion Sort)'''
-*'''[[삽입 정렬|삽입 정렬(Insertion Sort)]]'''
+** 이미 순서화된 파일에 새로운 레코드를 추가하여 순서에 맞게 배치 (2번째 값부터 시작한다)
-**이미 순서화된 파일에 새로운 레코드를 추가하여 순서에 맞게 배치 (2번째 값부터 시작한다)
+** 시간 복잡도: O(n²)
-**시간 복잡도: O(n²)
-*'''[[셀 정렬|셸 정렬(Shell Sort)]] '''
-**시간 복잡도: O(n^1.5)
-*'''[[선택 정렬|선택 정렬(Selection Sort)]]'''
-**레코드의 최소값을 찾아 첫번째 위치에 놓고 다음 최소값을 찾아 두번째 위치에 놓는 방법을 반복하여 정렬
-**시간 복잡도: O(n²)
-*'''[[버블 정렬|버블 정렬(Bubble Sort)]]'''
-**인접한 값과 비교하여 정렬하는 방식. 끝에 값부터 정해진다.
-**시간 복잡도: O(n²)
-*'''[[퀵 정렬|퀵 정렬(Quick Sort)]]'''
+* '''셸 정렬(Shell Sort) '''
-**시간 복잡도: O(nlog₂n)
+** 시간 복잡도: O(n^1.5)
-*'''[[힙 정렬|힙 정렬(Heap Sort)]]'''
+* '''선택 정렬(Select Sort)'''
-**정렬한 입력 레코드들로 힙을 구성하고 가장 큰 키값을 갖는 루트 노드를 제거하는 과정을 반복하여 정렬하는 기법
+** 레코드의 최소값을 찾아 첫번째 위치에 놓고 다음 최소값을 찾아 두번째 위치에 놓는 방법을 반복하여 정렬
-**시간 복잡도: O(nlog₂n)
+** 시간 복잡도: O(n²)
-*'''[[병합 정렬|병합 정렬(Merge Sort)]]'''
+* '''버블 정렬(Bubble Sort)'''
-**시간 복잡도: O(nlog₂n)
+** 인접한 값과 비교하여 정렬하는 방식. 끝에 값부터 정해진다.
+** 시간 복잡도: O(n²)
-*'''[[기수 정렬|기수 정렬(Radix Sort)]]'''
+* '''퀵 정렬(Quick Sort)'''
-**시간 복잡도: O(n)
+** 시간 복잡도: O(nlog₂n)
-===외부정렬기법===
+* '''힙 정렬(Heap Sort)'''
+** 시간 복잡도: O(nlog₂n)
-;대용량의 데이터를 몇 개의 서브 파일로 나누어 각각 내부 정렬을 한 후에 테이프나 디스크 내에서 각 서브파일을 합병하는 방법
+* '''병합 정렬(Merge Sort)'''
+** 시간 복잡도: O(nlog₂n)
-*속도는 느리지만 자료의 대용량 자료를 정렬할 수 있음
+* '''기수 정렬(Radix Sort)'''
-*진동 병합 정렬(Oscillating Merge Sort)
+** 시간 복잡도: O(n)
-*캐스케이드 병합 정렬(Cascade Merge Sort)
-*폴리파즈 병합 정렬(Polyphase Merge Sort)
-*균형 병합 정렬(Balance Merge Sort)
-==정렬 알고리즘의 선택시 고려사항==
+=== 외부정렬기법 ===
+; 대용량의 데이터를 몇 개의 서브 파일로 나누어 각각 내부 정렬을 한 후에 테이프나 디스크 내에서 각 서브파일을 합병하는 방법
+* 속도는 느리지만 자료의 대용량 자료를 정렬할 수 있음
+* 진동 병합 정렬(Oscillating Merge Sort)
+* 캐스케이드 병합 정렬(Cascade Merge Sort)
+* 폴리파즈 병합 정렬(Polyphase Merge Sort)
+* 균형 병합 정렬(Balance Merge Sort)
-#키값들의 분포 상태
+== 정렬 알고리즘의 선택시 고려사항 ==
-#소요공간 및 작업시간
+# 키값들의 분포 상태
-#정렬에 필요한 기억공간의 크기
+# 소요공간 및 작업시간
-#데이터의 양
+# 정렬에 필요한 기억공간의 크기
-#초기 데이터의 배열상태
+# 데이터의 양
-#사용 컴퓨터 시스템의 특성
+# 초기 데이터의 배열상태
+# 사용 컴퓨터 시스템의 특성