정렬(Sort)

정렬(Sort)

- 여러 개의 자료를 순서에 따라 나열하는 방법입니다.

삽입 정렬(Insertion Sort)

- 이미 순서화된 파일에 새로운 하나의 레코드를 순서에 맞게 삽입시켜 정렬합니다.

- 가장 간단한 정렬 방식입니다.

- 평균 시간 복잡도와 최악 시간 복잡도는 O(n^2)입니다.

선택 정렬(Selection Sort)

- n개의 레코드 중에서 최소값을 찾아 첫 번째 레코드 위치에 놓고 나머지 n-1개 중에서 다시 최소값을 찾아 두 번째 레코드 위치에 놓는 방식을 반복하여 정렬합니다.

- 평균 시간 복잡도와 최악 시간 복잡도는 O(n^2)입니다.

버블 정렬(Bubble Sort)

- 주어진 파일에서 인접한 두 개의 레코드 키 값을 비교하여 그 크기에 따라 레코드 위치를 서로 교환하는 정렬합니다.

- 평균 시간 복잡도와 최악 시간 복잡도는 O(n^2)입니다.

퀵 정렬(Quick Sort)

- 키를 기준으로 작은 값은 왼쪽에, 큰 값은 오른쪽 서브 파일로 분해시는 방식으로 정렬합니다.

- 레코드의 많은 자료 이동을 없애고 하나의 파일을 부분적으로 나누어 가면서 정렬합니다.

- 평균 시간 복잡도는 O(nlogn)이고, 최악 시간 복잡도는 O(n^2)입니다.

 

정보처리기사 2022년 1회 36번 출제