최적화된 버블 정렬(Optimized Bubble Sort)이란 무엇인가?

이전 글에서 버블 정렬에 대해 알아보았습니다. 

2024.12.08 - [코딩 테스트] - 버블 정렬(Bubble_Sort)이란 무엇인가?

버블 정렬(Bubble_Sort)이란 무엇인가?

 

여기서 한 단계 더 들어가서 최적화된 버블 정렬에 대해 알아보기 전에 버블 정렬을 다시 생각해 보겠습니다. 버블 정렬 코드는 모든 패스에서 전체 배열을 비교하여 정렬합니다. 즉, 이미 정렬된 부분도 다시 비교한다는 단점이 있습니다. 

 

하지만 최적화된 버블 정렬은 이미 정렬된 부분을 다시 비교하지 않도록 하여 효율성을 향상시킵니다. 여기에는 두 가지 주요 최적화 방법이 있습니다. 

 

 

1. 이미 정렬된 부분 제외
   각 패스에서 이미 정렬된 부분을 제외하여 비교 범위를 줄입니다. 하지만, 이 방법은 기본적인 버블 정렬 코드에서도 이미 적용되어 있습니다. (‘j’의 범위가 ‘n-i-1'까지인 이유) 
   
   
2.  교환 여부 확인
   이 방법은 더 중요한 최적화로, 한 패스에서 교환이 발생하지 않았으면 배열이 이미 정렬된 것으로 간주하고 반복을 중지합니다. 이 방법을 사용한 코드는 다음과 같습니다. 

def optimized_bubble_sort(arr): 
    n = len(arr) 
    for i in range(n): 
        swapped = False 
        for j in range(0, n-i-1): 
            if arr[j] > arr[j+1]: 
                arr[j], arr[j+1] = arr[j+1], arr[j] 
                swapped = True 
        if not swapped: 
            break 
    return arr

 

기존 버블 정렬과의 차이점을 확인해보겠습니다

 

기본적인 버블 정렬에서는 모든 패스를 완료해야 합니다, 즉 ‘n’ 번의 패스를 모두 수행합니다. 

하지만 최적화된 버블 정렬에서는 한 패스에서 교환이 발생하지 않으면, 즉 swapped 변수가 False로 남아있으면, 더 이상 반복할 필요가 없으므로 반복을 중지합니다. 이로 인해 이미 정렬된 배열이나 부분적으로 정렬된 배열의 경우 성능이 크게 향상됩니다. 

 

예시를 하나 보고 넘어가겠습니다. 

이미 정렬된 배열 [1, 2, 3, 4, 5]을 정렬하는 경우: 

• 기본적인 버블 정렬: 모든 패스를 완료해야 하므로 ‘n’번의 패스를 모두 수행합니다. 

• 최적화된 버블 정렬: 첫 번째 패스에서 교환이 발생하지 않으므로 즉시 반복을 중지하고 종료합니다. 

이와 같이, 최적화된 버블 정렬은 이미 정렬된 배열이나 부분적으로 정렬된 배열에 대해 더 효율적으로 작동합니다 

 

버블 정렬은 어찌 되었건 반복문을 2번 돌리기 때문에 시간 복잡도는 O(N^2)을 가집니다. 물론 최선의 경우, 만약 이미 정렬된 배열일 때, 최적화된 버블 정렬에서는 O(N)의 시간 복잡도를 가질 수 있습니다만 평균적으로 여전히 O(N^2)의 시간 복잡도를 가집니다. 이는 다른 효율적인 정렬 알고리즘에 비해 상대적으로 느린 성능을 보여줍니다. 

 

---

 

 

이번에는 while 루프를 이용한 방법을 한 번 살펴보겠습니다. 

전체적인 코드는 아래와 같습니다. 

def optimized_Bubble_Sort(arr):
    n = len(arr)
    while n > 1:
        swapped = False
        for i in range(n -1):
            if arr[i] > arr[i+1]:
                arr[i], arr[i+1] = arr[i+1], arr[i]
                swapped = True
        if not swapped:
            break
        n -= 1
    return arr

 

함수의 각 부분을 자세히 분석해 보겠습니다. 

1. 초기 설정

       n = len(arr)

    
   • n: 배열의 길이를 저장합니다. 각 패스마다 감소하여 정렬해야 할 요소의 수를 나타냅니다. 
2. 메인 루프

       while n > 1:

    
   • 이 while 루프는 n이 1보다 클 때까지 계속됩니다. 즉, 정렬할 요소가 2개 이상 남아있을 때 실행됩니다. 
3. 내부 루프

           swapped = False
           for i in range(n -1):
               if arr[i] > arr[i+1]:
                   arr[i], arr[i+1] = arr[i+1], arr[i]
                   swapped = True

   • 각 패스의 시작에서 swapped를 False로 설정합니다. 교환이 발생하면 True로 변경됩니다. 
   • range(n - 1)로 루프 범위를 설정하여, 이미 정렬된 요소들을 다시 비교하지 않습니다. 
   • 인접한 요소를 비교하고 필요시 교환합니다.
4. 조기 종료 조건

           if not swapped:
               break

    
   • 만약 한 패스동안 교환이 없었더라면(즉, swapped = False라면), 배열이 이미 정리된 상태이므로 break를 사용해서 루프를 종료합니다. 
5. 최적화 요소

           n -= 1

    
   • 각 패스가 끝날 때마다 n을 1씩 감소시킵니다. 
   • 이는 다음 패스에서 마지막 요소(가장 큰 값)가 이미 올바른 위치에 있음을 의미합니다.