Written by Misun
on September 27, 2021

[Java/백준]2750번: 수 정렬하기

Image with caption

알아야 할 개념

삽입정렬(Insertion sort)

삽입 정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다. 배열이 길어질수록 효율이 떨어진다.

버블정렬(Bubble sort)

거품(버블) 정렬은 두 인접한 원소를 검사하여 정렬하는 방법이다. 시간 복잡도가 상당히 느리지만, 코드가 단순하기 때문에 자주 사용된다. 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이다. 양방향으로 번갈아 수행하면 칵테일 정렬이 된다.

추가내용 참고 https://st-lab.tistory.com/195

문제풀이

첫번째 방법: Scanner + 버블정렬

import java.util.Scanner;

class Main_2750 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int n = in.nextInt();

        int[] arr = new int[n];

        for (int i = 0; i < n; i++) {
//            System.out.print("arr[" + i + "] = ");
            arr[i] = in.nextInt();
        }

        bubbleSort(arr, n);

        for (int i = 0; i < n; i++) {
            System.out.println(arr[i]);
        }
    }

    // 값 바꾸기
    static void swap(int[] a, int idx1, int idx2) {
        int t = a[idx1];
        a[idx1] = a[idx2];
        a[idx2] = t;
    }

    // 버블정렬
    static void bubbleSort(int[] arr, int n) {
        for (int i = 0; i < n - 1; i++) {
            for (int j = n - 1; j > i; j--) {
                if (arr[j - 1] > arr[j]) {
                    swap(arr, j - 1, j);
                }
            }
        }
    }
}

두번째 방법: BufferedReader + 삽입정렬

좀 더 가볍고 빠른 BufferedReader를 이용해봤다.

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

public class Insertion_sort {

    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());
        }

        insertionSort(arr, n);

        for (int a : arr) {
            System.out.println(a);
        }
    }

    static void insertionSort(int[] a, int n) {
        for (int i = 1; i < n; i++) {
            int j;
            int tmp = a[i];
            for (j = i; j > 0 && a[j - 1] > tmp; j--) {
                a[j] = a[j - 1];
            }
            a[j] = tmp;
        }
    }

}

Discussion and feedback

← → Top