[PS] 인프런 강의 - Sorting and Searching 2. 버블 정렬

 

문제

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

▣ 입력설명
첫 번째 줄에 자연수 N(1<=N<=100)이 주어집니다.
두 번째 줄에 N개의 자연수가 공백을 사이에 두고 입력됩니다. 각 자연수는 정수형 범위 안에 있습니다.

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

▣ 입력예제 1
6
13 5 11 7 23 15

▣ 출력예제 1
5 7 11 13 15 23

 

풀이

 

❗ 정렬의 회전 횟수 및 비교횟수

정렬은 기본적으로 1번의 회전이 끝나고 찾은 배열의 최소값이나 최대값을, 맨앞이나 맨뒤의 값과 교체하는 것이다.

한 번의 회전 당 하나의 값이 정렬되는 꼴인데,

n개의 값을 정렬한다고 할 때, n-1개를 정렬하면 나머지 하나는 저절로 정렬되기 때문에 n-1번의 회전이 필요하게 된다.

그리고 n개의 값이 있다고 할 때, 맨 마지막 값은 비교할 필요가 없기 때문에 두 값을 비교하는 횟수는 n-1번이면된다.

 

 

버블정렬(Bubble Sort) : 2개의 인접한 데이터를 비교해서 자리를 바꾸는 정렬 

•  n-1번의 회전이 필요하다. 예를 들어 6개의 경우 5회전을 한다.
• 이렇게 정렬하면 1회전이 끝났을 때 최소값 또는 최대값이 맨뒤에 가게된다.
  • 즉 뒤쪽부터 앞으로 ← 쌓인 정렬된 값을 제외해가며 체크해야 한다.
•  i회전 이면 n-i개를 비교한다 그런데 마지막 하나는 비교할 필요가 없으므로 결론적으로! n-i-1번 체크
  • 2회전의 경우 정렬된 맨마지막 1개를 뺀 5개, 인접한 값을 4번(6-1-1) 비교
  • 3회전의 경우 정렬된 마지막 2개를 뺀 4개,  인접한 값을 3번(6-2-1) 비교
• 시간 복잡도 O(n²)

gif 출처

 

코드

import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);

		int n = in.nextInt();
		int[] arr = new int[n];
		for(int i=0; i<n; i++) {
			arr[i] = in.nextInt();
		}
		//버블 정렬 오름차순, 2개중에 뒤쪽을 기준으로 체크 j i
		for(int i=1; i<=n-1; i++) { //1회전부터 셋을 때 n-1번의 회전
			for(int j=0; j<=n-i-1; j++) { //n-i-1번 비교
				if(arr[j] > arr[j+1]) {
					//swap
					int tmp = arr[j];
					arr[j] = arr[j+1];
					arr[j+1] = tmp;
				}
			}
		}
		
		for(int x : arr) {
			System.out.print(x+" ");
		}
	}
}