[알고리즘] 버블 정렬(Bubble Sort)이란 ?

📁버블 정렬

두 인접한 데이터의 크기를 비교해 정렬하는 방법으로 시간복잡도는 O(n²)이지만, 간단하게 구현할 수 있어 자주 사용한다.

1️⃣ 버블 정렬의 과정

1. 앞에서부터 인접한 데이터 값을 비교한다.
2. 현재 데이터와 다음 데이터를 비교한다.
3. 만약 다음 데이터가 더 작다면 위치를 바꾸고 아니라면 그대로 둔다.
4. 다음 데이터로 이동하여 값을 비교한다.

public class Main {
	public static void main(String[] args) {
		int[] arr = new int[] {5, 4, 1, 3, 2};

     	arr = bubbleSort(arr);

        System.out.println(Arrays.toString(arr));
	}
		
	static int[] bubbleSort(int[] arr) {
		for(int i = 0; i < arr.length - 1; i++) {
			for(int j = 1; j < arr.length - i; j++) {
				// 앞 인덱스 데이터와 뒷 인덱스 데이터와 비교해서 앞이 더 크면 위치 변경
				if(arr[j] < arr[j-1]) {
					int tmp = arr[j-1];
					arr[j-1] = arr[j];
					arr[j] = tmp;
				}
			}
		}
	}
}

2️⃣ 버블 정렬 정리

1. 제자리 정렬(In-Place Sort)이다.

   • 입력 배열 내에서 정렬이 수행되므로 별도의 추가 메모리가 필요하지 않는다.

2. 버블 정렬은 간단한 만큼 빠른 속도로 수행되지 않아 효율적으로 알고리즘을 짜야하는 경우에는 거의 사용되지 않는다.

3️⃣ 정렬 알고리즘 시간복잡도 비교

4️⃣ 버블 정렬 코딩테스트 예제

2750. 수 정렬하기

📌 문제 탐색하기

🌝 입력

1. N개의 수가 주어진다. (1 <= N <= 1,000)
2. N개의 줄에 수가 주어진다. 이 값은 절댓값이 1,000보다 작거나 같은 정수이고 중복되지 않는 값이다.

🌑 출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

🕔 시간제한

1초

🚨 접근

버블 정렬을 활용해 정렬해보자.

• Java에서 제공하는 정렬을 하면 되지만 버블 정렬 공부를 위해 버블 정렬을 통해 정렬을 해보자.

🙆‍♂️ 가능한 시간복잡도

시간 초과는 고려할 사항이 아니다.

• N이 1,000개이기 때문에 이중으로 반복을 수행해도 1,000,000이기 때문에 시간 초과를 생각해야할 문제는 아니다.

📌 문제 풀이

1. N개의 수를 배열에 담는다.
2. 버블 소트를 이용해 N개의 수를 정렬한다.

📌 정답 코드

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

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		int[] arr = new int[n+1];
		for(int i = 1; i < n+1; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		
		bubbleSort(n, arr);
        
        StringBuilder sb = new StringBuilder();
        for(int i = 1; i < n+1; i++) {
            sb.append(arr[i]).append("\n");
        }
        System.out.println(sb);
	}
	
	static void bubbleSort(int n, int[] arr) {
		
		for(int i = 1; i <= n+1; i++) {
			for(int j = 1; j <= n-i; j++) {
				if(arr[j] > arr[j+1]) {
					int temp = arr[j];
					arr[j] = arr[j+1];
					arr[j+1] = temp;
				}
			}
		}
	}
}