[0707] Bubble Sort

ㅇㅇㅈ·2025년 7월 18일

개념

인접한 두 개의 원소를 비교하고, 필요하면 교환하여 정렬하는 방식
한 번의 패스(반복)마다 가장 큰 값이 맨 끝으로 이동
총 (N-1)번 반복하며, 각 반복마다 비교 횟수가 감소

정렬 알고리즘 이야기는 재밌는 것 같다.

예전에 유튜브에서 유행했던 'Sound Sorting Algorithm'에 꽂혔던 적이 있어서, 한동안 얘네들을 엄청 봤었는데,
정렬 알고리즘 개념 강의를 듣다보면 얘네들이 생각나서 이해가 조금 빠르게 되는 것 같다.

여담이지만 난 Bubble sort가 싫었다. 무지막지하게 시간이 걸려서. O(n²)

https://youtu.be/kPRA0W1kECg?t=241
^ Bubble Sort를 보여주는 부분.

실제로 '현재 음'의 '다음의 음'을 찾아내면 '현재 음'의 옆에 붙여두기 때문에, 빨간 포인터가 반복할 때마다 탐색하는 범위가 -1씩 되는 것을 시각적으로 확인할 수 있다.

시간 복잡도

Best Case	Average Sort	Worst Case
O(n) 이미 정렬된 경우	O(n^2)	O(N^2)

이럴 줄 알았다.

원리도 너무 단순하고, 아마 정렬 알고리즘 중에 가장 오래 걸릴 것 같다.
위에 있는 유튜브 영상에서도, 데이터를 반으로 나누어 양방향에서 버블 소트를 병렬로 진행하는 알고리즘이 있었는데. 그 친구는 시간 복잡도가 어느정도 나올 지 궁금하다.

코드 구현

import java.io.*;
import java.util.*;

public class BubbleSort {

    public static void bubbleSort(int[] arr) {
        int size = arr.length;
        for (int i = 0; i < size - 1; i++) {
            //              이 부분은 n-1을 구현하는 것이 중요한 부분이기에
            //              구분을 개인 역량대로 바꿀 수 있다.
            //              내가 이해하기 쉬운 것이 중요하다!!!
            for (int j=0; j < size - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        int[] arr = {5, 3, 8, 4, 2};
        System.out.println("정렬 전: " + Arrays.toString(arr));
        bubbleSort(arr);
        System.out.println("정렬 후: " + Arrays.toString(arr));
    }


}