백준 2750 수 정렬하기

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

문제해결

정렬 알고리즘에는 버블정렬, 삽입정렬, 퀵정렬 등 다양한 알고리즘이 있어서 직접 구현을 하며 시간복잡도에 대해 공부하였다.

첫 번째 코드는 버블정렬 알고리즘을 구현한 코드이다. 버블정렬은 현재 요소와 다음 요소를 비교하며 현재 요소가 다음 요소보다 크면 교환하는 방식이다. 구현이 매우 쉽다는 장점이 있지만 배열의 길이만큼 2번의 for문을 돌기 때문에 시간복잡도가 O(N^2)으로 크다는 단점이 있다.

소스코드

1. 버블정렬

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

/** 
* 버블정렬
*/

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        bubbleSort(arr);
        for (int a : arr) {
            System.out.println(a);
        }
    }

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