알고리즘 - 버블정렬

이번 시간에는 정렬 중 버블정렬에 대해 알아보겠습니다

핵심이론

버블 정렬은 두 인접한 데이터의 크기를 비교해 정렬하는 방법입니다

간단하게 구현할 수 있지만 시간 복잡도는 O(n^2)으로 다른 정렬 알고리즘보다 속도가 느린편이다

위에서는 오름차순으로 정렬한다고 가정합니다

1번째 루프에서의 결과값에서 보장되는 것은 가장 우측의 수가 가장 큰 수로 정렬되는 것입니다

이런 현상이 일어나는 이유는 정렬을 위한 비교 방향이 왼쪽에서 오른쪽으로 진행되기 때문입니다

만약 오른쪽에서 왼쪽으로 비교 방향이 진행된다면 1번째 루프에서의 결과값에서 보장되는 것은 가장 왼쪽의 수가 가장 작은수가 정렬되는 것입니다

여기서 중요한 부분은 정렬된 영역입니다

가장 오른쪽을 보면 파란색으로 표시된 부분이 있을텐데요 그 부분이 의미하는 것은 정렬이 완료된 범위이며 다음루프를 돌때는 해당 영역을 제외한 범위에 대해 정렬을 진행합니다

그러므로 for 문에서는 N-1-i 의 범위에 대해 루프문을 수행합니다 여기서 i가 의미하는 것은 정렬이 완료된 범위입니다

시간복잡도

버블정렬의 시간복잡도는 O(N^2) 입니다

원소의 개수를 N개라고 가정하면

매번 루프를 돌때 N-1-i 번의 인접한 원소들을 비교하며 swap하기때문에 N 의 시간복잡도가 발생하고
해당 루프를 총 N-1번 진행하기 때문에 총 N^2 가 됩니다

백준 2750

package org.example;

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

public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        StringTokenizer st;
        int[] arr = new int[N];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            arr[i] = Integer.parseInt(st.nextToken());
        }

		
        for (int i = 0; i < N-1; i++) {
        	// swap() 진행
            for (int j = 0; j < N - 1 - i; j++) {
                swap(arr, j, j + 1);
            }
        }

        for (int i = 0; i < N; i++) {
            System.out.println(arr[i]);
        }


    }

    static void swap(int[] arr, int a, int b) {
        if (arr[a] > arr[b]) {
            int tmp = arr[b];
            arr[b] = arr[a];
            arr[a] = tmp;
        }
    }
}

위 코드에서도 볼 수 있다 시피 swap() 을 진행하는 for 문에서 범위가 J < N - 1 - i; 인 것을 볼 수 있습니다

이러한 이유는 정렬된 범위에 대해 swap()을 진행할 필요가 없기 때문이며 나머지 영역에 대해서 swap() 여부를 if문으로 확인한 뒤 진행합니다