[자료구조] 정렬과 선택정렬

[자료구조] 정렬과 선택정렬

• 정렬의 개념

 - 순서 없이 배열되어 있는 자료들을 오름차순(작은 것부터 큰 것)이나 내림차순(큰 것부터 작은 것)으로 재배열 하는 것

 - key : 기준이 되는 특정 값  [Ex] 학생의 성적 나열에서 키는 '총점'

 

• 정렬방법의 분류

 - 정렬 방법은 실행 방법, 수행 장소에 따라 분류할 수 있다.

 [실행 방법에 따른 분류] 

  * 비교식 정렬(Comparative Sort) : 한 번에 2개씩 비교하여 교환

  * 분산식 정렬(Distribute Sort) : 키 값을 기준으로 여러 개로 분해하고 부분집합을 정렬하여 전체 정렬

 [정렬 장소에 따른 분류]

  * 내부 정렬 : 정렬할 자료를 메인 메모리에 올려 정렬하는 방식, 정렬 속도는 빠르나 자료의 양이 메모리에 따라 제한된다.

   - 교환 방식 : 키를 비교하고 교환하여 정렬(선택/버블/퀵 정렬)

   - 삽입 방식 : 키를 비교하고 삽입하여 정렬(삽입/셸 정렬)

   - 병합 방식 : 키를 비교하고 병합하여 정렬(2-way 병합/n-way 병합)

   - 분배 방식 : 키를 구성하는 값을 여러 개의 부분 집합에 분배하여 정렬(기수 정렬)

   - 선택 방식 : 이진 트리를 사용하여 정렬(히프/트리 정렬)

  

  * 외부 정렬 : 대용량 보조 기억 장치를 사용하여 속도는 떨어지나 대용량의 자료를 정렬할 수 있다.

   - 병합 방식 : 파일을 부분 파일로 분리해 각각을 내부 정렬 방법으로 정렬 후 병합하여 정렬(2-way 병합/n-way 병합)

[참조] C로 배우는 쉬운 자료구조-한빛미디어, 이지영 저