버블 정렬 알고리즘에는 한 쌍의 중첩 루프가 필요합니다. 외부 루프는 데이터 세트 (크기 n)의 각 요소에 대해 한 번 반복해야하며 내부 루프는 처음 입력 할 때 n 번, 두 번째에 n-1 번 반복하는 식입니다. 각 루프의 목적을 고려하십시오. 위에서 설명한 것처럼 버블 정렬은 목록을 통과 할 때마다 데이터의 다음으로 큰 요소가 적절한 위치로 이동하도록 구조화됩니다. 따라서 모든 n 요소를 올바른 위치에 가져 오려면 외부 루프를 n 번 실행해야합니다.
내부 루프는 외부 루프가 반복 될 때마다 실행됩니다. 그 목적은 다음으로 큰 요소를 배치하는 것입니다. 따라서 내부 루프는 인접한 요소의 비교 및 교체를 수행합니다. 이 루프의 복잡성을 확인하기 위해 수행해야하는 비교 횟수를 계산합니다. 외부 루프의 첫 번째 반복에서 가장 큰 요소를 배치하려고 시도하는 동안 n-1 개의 비교가 있어야합니다. 첫 번째 요소는 첫 번째와 두 번째 요소 사이에, 두 번째는 두 번째와 세 번째 요소 사이에 이루어집니다. n-1 번째 요소와 n 번째 요소 사이에 n-1 번째 비교가 이루어질 때까지 계속됩니다. 외부 루프의 두 번째 반복에서는 이전 패스의 올바른 위치에 배치 되었기 때문에 목록의 마지막 요소와 비교할 필요가 없습니다. 따라서 두 번째 반복에는 n-2 비교 만 필요합니다. 이 패턴은 목록의 처음 두 요소 만 정렬되지 않은 경우 외부 루프의 두 번째에서 마지막 반복까지 계속됩니다. 이 경우에는 하나의 비교 만 필요합니다. 따라서 총 비교 횟수는 (n-1) + (n-2) … (2) + (1) = n (n-1) / 2 또는 O (n2)입니다.
버블 정렬의 가장 좋은 경우는 목록이 이미 정렬되었거나 거의 정렬되었을 때 발생합니다. 목록이 이미 정렬 된 경우 스왑이 수행되지 않았으므로 버블 정렬이 첫 번째 반복 후에 종료됩니다. 목록을 통과하고 스왑이 이루어지지 않았을 때마다 목록이 정렬됩니다. 버블 정렬은 새 요소가 끝이 아닌 시작 부분에 배치되는 경우 임의의 요소 하나를 정렬 된 목록으로 정렬해야하는 경우에도 효율적입니다. 처음에 배치하면 단순히 올바른 위치로 버블 링되고 목록을 통한 두 번째 반복은 0 개의 스왑을 생성하여 정렬을 종료합니다. 임의의 요소가 끝에 배치되면 거품 정렬이 효율성을 잃게됩니다. 그보다 큰 각 요소는 맨 위로 올라와야하기 때문입니다.
버블 정렬의 절대 최악의 경우는 목록의 가장 작은 요소는 큰 끝에 있습니다. 각 반복에서 가장 큰 정렬되지 않은 요소 만 적절한 위치에 배치되기 때문에 가장 작은 요소가 끝에있을 때 목록을 통해 매번 교체되어야하며 모든 n이 될 때까지 목록의 맨 앞으로 이동하지 않습니다. 반복이 발생했습니다. 이 최악의 경우 n / 2 스왑의 n 반복이 필요하므로 순서는 다시 n2입니다.
최상의 사례 : n 평균 사례 : n2 최악 사례 : n2