버블 정렬(Bubble sort)

거품 정렬(bubble sort, sinking sort)은 두 인접한 원소를 검사하여 정렬하는 방법이다. 

시간 복잡도가 O(n^2)로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용된다.

원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이다.

양방향으로 번갈아 수행하면 칵테일 정렬이 된다.

버블 정렬의 시각화

** 시각화 이미지를 보면 알겠지만 오른쪽끝(큰 숫자)부터 정렬이 시작된다

---

문제

설명

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

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

 

입력

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

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

 

출력

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

 

예시 입력 1 

6

13 5 11 7 23 15

 

예시 출력 1

5 7 11 13 15 23

 

 

<구현>

import java.util.*;

public class Main {
    public static int[] solution(int n, int[] arr){
        for(int i=0;i<n-1;i++){
            for(int j=1;j<n-i;j++){
                int prior = arr[j-1];
                int curr = arr[j];

                if(curr < prior){
                    arr[j-1] = curr;
                    arr[j] = prior;
                }
            }
        }
        return arr;
    }

    public static void main(String[] args) {
      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 e : solution(n,arr)){
          System.out.print(e + " ");
      }
    }
}