[ 정렬 ] 버블 정렬, 선택 정렬 (백준 2750, 1427)

 버블 정렬(Bubble sort) : O(n²)

데이터의 인접 요소끼리 비교하고, swap연산을 수행하며 정렬하는 방식

인접한 요소끼리 비교하고 가장 큰 수를 오른쪽으로 보내면서 진행한다.

1️⃣  비교 연산이 필요한 루프 범위를 설정한다.

2️⃣  인접한 데이터 값을 비교한다.

3️⃣  swap 조건에 부합하면 swap연산을 수행한다.

4️⃣  루프 범위가 끝날 때까지 2️⃣ ~ 3️⃣ 을 반복한다.

5️⃣  정렬 영역을 설정하고, 다음 루프를 실행할 때는 이 영역을 제외한다.

6️⃣  비교 대상이 없을 때까지 1️⃣ ~ 5️⃣ 를 반복한다.

☝🏻 만약 특정한 루프의 전체 영역에서 swap이 한 번도 발생하지 않았다면 그 정렬은 정렬되었다는 뜻이다.!

 

 2750 : 수 정렬하기

문제

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

 

입력

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

 

출력

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

실행 코드

import java.util.Scanner;
public class P2750 {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        // 입력 받기
        int N = sc.nextInt();
        int[] A = new int[N];
        for(int i=0;i<N;i++){
            A[i] = sc.nextInt();
        }

        // 버블 정렬(Bubble Sort)
        for(int i=0;i<N;i++){
            int num = 0;
            for(int j = 0;j<N-i-1;j++){
                if(A[j]<A[j+1]){
                    continue;
                }else{
                    int swap = A[j];
                    A[j] = A[j+1];
                    A[j+1] = swap;
                    num++;
                }
            }
            if(num==0)
                break;
        }

        // 출력
        for(int i=0;i<N;i++){
            System.out.println(A[i]);
        }
    }
}

 

 

 선택 정렬(Selection sort) : O(n²)

최대나 최소 데이터를 데이터가 나열된 순으로 찾아가며 선택하는 방법

1️⃣  남은 정렬 부분에서 최솟값 또는 최댓값을 찾는다.

2️⃣  남은 정렬 부분에서 가장 앞에 있는 데이터와 선택된 데이터를 swap한다.

3️⃣  가장 앞에 있는 데이터의 위치를 변경해 남은 정렬 부분의 범위를 축소한다.

4️⃣  전체 데이터 크기만큼 index가 커질 때까지, 즉 남은 정렬 부분이 없을 때까지 반복한다.

💡 시간 복잡도 계산하기

첫번째 선택 : N

두번째 선택 : N-1

세번째 선택 : N-2

          · · ·

마지막 선택 : N-N

이러한 선택이 총 N번이 실행된다. 즉 시간복잡도가 O(n²)

 

 1427 : 소트인사이드

문제

배열을 정렬하는 것은 쉽다. 수가 주어지면, 그 수의 각 자리수를 내림차순으로 정렬해보자.

 

입력

첫째 줄에 정렬하려고 하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다.

 

출력

첫째 줄에 자리수를 내림차순으로 정렬한 수를 출력한다.

 

문제 풀이

• 입력 값을 String으로 받고 substring()함수로 자릿수 단위로 나눈다. 이를 다시 int형으로 바꾼다.
  substring(startIdx, endIdx) 이렇게써야함미다....안그러면 저처럼 이상한 결과가 나와여.....여기서 endIdx는 불포함!endIdx전까지 자릅니당~

오른쪽이 맞습니당~

 

실행 코드

import java.util.Scanner;

public class P1427 {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        // 입력 받기
        String str = sc.next();
        int[] A = new int[str.length()];
        for(int i=0;i<str.length();i++){
            A[i] = Integer.parseInt(str.substring(i, i+1));
        }

        // 선택 정렬(Selection Sort)
        for(int i=0;i<str.length();i++){
            int idx = i;
            for(int j=i;j<str.length();j++){
                if (A[idx] < A[j]) {
                    idx = j;
                }
            }
            // 불필요한 swap을 줄임
            if(A[i]<A[idx]){
                int temp = A[idx];
                A[idx] = A[i];
                A[i] = temp;
            }
        }

        // 출력
        for(int i=0;i<str.length();i++)
            System.out.print(A[i]);
    }
}