[Sorting] 버블 정렬(BOJ 2750번)

1. 버블 정렬

: 두 인접한 데이터의 크기를 비교하고 swap 연산으로 정렬

1) 시간 복잡도 O(n²)으로 타 정렬 알고리즘보다 오래 걸리는 편. 대신 코드가 간단하다

2) swap 연산

: 두 수의 값을 교환하는 과정.

a와 b의 값을 서로 바꾸고 싶을 때 a=b를 바로 해버리면 a에 들어있던 값이 사라져 교환할 수 없게 된다.  따라서 a의 값을 임의의 변수 temp에 저장해두고 a=b를 수행한 뒤 b=temp를 수행해야 한다

public void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

3) 과정

 인접한 값끼리 비교하며 범위 내의 최댓값을 범위의 맨뒤로 보낸다
 범위를 배열 전체에서 맨뒤부터 하나씩 줄여가며 반복한다

public static void bubbleSort(int[] arr){
    int len = arr.length;
    for(int i=0; i<len-1; i++){
        for(int j=0; j<len-1-i; j++){
            if(arr[j]>arr[j+1])
                swap(arr, j, j+1);
        }
    }
}

 

 

2. 백준 2750번: 수 정렬하기

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

2750번: 수 정렬하기

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 

 

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

 

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

 

난이도

브론즈 2

 

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

public class B2750_수정렬하기 {
    public static void main(String[] args) {
        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();
        }
        // input

        bubbleSort(arr);
        // operation

        for(int i : arr){
            System.out.println(i);
        }
        // output
    }

    public static void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void bubbleSort(int[] arr){
        int len = arr.length;
        for(int i=0; i<len-1; i++){
            for(int j=0; j<len-1-i; j++){
                if(arr[j]>arr[j+1])
                    swap(arr, j, j+1);
            }
        }
    }
}