정렬이란 항목값의 대소관계에 따라 데이터 집합을 일정한 순서로 바꾸어 늘어놓는 작업을 말합니다. 정렬 알고리즘은 안정적인 알고리즘과 그렇지 않은 알고리즘으로 나눌 수 있습니다. 안정적인 정렬 알고리즘은 같은 원소의 순서가 정렬한 후에도 유지되는 것입니다. 안정적이지 않은 알고리즘은 정렬한 후에도 원래의 순서가 유지된다는 보장을 할 수 없습니다.

데이터 크기에 따라 내부정렬과 외부정렬로 나눌 수 있는데요. 내부정렬은 정렬할 모든 데이터를 하나의 배열에 저장할 수 있는 경우에 사용하는 알고리즘입니다. 외부정렬은 정렬할 데이터가 많아서 하나의 배열에 저장할 수 없는 경우에 사용하는 알고리즘입니다.

정렬 알고리즘은 데이터를 교환, 선택, 삽입하면서 정렬을 완료합니다.

버블 정렬은 이웃한 두 원소의 대소 관계를 비교하여 필요에 따라 교환을 반복하는 알고리즘입니다. 이웃한 원소를 비교하고 필요하면 교환하는 작업을 반복합니다. 이렇게 비교하고 교환하는 일련의 과정을 패스하고 합니다. 모든 정렬이 끝나려면 패스를 n-1번 수행해야 합니다. 버블 정렬은 서로 이웃한 원소만 교환하므로 안정적입니다.

버블 정렬 알고리즘을 개선하는 방법으로는 3가지가 있습니다. 먼저 어떤 원소의 교환 횟수가 0이면 모든 원소가 정렬을 완료한 경우이므로 그 이후의 패스는 불필요하다고 판단하여 정렬을 중단할 수 있습니다. 이러한 중단 방식을 적용하면 정렬을 모두 마쳤거나 정렬이 거의 다 된 배열에서는 비교 연산이 크게 줄어 실행 시간을 단축할 수 있습니다. 또한, 이미 정렬된 원소를 제외하고 나머지만 비교하여 교환하도록 스캔 범위를 제한하여 알고리즘을 개선할수도 있습니다. 마지막으로 패스의 스캔 방향을 번갈아 바꾸는 세이커 정렬 방법으로도 개선할 수 있습니다.