[코드트리] 오름차순으로 정렬 - 자바(Java)

문제

https://www.codetree.ai/training-field/search/problems/sort-in-ascending-order?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

n개의 정수가 주어졌을 때, 오름차순으로 정렬하여 출력하는 프로그램을 작성해 보세요.

 

 

코드

첫 번째 줄에 정수 n이 주어지고, 두 번째 줄에 n개의 정수가 공백으로 구분되어 주어진다.

• 1 <= n <= 100
• 1 <= 주어지는 수 <= 200

 

Arrays.sort()

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

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());
        StringTokenizer st = new StringTokenizer(br.readLine());

        int[] arr = new int[n];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(arr);

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(arr[i]).append(" ");
        }

        System.out.println(sb);
    }
}

 

 

삽입 정렬

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

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());
        StringTokenizer st = new StringTokenizer(br.readLine());

        int[] arr = new int[n];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        for (int i = 1; i < n; i++) {
            int temp = arr[i]; // 현재 숫자
            int j = i - 1; // 정렬을 위한 위치
            
            // j가 0보다 크고, arr[j]가 temp보다 크면 반복
            while (j >= 0 && arr[j] > temp) {
                arr[j + 1] = arr[j]; // 오른쪽으로 이동
                j--; // j 감소
            }
            
            arr[j + 1] = temp;
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(arr[i]).append(" ");
        }

        System.out.println(sb);
    }
}

 

병합 정렬

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

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());
        StringTokenizer st = new StringTokenizer(br.readLine());

        // 입력받은 정수 배열에 담기
        int[] arr = new int[n];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        // 병합 정렬
        sort(arr, 0, n - 1);

        // 출력
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(arr[i]).append(" ");
        }

        System.out.println(sb);
    }

    private static void sort(int[] arr, int left, int right) {
        if (left == right) {
            return;
        }

        // 중간 인덱스
        int mid = (left + right) / 2;

        // 왼쪽 정렬
        sort(arr, left, mid);
        // 오른쪽 정렬
        sort(arr, mid + 1, right);

        // 배열 합치기
        merge(arr, left, mid, right);
    }

    private static void merge(int[] arr, int left, int mid, int right) {
        int n1 = mid - left + 1; // 왼쪽 배열의 길이
        int n2 = right - mid; // 오른쪽 배열의 길이

        // 왼쪽 배열 오른쪽 배열
        int[] leftTemp = new int[n1];
        int[] rightTemp = new int[n2];

        // 왼쪽 배열 담기
        for (int i = 0; i < n1; i++) {
            leftTemp[i] = arr[left + i];
        }
        // 오른쪽 배열 담기
        for (int i = 0; i < n2; i++) {
            rightTemp[i] = arr[mid + 1 + i];
        }

        // 왼쪽 배열과 오른쪽 배열의 인덱스
        int i = 0, j = 0;
        // 원본 배열 arr의 시작 인덱스
        int k = left;

        // 원본 배열에 정렬
        while (i < n1 && j < n2) {
            if (leftTemp[i] <= rightTemp[j]) {
                arr[k] = leftTemp[i];
                i++;
            } else {
                arr[k] = rightTemp[j];
                j++;
            }
            k++;
        }

        // 정렬 후 남아 있는 요소 담기
        while (i < n1) {
            arr[k] = leftTemp[i];
            i++;
            k++;
        }

        while (j < n2) {
            arr[k] = rightTemp[j];
            j++;
            k++;
        }
    }
}