Campus Coder

외부 정렬 정렬하려는 리스트 전체가 컴퓨터의 메인 메모리에 모두 올라갈 수 없다면 내부 정렬 사용 불가 블록 - 한 번에 디스크로부터 읽거나 디스크에 쓸 수 있는 데이터 단위, 여러 개의 레코드들로 구성 판독/기록 시간에 영향을 미치는 요소 탐구 시간: 판독/기록 헤드가 디스크 상의 원하는 실린더로 이동하는데 걸리는 시간, 헤드가 가로질러야 하는 실린더 수에 따라 결정됨 회전지연 시간: 트랙의 해당 섹터가 판독/기록 헤드 밑으로 회전해 올 때까지 걸리는 시간 전송 시간: 디스크로 오는 디스크로부터 데이터 블록을 전송하는 데 걸리는 시간 합병 정렬 입력 리스트의 여러 세그먼트들을 좋은 내부 정렬 방법으로 정렬 런(run) - 정렬된 세그먼트들 런이 생성되면 외부 저장 장치에 기록됨 1에서 만들어진 런들은 ..

정렬 리스트를 오름차순, 내림차순 혹은 어떤 조건에 대해 순서대로 배열한 것 정렬에 필요성 빠른 탐색을 위해 사용 리스트의 엔트리를 비교하는 방법으로 사용 정렬 방법 내부 방법 - 정렬할 리스트가 작아서 전체적인 정렬이 메인 메모리 상에서 실행될 수 있을 때 사용 외부 방법 - 큰 리스트에 사용 삽입 정렬 template void Insert(const T &e, T *a, int i) { // e를 정렬된 리스트 a[1:i]에 삽입 // 리스트 a[1:i+1]도 정렬되게 함 // 배열 a는 적어도 i+2 원소를 포함할 공간 필요 a[0] = e; while (e < a[i]) { // 리스트의 맨 뒤부터 e가 삽입될 위치인지 탐색하며, a[i + 1] = a[i]; // 배열 a의 원소를 한칸씩 위로 ..