[Algorithm] bubble sort

bubble sort
O(N^2)

배열에서 이웃한 인덱스끼리 비교하여 자리를 교환한다.

사진 출처 : https://velog.io/@kimjihong9/Bubble-Sort

 

https://www.acmicpc.net/problem/2750

2750번: 수 정렬하기

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

            int N=Integer.parseInt(br.readLine());
            int[] arr=new int[N];
            for(int i=0; i<N; i++){
                arr[i] = Integer.parseInt(br.readLine());
            }

            // 버블 정렬
            for(int i=0; i<N-1; i++){ // 마지막 정렬 시, 데이터 하나를 정렬할 필요가 없으므로
                for(int j=0; j<N-1-i; j++){	// 맨 뒤에서부터 정렬이 차곡차곡 되므로 비교할 횟수가 1증 줄어듬
                    if(arr[j] > arr[j+1]){
                        int temp = arr[j];
                        arr[j] = arr[j+1];
                        arr[j+1] = temp;
                    }
                }
            }

            Arrays.stream(arr).forEach(System.out::println);
        } catch (Exception e) {
            System.out.println(e);
        }
    }
}