[정렬] 버블 정렬(Bubble Sort)

1. 아이디어

• . 첫번째와 두번째 값을 비교하고, 두번째와 세번째 값을 비교하고, ... n-1번째와 n번째 값을 비교합니다. 이 과정에서 순서가 맞지 않은 값을 서로 교환
• 정렬이 될 때까지 반복

2. 구현 (Python, Java)

• Python

def bubbl_sort(arr: list[int]) -> list[int]:
    for i in range(n - 1):
        swapped = False
        for j in range(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

 

• Java

  private static List<Integer> bubblSort(List<Integer> arr) {
        int n = arr.size();
        for (int i = 0; i < n - 1; i++) {
            boolean isSwap = false;
            for (int j = 0; j < n - i - 1; j++) {
                if (arr.get(j) > arr.get(j + 1)) {
                    int temp = arr.get(j);
                    arr.set(j, arr.get(j + 1));
                    arr.set(j + 1, temp);
                    isSwap = true;
                }
            }

            if (!isSwap) {
                break;
            }
        }
        return arr;
    }

 

3.  시간복잡도

• 구현에 따라
  • O(N)
  • O(N^2)