섹션6. Sort - 2. 버블 정렬

📌 문제 설명

N개의 숫자가 입력되면 버블 정렬(Bubble Sort) 알고리즘을 이용해 오름차순으로 정렬하여 출력하는 프로그램을 작성하세요.

---

📝 입력 & 출력

입력

• 첫 번째 줄에 자연수 N(1 ≤ N ≤ 100)이 주어집니다.
• 두 번째 줄에 N개의 자연수가 공백을 기준으로 입력됩니다.

출력

• 버블 정렬 알고리즘을 이용해 오름차순으로 정렬된 수열을 출력합니다.

---

🔹 예제 입력 & 출력

예제 입력 1

6
13 5 11 7 23 15

 

예제 출력 1

5 7 11 13 15 23

💡 해결 방법

• 버블 정렬은 인접한 두 수를 비교하여 큰 수를 오른쪽으로 이동시키는 방식입니다.
• 한 바퀴 돌 때마다 가장 큰 수가 맨 끝으로 가기 때문에 "거품처럼 올라간다"는 이름이 붙었습니다.
• 총 N-1번 반복하며, 각 회차마다 비교 범위는 점점 줄어듭니다.

---

💻 코드 구현 (Java)

package partSort;

import java.util.*;

public class Problem2 {
	public int[] solution(int n, int[] arr) {
		for (int i = 0; i < n - 1; i++) {
			for (int j = 0; j < n - 1; j++) {
				if (arr[j] > arr[j + 1]) {
					int tmp = arr[j];
					arr[j] = arr[j + 1];
					arr[j + 1] = tmp;
				}
			}
		}
		return arr;
	}

	public static void main(String[] args) {
		Problem2 T = new Problem2();
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		int[] arr = new int[n];
		for (int i = 0; i < n; i++) arr[i] = kb.nextInt();
		for (int x : T.solution(n, arr)) System.out.print(x + " ");
		kb.close();
	}
}

---

📖 코드 설명

for (int i = 0; i < n - 1; i++) {
	for (int j = 0; j < n - 1; j++) {
		if (arr[j] > arr[j + 1]) {
			int tmp = arr[j];
			arr[j] = arr[j + 1];
			arr[j + 1] = tmp;
		}
	}
}

• 바깥 반복문은 총 N-1회 수행
• 안쪽 반복문에서 인접한 두 값을 비교하고, 왼쪽 값이 더 크면 자리를 바꿉니다
• 한 바퀴마다 가장 큰 값이 뒤로 이동함

---

⏳ 시간 복잡도 분석

• 모든 요소를 비교하고 교환해야 하므로 O(N²)

---

출처: 인프런 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비

https://www.inflearn.com/course/자바-알고리즘-문제풀이-코테대비/dashboard

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 강의 | 김태원 - 인프런