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

Selection Sort, 선택 정렬

선택된 값과 나머지 데이터를 비교하여 알맞은 자리를 찾는 알고리즘

첫 번째 값을 선택하고 두 번째 값부터 순회하면서 제일 작은 값을 첫 번째 값과 바꿈 두 번째 값을 선택하고 세 번째 값부터 순회하면서 제일 작은 값을 두 번째 값과 바꿈 … 반복

시간 복잡도: O(n^2)

Bubble Sort, 버블 정렬

배열을 계~속 순회하면서 앞뒤 원소가 오름차순이 아니면 둘이 바꿈

Insertion Sort, 삽입 정렬

데이터 집합을 순회하면서 정렬이 필요한 요소를 뽑아 적당한 곳으로 삽입

시간 복잡도: O(n^2)

Quick Sort, 퀵 정렬

분할 정복

임의의 기준 값(pivot)을 정하고 해당 피벗을 기준으로 두 개의 부분 집합으로 나눔 왼쪽에는 피벗보다 작은 값들만, 오른쪽에는 큰 값들만 더 이상 쪼갤 수 없을 때까지 쪼개기

Merge Sort, 병합 정렬

분할 정복

둘 이상의 부분 집합으로 가르고 갈라서 정렬한 후 합치기 부분 배열을 위한 추가 메모리 공간이 필요

시간 복잡도: O(n log n)

Heap Sort, 힙 정렬

트리 기반으로 최대/최소 힙 트리를 구성하여 정렬(asc: 최소 힙, desc: 최대 힙) 완전 이진 트리여야 함

*힙: 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있는 느슨한 정렬 트리, 중복 값 허용

*완전 이진 트리: 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 모든 노드 또한 왼쪽으로 몰아져 있는 것

시간 복잡도: O(n log n)

 

 

 

정답 코드

1. 버블 정렬

/* bubble sorting */

import java.io.*;
public class Main {
    public static void main(String args[]) throws IOException {
        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; i++) {
            for (int j=0; j<n-1; 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; i++) {
            bw.write(Integer.toString(arr[i]));
            bw.newLine();
        }

        br.close();
        bw.flush();
        bw.close();
    }
}

 

2. Collection 내 메서드 사용

import java.io.*;
import java.util.*;
public class Main {
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());
        List<Integer> list = new ArrayList<>();
        for (int i=0; i<n; i++) {
            list.add(Integer.parseInt(br.readLine()));
        }

        Collections.sort(list);
        for (int i=0; i<n; i++) {
            bw.write(Integer.toString(list.get(i)));
            bw.newLine();
        }

        br.close();
        bw.flush();
        bw.close();
    }
}