버블 정렬

설명

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

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

 

입력

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

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

 

출력

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

 

예시 입력 1 

6
13 5 11 7 23 15

 

예시 출력 1

5 7 11 13 15 23

 

 

문제 해결

 

버블 정렬이란?

서로 인접한 두 원소를 비교해 정렬하는 알고리즘이다.
( 비눗방울은 가까이 있으면 합쳐지구.. 예전에 이렇게 외웠었는데..! )
앞에서부터 옆 자료와 비교해 순서대로 정렬되어 있지 않으면 교환하는 방식으로 진행된다.

 

 

버블 정렬이 끝 자료까지 1회전 진행되면 가장 큰 자료는 맨 뒤에 위치하게 된다.

2회전에서는 끝에서 2번째 자료까지 정렬이 되어있고 .. 이런 방식이므로 회전이 진행될수록 비교하는 횟수가 줄어드는 것이 이 구현의 핵심일 것 같다.

 

그럼 코드로 구현해보자. 선택정렬과 마찬가지로 외부  for문은 주어진 자료보다 1작은만큼 반복된다.

for(int i = 0; i < N-1; i++)

 

아까 핵심이라고 말했던 내부 for문 부분이다.

돌아간 회전 횟수만큼 정렬이 이미 진행되어있기 때문에 N-1에서 i를 빼준만큼 for문을 반복해주면 된다!!

 

for(int j = 0; j < N-1-i; j++)

 

이 내부 for문 안에서 현재 위치와 바로 다음 인덱스의 값을 비교하여 만약 현재 값이 더 크다면 둘을 교환하는 코드를 작성해준다.

if (num[j] > num[j+1]) {
    int temp = num[j];
    num[j] = num[j+1];
    num[j+1] = temp;
}

 

 

최종 코드

 

import java.util.Arrays;
import java.util.Scanner;

public class P02_버블정렬 {
    public static void main(String[] args) {

        /** 이웃끼리 비교 후 교환 **/
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int[] num = new int[N];

        for(int i = 0; i < N; i++) {
            num[i] = in.nextInt();
        }

        for(int i = 0; i < N-1; i++) {
            for(int j = 0; j < N-1-i; j++) { //돈 i만큼 빼주고 돔 (그 만큼은 정렬되어있기 때문)
                if (num[j] > num[j+1]) {
                    int temp = num[j];
                    num[j] = num[j+1];
                    num[j+1] = temp;
                }
            }
        }

        for (int i : num) {
            System.out.print(i + " ");
        }


    }
}