[알고리즘] 버블 정렬 Bubble Sort

버블 정렬(Bubble Sort)

• 버블 정렬은 인접한 두 요소를 비교하여 필요한 경우 교환하며 리스트를 정렬하는 알고리즘

 

 

 

동작 원리

1. 리스트의 처음부터 끝까지 인접한 두 요소를 반복적으로 비교한다.
2. 앞의 요소가 뒤의 요소보다 크면 두 요소를 교환.
3. 각 반복이 끝날 때마다 가장 큰 요소가 리스트의 끝에 위치하게 된다.
4. 이 과정을 리스트 전체가 정렬될 때까지 반복.

 

 

 

단계별 구현

1. 리스트의 마지막 요소부터 첫 번째 요소까지 역순으로 순회.
2. 각 반복에서 리스트의 처음부터 현재 반복 요소까지 순회하여 인접한 두 요소를 비교하기.
3. 만약 앞의 요소가 뒤의 요소보다 크다면 두 요소를 교환.
4. 교환이 발생하지 않은 경우 리스트가 이미 정렬된 상태이므로 반복을 중단.

 

 

 

Python 파이썬 코드:

def bubbleSort(lst: list) -> list:
    
    length = len(lst)

    for last in range(length-1, 0, -1):
        swapped = False # 교환 여부

        for i in range(last):
            # 인접한 두 요소를 비교하여 앞의 요소가 크면 교환
            if(lst[i] > lst[i+1]):
                lst[i], lst[i+1] = lst[i+1], lst[i]
                swapped = True

        # 교환이 발생하지 않았다면 -> 정렬된 상태
        if not swapped:
            break

    return lst

def bubbleSort(lst: list) -> list:

   

    length = len(lst)

    for last in range(length-1, 0, -1):

        swapped = False # 교환 여부

        for i in range(last):

            # 인접한 두 요소를 비교하여 앞의 요소가 크면 교환

            if(lst[i] > lst[i+1]):

                lst[i], lst[i+1] = lst[i+1], lst[i]

                swapped = True

        # 교환이 발생하지 않았다면 -> 정렬된 상태

        if not swapped:

            break

    return lst

 

 

 

장단점

장점:

• 구현이 간단하고 직관적이다?.

 

단점:

• 시간 복잡도가 O(n^2)로, 큰 데이터셋에는 비효율적이다.
• 교환 횟수가 많아 다른 정렬 알고리즘보다 느릴 수 있다.