[컴퓨터]sort ( shell sort , selection sort ) 에 관해

1.1 정렬(sort)의 개요
정렬이란 임의의 순서대로 배열되어 있는 자료의 집합을 일정한 순서대로 재배열 하는 것을 의미한다.
정렬은 컴퓨터로 문제 해결을 하는데 있어서 검색과 함께 가장 많이 부닥치는 문제이다.
그래서 알고리즘들 중에서는 가장 역사가 깊으며, 가장 연구가 많이 되어 왔으며, 가장 다양한 알고리즘들이 선택을 기다리고 있다.
1.2 정렬의 방법론
모든 정렬 알고리즘은 판단과 교환을 어떻게 적절히 조합하는가에 대한 방법론이다.
정렬을 하는 대상을 파일(file)이라고 하며, 이 파일은 정보의 단위인 레코드(record)의 나열이다.
‘비교’의 대상이 되는 것은 레코드 중에서도 키 값이며, ‘교환’의 대상이 되는 것은 레코드 자체가 된다.
1.3 정렬 알고리즘의 다양성
정렬 알고리즘은 참으로 다양하다.
1) 정렬의 관습적 분류 : 그 알고리즘이 간단한 것이냐, 복잡한 것이냐에 따라 나누는 것
• 간단한 알고리즘 : 선택 정렬, 삽입 정렬, 거품 정렬, 셀 정렬 등이 있다.
• 복잡한 알고리즘 : 퀵 정렬, 기수 정렬, 힙 정렬, 병합 정렬
• 각각의 장단점 : 간단한 알고리즘은 안정되어 있고 구현이 쉬운 장점이 있으나 복잡한 알고리즘에 비해서 정렬 속도가 느리다. 반면에 복잡한 알고리즘은 구현에 어려움이 있고 부차원적인 메모리가 필요하기도 하지만 일반적으로 단순한 알고리즘에 비해서 정렬 속도가 빠르다.
2) 외부 정렬과 내부 정렬
• 내부 정렬 : 정렬의 대상이 되는 레코드들의 배열이 컴퓨터 메모리 내부에 있는 것
• 외부 정렬 : 정렬의 대상이 되는 레코드들의 배열이 디스크나 테이프 장치왿� 같은 컴퓨터의 외부에 있는 것.
• 각각의 장단점 : 내부 정렬의 특징은 컴퓨터 메모리의 빠른 비교왿� 교환을 이용하기 때문에 속도가 빠르다는 장점이 있으나, 모든 자료를 컴퓨터의 메인 메모리로 옮겨 놓아야 한다는 부담이 있다. 외부 정렬은 디스크나 테이프상에서 직접 정렬을 행하기 때문에 속도는 느리지만 메인 메모리를 자료들이 차지하지는 않는다.