13-1 자료 정렬 방법

1. 정렬의 개념과 정렬의 종류

① 정렬

- 순서 없이 배열된 자료를 작은 것부터 큰 것 순서인 오름차순이나, 큰 것부터 작은 것 순서인 내림차순으로 재배열하는 것

- 키 : 자료를 정렬하는데 사용하는 기준이 되는 특정 값.

 

②정렬 방식 분류

- 내부 정렬 

  □ 정렬할 자료를 메인 메모리에 올려서 정렬하는 방식

  □ 정렬 속도가 빠르지만 정렬할 수 있는 자료의 양이 메인 메모리의 용량에 따라 제한됨.

 

- 외부 정렬

  □ 정렬할 자료를 보조 기억장치에서 정렬하는 방식

  □ 대용량의 보조 기억 장치를 사용하기 때문에 내부 정렬보다 속도는 떨어져도 내부 정렬로 처리할 수 없는 대용량의 자료에 대한 정렬이 가능.

 

2. 선택 정렬과 버블 정렬

① 선택정렬

- 전체 원소들 중에서 기준 위치에 맞는 원소를 선택하여 자리를 교환하는 방식으로 정렬

 

② 버블 정렬

- 인접한 두개의 원소를 비교하여 자리를 교환하는 방식

 

3. 퀵정렬과 삽입정렬

① 퀵정렬의 이해

- 정렬할 전체 원소에 대해 정렬을 수행하지 않고, 기준 값을 중심으로 왼쪽 부분, 오른쪽 부분 집합으로 분할하여 정렬하는 방법

- 분할과 정복을 반복하여 수행하여 완성

- 피봇(기준값)은 주로 전체 원소 중 가운데에 위치한 것을 선택.

 

② 삽입정렬의 이해

- 정렬되어 있는 부분집합에 정렬할 새로운 원소의 위치를 찾아 삽입하는 방법

- 정렬할 자료를 두 개의 부분집합 S와 U로 가정