[백준/자바] 2750번 수 정렬하기 - 선택정렬, 삽입정렬, 버블정렬

• 문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

 

 

• 코드

간단한 정렬 문제인데 나는 정렬 알고리즘에 대해 처음 학습하고 있는 입장이라 기본적인 정렬 세가지를 모두 사용해봤다. 

셋 다 상대적으로 구현이 쉬운 정렬인데, 그만큼 속도가 느릴 수 있다. (평균 시간복잡도 = n^2)

참고 링크

 

 

1. 선택 정렬

맨앞에서부터 다른 인덱스 숫자들과 비교하며 최소값 찾아 순차 배치시키는 정렬

 

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

public class SelectionSort {

    public static void sort (int count, int[] numbers){
        //선택 정렬
        //매 루프마다 최솟값 찾아 순차 배치
        int temp;
        for (int i=0;i<count-1;i++){ //비교 기준 숫자
            for (int j=i+1;j<count;j++){ //비교되는 숫자들
                if (numbers[i]>numbers[j]){
                    temp = numbers[i];
                    numbers[i] = numbers[j];
                    numbers[j] = temp;
                }
            }
        }
    }

    public static void main(String[] args) throws NumberFormatException, IOException {
        //N개의 수 오름차 정렬 (선택정렬 사용)
        //1 ≤ N ≤ 1,000, 숫자 증복 X
        //1번째 입력값은 숫자들 개수(N), 그 이후 입력값은 숫자들

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int count = Integer.parseInt(br.readLine());

        //입력 숫자들 배열에 대입
        int[] numbers = new int[count];
        for (int i=0;i<count;i++){
            numbers[i] = Integer.parseInt(br.readLine());
        }

        //정렬 실행
        sort(count, numbers);

        for (int i=0;i<count;i++){
            System.out.println(numbers[i]);
        }

    }

}

 

 

2. 삽입 정렬

앞에서부터 정렬 시작해 해당 정렬에 삽입해가는 정렬

 

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

public class InsertionSort {

    public static int[] sort (int count, int[] numbers){
        //삽입 정렬
        //인덱스1부터 앞 숫자들과 비교해 삽입해가며 정렬
        for (int i=1;i<count;i++){ //인덱스 1에서부터
            for (int j=0;j<i;j++){ //앞 인덱스들과 대소 비교, 삽입
                int temp;
                if (numbers[i]<numbers[j]){
                    temp = numbers[i];
                    numbers[i] = numbers[j];
                    numbers[j] = temp;
                }
            }
        }

        return numbers;
    }

    public static void main(String[] args) throws NumberFormatException, IOException {
        //1번째 입력값은 숫자들 개수(N), 그 이후 입력값은 숫자들
        //1 ≤ N ≤ 1,000, 숫자 증복 X

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int count = Integer.parseInt(br.readLine());

        //입력값들 배열에 대입
        int[] numbers = new int[count];
        for (int i=0;i<count;i++){
            numbers[i] = Integer.parseInt(br.readLine());
        }

        //정렬 실행
        int[] sortedNumbers = sort(count, numbers);

        for (int i=0;i<count;i++){
            System.out.println(sortedNumbers[i]);
        }

    }

}

 

 

3. 버블 정렬

앞에서부터 인접한 두 숫자를 비교하며 진행하는 정렬

 

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

public class BubbleSort {

    public static int[] sort(int count, int[] numbers){
        //버블 정렬
        //앞에서부터 인접한 숫자 두개 반복 비교
        int temp;
        for (int i=1;i<count;i++){ //숫자 개수-1만큼 루프 실행
            for (int j=0;j<count-i;j++){ //순차적으로 뒤 인덱스는 정렬에서 제외
                if (numbers[j]>numbers[j+1]){
                    temp = numbers[j];
                    numbers[j] = numbers[j+1];
                    numbers[j+1] = temp;
                }
            }
        }
        return numbers;
    }

    public static void main(String[] args) throws NumberFormatException, IOException {
        //N개의 수 오름차 정렬
        //1 ≤ N ≤ 1,000, 숫자 증복 X
        //1번째 입력값은 숫자들 개수(N), 그 이후 입력값은 숫자들

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int count = Integer.parseInt(br.readLine());

        //입력 숫자들 배열에 대입
        int[] numbers = new int[count];
        for (int i=0;i<count;i++){
            numbers[i] = Integer.parseInt(br.readLine());
        }

        //정렬 실행
        int[] sortedNumbers = sort(count, numbers);

        for (int i=0;i<count;i++){
            System.out.println(sortedNumbers[i]);
        }

    }

}