버블 정렬

PerformanceEdit

버블 정렬은 О (n2)의 최악의 경우 및 평균 복잡도를 가지며 여기서 n은 정렬되는 항목의 수입니다. 대부분의 실용적인 정렬 알고리즘은 최악의 경우 또는 평균 복잡성이 상당히 우수하며 종종 O (n log n)입니다. 삽입 정렬과 같은 다른 О (n2) 정렬 알고리즘도 일반적으로 버블 정렬보다 빠르게 실행되며 더 이상 복잡하지 않습니다. 따라서 버블 정렬은 실용적인 정렬 알고리즘이 아닙니다.

버블 정렬이 다른 대부분의 알고리즘, 심지어 빠른 정렬 (삽입 정렬은 아님)에 비해 가지는 유일한 중요한 이점은 목록이 정렬되었음을 감지하는 기능입니다. 효율적으로 알고리즘에 내장되어 있습니다. 목록이 이미 정렬 된 경우 (최상의 경우) 버블 정렬의 복잡성은 O (n)뿐입니다. 대조적으로, 대부분의 다른 알고리즘, 심지어 더 나은 평균 케이스 복잡성을 가진 알고리즘은 세트에서 전체 정렬 프로세스를 수행하므로 더 복잡합니다. 그러나 삽입 정렬은 이러한 이점을 공유 할뿐만 아니라 실질적으로 정렬 된 목록 (작은 수의 반전 포함)에서도 더 잘 수행됩니다. 또한이 동작이 필요한 경우 알고리즘이 실행되기 전에 목록을 확인하여 다른 알고리즘에 간단하게 추가 할 수 있습니다.

대규모 컬렉션의 경우 버블 정렬을 피해야합니다. 역순으로 정렬 된 컬렉션의 경우 효율적이지 않습니다.

Rabbits and TurtlesEdit

정렬 중에 요소가 이동해야하는 거리와 방향이 버블 정렬의 성능을 결정하기 때문입니다. 요소는 서로 다른 속도로 서로 다른 방향으로 이동합니다. 목록 끝으로 이동해야하는 요소는 연속적인 교체에 참여할 수 있기 때문에 빠르게 이동할 수 있습니다. 예를 들어 목록에서 가장 큰 요소가 모든 교체에서 승리하므로 다음으로 이동합니다. 첫 번째 패스에서 정렬 된 위치는 시작 근처에서 시작하더라도 목록의 시작 부분으로 이동해야하는 요소는 패스 당 한 단계보다 빠르게 이동할 수 없으므로 요소는 처음으로 매우 느리게 이동합니다. 가장 작은 요소는 목록의 끝에 있으며, 처음으로 이동하려면 n-1 패스가 필요합니다. 이로 인해 이러한 유형의 요소는 각각 이솝 우화의 캐릭터 이름을 따서 토끼와 거북이로 명명되었습니다. 거북이와 토끼.

각종 거품 분류 속도를 향상시키기 위해 거북이를 제거하기위한 노력이있었습니다. 칵테일 정렬은 처음에서 끝으로 이동 한 다음 자체를 뒤집어 끝에서 시작으로 이동하는 양방향 거품 정렬입니다. 거북이를 상당히 잘 움직일 수 있지만 최악의 경우 O (n2) 복잡성을 유지합니다. 콤 정렬은 큰 간격으로 분리 된 요소를 비교하고 목록을 부드럽게하기 위해 더 작고 작은 간격으로 진행하기 전에 거북이를 매우 빠르게 이동할 수 있습니다. 평균 속도는 빠른 정렬과 같은 더 빠른 알고리즘과 비슷합니다.

단계별 exampleEdit

숫자 배열 “5 1 4 2 8″을 가져 와서 가장 낮은 것부터 정렬합니다. 버블 정렬을 사용하여 숫자를 가장 큰 숫자로 만듭니다. 각 단계에서 굵게 표시된 요소가 비교됩니다. 세 번의 패스가 필요합니다.

첫 번째 패스 (5 1 4 2 8) → (1 5 4 2 8), 여기서 알고리즘은 처음 두 요소를 비교하고 5 개 이후로 교체합니다. > 1. (1 5 4 2 8) → (1 4 5 2 8), 5 이후 스왑 > 4 (1 4 5 2 8) → (1 4 2 5 8), 5 이후 스왑 > 2 (1 4 2 5 8) → (1 4 2 5 8), 이제 이러한 요소가 이미 순서대로되어 있으므로 (8 > 5), 알고리즘은 이들을 교환하지 않습니다. 두 번째 패스 (1 4 2 5 8) → (1 4 2 5 8) (1 4 2 5 8) → (1 2 4 5 8), Swap since 4 > 2 ( 12 4 5 8) → (1 2 4 5 8) (1 2 4 5 8) → (1 2 4 5 8)

이제 배열은 이미 정렬되었지만 알고리즘은 완료 여부를 알 수 없습니다. . 알고리즘이 정렬되었는지 알기 위해서는 스왑없이 전체 패스가 하나 필요합니다.