JAVA 백준 문제풀이 (18) 2750:수 정렬하기

 

시간 복잡도가 O(N＾²)인 정렬 알고리즘을 연습하기 위한 기초 문제이다.

 

https://7357.tistory.com/137 

 

거품 정렬에 대한 포스팅에 이 문제를 예제로 작성했기 때문에 설명을 생략한다.

삽입 정렬 및 선택 정렬은 추후 포스팅 예정.

 

 

 

정답 1.

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

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()); // 배열의 크기를 정하는 입력값
        int[] arr = new int[N];

        for (int i=0; i<N; i++) { // 배열에 해당 수들을 추가
            arr[i] = Integer.parseInt(br.readLine());
        }

        for (int i=0; i<arr.length-1; i++) { 
            for (int j=0; j<arr.length-1-i; j++) { // 매 반복마다 반복 횟수가 줄어든다
                if (arr[j]>arr[j+1]) { // 만약 우측의 값이 좌측보다 작다면 위치를 바꾼다
                    int temp = arr[j]; // swap이 없기 때문에 별도 임시 변수를 만들어줘야 한다.
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }

        for (int num : arr) {
            System.out.println(num);
        }
        }
    }
출처: https://7357.tistory.com/137 [응애. 나 애기 개발자.:티스토리]

 

 

정답 2.

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

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());
        int[] arr = new int[N];

        for (int i=0; i<N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        for (int i=0; i<arr.length-1; i++) {
        boolean isChanged = false; // 정렬 작업이 수행되고 있는지 체크
            for (int j=0; j<arr.length-1-i; j++) {
                if (arr[j]>arr[j+1]) {
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                    isChanged = true; // 정렬 작업이 수행되었다면 true
                }
            }
            if (!isChanged) { break; } // 배열을 순회하며 단 한 번도 반복되지 않았다면 비교를 멈춘다
        }

        for (int num : arr) {
            System.out.println(num);
        }
        }
    }
출처: https://7357.tistory.com/137 [응애. 나 애기 개발자.:티스토리]