버블 정렬(Bubble Sort)

버블 정렬(Bubble Sort)

버블 정렬은 인접한 두 요소를 비교해서 큰 값을 뒤로 보내는 방식으로 작동합니다.
여러 번 반복하면서 가장 큰 값이 뒤로 가는 정렬입니다.

이제 코드로 구현해 보겠습니다. 코드로 구현 할 때의 핵심은 다로 for문을 어떻게 쓰냐인데요, 한번 살펴보도록 하겠습니다.

📌 문제 버블 정렬

설명

N개이 숫자가 입력되면 오름차순으로 정렬하여 출력하는 프로그램을 작성하세요.

정렬하는 방법은 버블정렬입니다.

입력

첫 번째 줄에 자연수 N(1<=N<=100)이 주어집니다.

두 번째 줄에 N개의 자연수가 공백을 사이에 두고 입력됩니다. 각 자연수는 정수형 범위 안에 있습니다.

출력

오름차순으로 정렬된 수열을 출력합니다.

예시 입력 1

6
13 5 11 7 23 15

예시 출력 1

5 7 11 13 15 23

코드로 살펴보기

public class Main {
	public int[] solution(int n, int arr[]) {
		for(int i = 0; i < n-1; i++) {
			
			for(int j = 0; j < n-1-i; j++) {
				if(arr[j] > arr[j+1]) {
					int temp = arr[j];
					arr[j] = arr[j+1];
					arr[j+1] = temp;
				}
			}
		}
		
		return arr;
	}
	
	public static void main(String[] args) {
		Main T = new Main();
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int arr[] = new int[n];
		
		for(int i = 0; i < n; i++) {
			arr[i] = sc.nextInt();
		}
		
		for(int i : T.solution(n, arr)) {
			System.out.print(i + " ");
		}
	}
}

✔️ 문제 풀이

N개의 숫자가 입력되면, 이를 버블 정렬을 이용하여 오름차순으로 정렬한 뒤 출력하는 프로그램을 작성합니다.

버블 정렬은 인접한 두 수를 비교하여 왼쪽 수가 오른쪽 수보다 크면 자리를 바꾸는 방식입니다.
이 과정을 반복하면, 가장 큰 수가 점점 오른쪽 끝으로 이동하게 됩니다.

바깥쪽 for문은 전체 배열을 몇 번 반복할지를 나타내며, 배열의 크기가 N이라면 최대 N-1번 반복하면 정렬이 완료됩니다.

안쪽 for문은 이웃한 숫자들끼리 비교하는 부분으로, 한 번 반복할 때마다 가장 큰 수 하나가 뒤로 확정되므로, N - 1 - i까지만 비교하면 됩니다.

버블 정렬은 이중 for문으로 구성되므로, 전체 시간 복잡도는 O(n²) 입니다.