내부 정렬

내부 정렬은 전적으로 컴퓨터의 메인 메모리 내에서 수행되는 데이터 정렬 프로세스입니다.이는 정렬할 데이터가 모두 메인 메모리에 저장될 정도로 작을 때마다 가능합니다.대규모 데이터 세트를 정렬하는 경우 데이터 청크만 메모리에 저장해야 할 수 있습니다. 데이터 청크가 모두 들어맞지는 않기 때문입니다.나머지 데이터는 일반적으로 하드 디스크와 같이 크기가 크지만 속도가 느린 미디어에 보관됩니다.이 느린 미디어에서 데이터를 읽거나 쓰면 정렬 프로세스가 상당히 느려질 수 있습니다.이 문제는 다른 종류의 알고리즘에 영향을 미칩니다.

일반적인 내부 정렬 알고리즘은 다음과 같습니다.

1. 버블 정렬
2. 삽입 정렬
3. 빠른 정렬
4. 히프 정렬
5. 기수 정렬
6. 선택 정렬

Bublesort를 예로 들 수 있습니다.이곳에서는 인접 레코드가 올바른 순서로 교환되어 레코드가 데이터 공간을 통해 "버블" 상태로 보이도록 합니다.이 작업을 청크 단위로 수행해야 하는 경우 청크 1의 모든 레코드를 정렬한 후 청크 2로 이동하지만 청크 1의 일부 레코드는 청크 2에 "버블"해야 하며, 그 반대도 마찬가지입니다(즉, 청크 1에 속하는 레코드는 청크 2에 있고, 2 또는 그 이후의 청크 1에 속하는 레코드가 있습니다).이로 인해 레코드가 서로 경계를 넘나들 때 청크를 여러 번 읽고 디스크에 다시 쓰기 때문에 성능이 크게 저하됩니다.모든 데이터를 하나의 큰 청크로 메모리에 유지할 수 있으면 이 퍼포먼스에 대한 영향을 피할 수 있습니다.

한편, 일부 알고리즘은 외부 정렬을 더 잘 처리합니다.병합 정렬은 데이터를 청크로 나누고 다른 알고리즘(버블소트 또는 빠른 정렬 등)별로 청크를 정렬한 다음 재결합된 각 청크가 순서대로 정렬되도록 청크를 2개씩 재결합합니다.이 방법은 디스크에서 데이터 청크의 수 또는 읽기 및 쓰기를 최소화하며 널리 사용되는 외부 정렬 방법입니다.