알고리즘 정렬(sort) - 선택정렬,버블정렬,삽입정렬,쉘정렬,퀵정렬,합병정렬,히프정렬,계수정렬,기수정렬,버킷정렬,외부정렬,다단계 합병정렬

소개

알고리즘 정렬의 종류와 설명 및 소스

목차

1,정렬소개
2.선택정렬
3.버블정렬
4.삽입정렬
5.쉘정렬
6.퀵정렬
7.합병정렬
8.히프정렬
9.계수정렬
10.기수정렬
11.버킷정렬
12.외부정렬
13.다단계 합병정렬

본문내용

균형적 다방향 합병 정렬
t-방향 합병정렬에서 필요한 보조기억장치의 수는 2t개. 입력용, 출력용 각 t개씩.
정렬 과정과 합병 과정
초기 정렬 – 메모리에서 처리할 수 있는 크기의 블록 단위로 내부 정렬하여 t개의 출력 테이프에 번갈아 출력.
합병- 합병 과정마다 블록의 크기는 t배로 됨.

초기 정렬 블록을 크게 하여 테이프 이동 횟수를 줄이고자 한 것.
우선순위 큐(최소값 히프)에서 최소 원소를 블록의 다음 원소로 대치해 나가는 과정 평균적으로 약 2배 큰 정렬 블록
출력 테이프로 하나의 레코드를 출력하면 바로 입력 테이프에서 다음 레코드를 읽어들여 주기억장치에 항상 b개의 레코드가 유지되도록 함
다음 입력 레코드의 키 값이 방금 출력한 키 값보다 작으면 이 키는 현재 정렬 블록에는 속할 수 없으므로 새로운 정렬 블록에 속하는 것으로 마크

참고자료

· 없음