외부정렬

양방향 합병정렬

• 입력으로 보조기억장치 T0 , 출력으로 보조기억장치 T1이 사용된다.
• 주기억장치는 메모리이며 크기는 b만큼 가진다.
• 데이터 A는 주기억장치의 메모리크기 b만큼 나누어져 내부정렬을 통해 오름차순 또는 내림차순으로 정렬후 Run의 상태로 만든다.
• 보조기억장치 - 보조기억장치 또는 보조기억장치 - 주기억장치 간의 이동횟수(= 접근횟수) 를 따져서 시간복잡도를 계산한다.

다방향 합병정렬

• 양방향 합병정렬에서 더 많은 디스크(= 보조기억장치) 를 사용하는 알고리즘
• 순서는 왼쪽 상단부터 시작해서 아래 - 대각선 순서다.
• T0에 입력데이터가 들어왔을때 주기억장치의 메모리크기 b만큼 나누어 T1에 다 넣는것이아니라 T1, T2, T3에 나누어 입력한다.
• 각 보조기억장치의 첫번째 Run을 합병해서 T0에 넣는다. 마찬가지로 각 보조기억장치의 두번째 Run을 합병해서 T0에 넣는다. 이 과정을 반복한다.
• T0의 데이터를 다시 나누어 T1, T2, T3에 나누어 입력한다.
• 다시 각 보조기억장치의 첫번째 Run을 합병해서 T0에 넣는다. 이과저을 반복한다.
• 최종적으로 출력데이터를 T1에 보관하는 것을 목표로함으로 T1에 복사함에 따라 종료된다.

균형적 다방향 합병정렬

• 하나의 Run이 되는 과정을 보여줌
• 다방향 합병정렬에서의 비효율성을 보완
• 보통 짝수개의 보조기억장치를 사용한다
• T0의 입력데이터를 주기억장치 메모리크기 b만큼 나누어 T1은 제외한 나머지 T2,T3에 나누어 입력한다.
• T2,T3에서 첫번째 Run을 병합해 T0, 두번째 Run을 병합해 T1에 넣는다. 이 과정을 반복한다
• T0,T1에서 첫번째 Run을 병합하여 T2에, 두번째 Run을 병합하여 T3에 넣는다.
• 최종적으로 T0에 하나의 Run이 될때까지 이 과정을 반복한다.

탐색

순차탐색

• 간단한 알고리즘으로 인덱스를 증가시키면서 탐색하고자 하는 값과 같은지 비교

• 배열로 이루어진 경우로 인덱스를 증가시켜나가면서 탐색하고자 하는 값과 일치하면 종료되고 값을 반환

• 노드, 즉 Linked list로 이루어진 경우로 마지막 노드가 아니고, 일치하지 않는 경우 주소를 계속해서 옮겨가며 탐색하고자 하는 값과 일치하면 종료되고 값을 반환

• 배열로 이루어져있든 Linked List로 이루어져있든 시간복잡도는 동일하다.

이진탐색

• low와 high값을 인덱스의 처음과 끝 또는 값의 범위의 처음과 끝으로 정의한다.
• 이후 while문의 조건에서 low가 high를 넘지않는 경우에서 mid값을 정하고, if - elif - else문을 통해 mid값과 일치하는 경우 종료, mid값이 탐색하고자 하는 값보다 낮은 경우 low를 mid+1로 조정하여 mid값보다 작은 값들을 배제한다. 마찬가지로 mid값이 탐색하고자 하는 값보다 높은 경우 high를 mid-1로 조정하여 mid값보다 높은 값들을 배제한다.
• mid값을 조정하는 과정을 반복함에 따라 일치하면 종료되고 , 일치하지않고 결국 low가 high보다 높아지면 탐색값이 배열에 존재하지 않는 것이므로 while문이 종료된다.

외부탐색

• Database를 구축하지 않고 파일 처리를 위주로 하는 환경 에서 주로 사용
• 가정: 데이터 파일이 키 값에 따라 정렬된 상태를 유지하고 있음
• 인덱스 레코드: 데이터 파일을 일정 크기로 분할한 뒤 각 블록에서의 최대 키 값과 해당 블록 위치 정보들로 구성된 레코드를 생성
• 인덱스 파일: 인덱스 레코드들로 인덱스 파일을 구성
• 파일 접근법: 인덱스 파일을 탐색해서 원하는 코드가 존재 하는 블록 위치 정보를 얻은 다음 해당 블록을 주기억 장치로 불러들임
• 주기억 장치 내에서의 탐색은 순차탐색 방법을 사용