[백준] 2750

정렬

정렬은 보통 라이브러리를 사용한다.
다만, 정렬을 구현하는게 목적인 경우 다음 3가지를 통해 정렬이 가능하다.

• 버블 정렬
  앞과 뒤를 연속적으로 비교해서 큰 숫자를 찾는다.
  한번 정렬하면 가장 큰 숫자가 맨뒤에 있다.
  반복해서 큰 숫자를 뒤로 보내며 정렬을 한다.
  
  
• 선택 정렬
  맨 앞을 두고 뒤에서 가장 작은 숫자를 찾는다.
  해당 가장 작은 숫자와 맨 앞의 숫자를 비교해서, 맨 앞이 더 크면 자리를 바꾼다.
  한번 정렬하면 가장 작은 숫자가 맨 앞에 있다.
  반복해서 작은 숫자를 앞으로 가져오며 정렬을 한다.
  
  
• 삽입 정렬
  두번째 이후의 숫자를 선택한다.
  이전 숫자들과 비교해서 나보다 큰수들은 한칸 씩 당기고
  나보다 작은 숫자가 나오면 그 다음 자리에 본인을 넣는다.
  한번 정렬하면 0번과 1번 숫자들은 서로 정렬이 되어 있다.
  계속해서 새로운 숫자들을 추가하며 넣을 자리를 비교하여 넣는다.

정렬 구현

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

public class Main {

    public static void main(String[] args) throws Exception {
        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++) {
                if(arr[j] > arr[j+1]) { // 앞에 있는 수가 더 크면
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
        
        // 선택 정렬 (앞에서부터 작은 수 채우기)
        for(int i=0; i<N-1; i++) {
            int minIdx = i;
            for(int j=i+1; j<N; j++) {
                if(arr[j] < arr[minIdx]){
                    minIdx = j; // 가장 작은 수의 인덱스로 업데이트
                }
            }
            if(arr[minIdx] < arr[i]) {
                int temp = arr[i];
                arr[i] = arr[minIdx];
                arr[minIdx] = temp;
            }
        }

        // 삽입 정렬 (선택한 값이 들어갈 자리 찾기)
        for(int i=1; i<N; i++) {
            int key = arr[i];
            int j = i-1;

            while(j >= 0 && key < arr[j]) {
                arr[j+1] = arr[j];
                j --;
            }
            arr[j+1] = key;
        }
        
        // 라이브러리 정렬
        Arrays.sort(arr);

        for(int i=0; i<N; i++) {
            bw.write(arr[i]+"\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }
}