[백준] 2750_수정렬하기 / 선택정렬, 버블정렬, 삽입정렬

 

Bronze

 

문제

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

 

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

 

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

 

---

 

import java.util.*;

public class Main_B2750 {

    int arr[];

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] arr = new int[N];

        for(int i=0; i<N; i++){
            arr[i] = sc.nextInt();
        }

        selection(arr, N);
        bubble(arr, N);
        insertion(arr, N);

        for(int num : arr){
            System.out.println(num);
        }
        
        sc.close();
    }
}

 

 

풀이1. 선택정렬

    /* 1. 선택정렬 : 배열에서 해당 자리를 이미 선택하고 그 자리에 오는 값을 찾는 것 */ 
    private static void selection(int[] arr, int N){
        int temp;
        for(int i=0; i<N-1; i++){
            int indexMin = i;
            for(int j=i+1; j<N; j++){
                if(arr[indexMin]>arr[j]) indexMin = j;
            }
            temp = arr[i];
            arr[i] = arr[indexMin];
            arr[indexMin] = temp;
        }
    }

 

배열을 정렬된 부분과 정렬되지 않은 부분으로 나누어, 정렬되지 않은 부분에서 가장 작은(또는 큰) 요소를 선택하여 정렬된 부분의 끝에 추가하는 방식이다. 

 

동작 원리:

 

1. 배열 전체에서 최솟값을 찾아 첫 번째 위치에 놓는다.
2. 나머지 배열에서 최소값을 찾아 두 번째 위치에 놓는다.
3. 배열의 끝까지 반복한다.

시간복잡도:

• 평균, 최선, 최악의 경우: O(n^2)

 

---

 

 

풀이2. 버블정렬

    /* 2. 버블정렬 : 배열 내의 인접한 두개의 Index를 비교하여 더 큰 숫자를 뒤로 보내는 정렬 */ 
    private static void bubble(int[] arr, int N){
        int temp;
        for(int i=0; i<N; i++){
            for(int j=0; j<N-i-1; j++){
                if(arr[j] > arr[j+1]){
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
    }

 

인접한 요소들을 반복적으로 비교하여 순서가 잘못된 경우 서로 교환하는 방식이다.
가장 큰(또는 작은) 요소가 배열의 끝으로 이동하는 과정을 거친다.

 

동작 원리

1. 배열을 반복적으로 순회하면서 인접한 요소들을 비교한다. 
2. 순서가 잘못된 경우 두 요소를 교환한다.
3. 배열의 끝까지 반복하여 가장 큰 요소를 끝으로 이동시킨다. 
4. 이 과정을 배열이 정렬될 때까지 반복한다. 

시간복잡도:

• 평균 및 최악의 경우: O(n^2)
• 최선의 경우: O(n) (이미 정렬된 경우)

 

---

 

풀이3. 삽입정렬

    /* 3. 삽입정렬 : 기준이 되는 숫자와 그 왼쪽에 있는 배열들을 비교하여 조건에 맞게 정렬하는 방법 */ 
    public static void insertion(int[] arr, int N){
        for(int i=1; i<N; i++){
            int num = arr[i]; // 기준
            int j;
            for(j=i-1; j>=0; j--){
                if(arr[j] > num){
                    arr[j+1] = arr[j]; // 이전 원소를 한칸씩 미룬다 
                }
                else break;
            }
            arr[j+1] = num;
        }
    }

 

삽입 정렬은 배열을 정렬된 부분과 정렬되지 않은 부분으로 나누어, 정렬되지 않은 요소를 하나씩 꺼내어 정렬된 부분에 올바른 위치에 삽입하는 방식이다. 

기준이 되는 숫자와 그 왼쪽에 있는 배열들을 비교하여 조건에 맞게 정렬한다. 

 

동작 원리

1. 첫 번째 요소는 이미 정렬된 것으로 간주한다. (i =  1부터 시작)
2. 다음 요소를 선택하여 정렬된 부분의 올바른 위치에 삽입한다. (기준이 되는 수의 왼쪽 배열들을 비교)
3. 배열의 끝까지 반복한다. 

시간복잡도

• 평균 및 최악의 경우: O(n^2)
• 최선의 경우: O(n) (이미 정렬된 경우)

 

 

 

 

---

 

 

https://www.acmicpc.net/problem/2750

 

출처 : chatgpt