백준 2750번 | 수 정렬하기 문제 풀이 (Java)

 

제출코드

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

public class Main{

    public static void main(String[] args) throws Exception {
        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());
        }

        // 버블정렬
        // System.out.println("버블정렬");
        // int[] temp = Arrays.copyOf(arr, arr.length);
        // System.out.println(Arrays.toString(temp));
        // bubbleSort(temp);
        // System.out.println(Arrays.toString(temp));

        // System.out.println("선택정렬");
        // temp = Arrays.copyOf(arr, arr.length);
        // System.out.println(Arrays.toString(temp));
        // selectionSort(temp);
        // System.out.println(Arrays.toString(temp));

        // System.out.println("삽입정렬");
        temp = Arrays.copyOf(arr, arr.length);
        // System.out.println(Arrays.toString(temp));
        insertionSort(temp);
        // System.out.println(Arrays.toString(temp));

    }

    // 두 인접한 번호끼리 비교
    // 가장 큰값이 맨뒤로 배치
    public static void bubbleSort(int[] arr) {

        int size = arr.length;

        for(int i = 0; i < size-1; i++) {
            boolean isSwap = false;

            for(int j = 0; j < size - i - 1; j++) {

                // 오름차순이므로
                if(arr[j] > arr[j+1]) {
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                    isSwap = true;
                }
            }

            // 변경을 안했으면 정렬이 된 상태
            if(!isSwap) {
                break;
            }
        }
    }

    // 최솟값 찾기:
    // 위치 교환
    // 반복
    public static void selectionSort(int[] arr) {
        int size = arr.length;

        for(int i = 0; i < size-1; i++) {
            int minIdx = i;

            for(int j = i+1; j < size; j++) {
                if(arr[minIdx] > arr[j]) {
                    minIdx = j;
                }
            }

            if(minIdx != i) {
                int temp = arr[minIdx];
                arr[minIdx] = arr[i];
                arr[i] = temp;
            }

        }
    }

    // 데이터를 한 항목씩 선택하여, 이미 정렬된 부분에 적절한 위치에 '삽입'함으로써 전체 리스트를 정렬하는 알고리즘
    public static void insertionSort(int[] arr) {
        int size = arr.length;

        for(int i = 1; i < size; i++) {
            int key = arr[i];
            int j = i - 1;
            while(j >= 0 && arr[j] > key) {
                arr[j+1] = arr[j];
                j = j - 1;
            }
            arr[j+1] = key;
        }
    }
}

 

 

문제 의도

- 정렬 알고리즘의 이해

 

문제 출처