[Do it] 알코테 자바 5일차

05. 정렬

05-1 버블 정렬 (Bubble Sort)

버블 정렬은 인접한 두 요소를 비교하여 순서가 잘못되어 있으면 서로 교환(swap)하는 방식의 정렬 알고리즘이다.

가장 단순한 정렬 알고리즘 중 하나이며, 구현이 매우 쉽다.
하지만 효율이 낮아 실전에서는 거의 사용되지 않는다.

---

1. 동작 원리

배열을 처음부터 끝까지 순회하면서
인접한 두 값을 비교하고, 큰 값을 뒤로 보내는 방식으로 정렬한다.

한 번의 순회가 끝나면
가장 큰 값이 배열의 맨 뒤로 이동하게 된다.

이 과정을 반복하면
마치 거품이 위로 올라가듯이 큰 값이 뒤로 이동한다는 의미에서
“버블 정렬”이라는 이름이 붙었다.

---

2. 예시

배열:
5 3 8 4 2

1회전 후:
3 5 4 2 8

2회전 후:
3 4 2 5 8

3회전 후:
3 2 4 5 8

4회전 후:
2 3 4 5 8

---

3. 시간 복잡도

경우	시간복잡도
최선 (이미 정렬된 경우)	O(N²)
평균	O(N²)
최악	O(N²)

비교 횟수는 항상 약 N²에 비례한다.

따라서 데이터가 많아질수록 매우 비효율적이다.

---

4. 공간 복잡도

• O(1)
• 추가 메모리를 거의 사용하지 않는 제자리 정렬(In-place Sort)

---

5. 특징

• 구현이 가장 단순한 정렬 알고리즘
• 안정 정렬(Stable Sort)
• 대규모 데이터에는 부적합

__[015] 수 정렬하기 1

백준 온라인 져지 2750번 https://www.acmicpc.net/problem/2750

import java.util.*;
import java.lang.*;
import java.io.*;

// The main method must be in a class named "Main".
class Main {
	public static void main(String[] args) {

		Scanner in = new Scanner(System.in);

		int n = in.nextInt();
		int[] arr = new int[n];

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

		// Bubble Sort
		for(int i = 0; i < n - 1; i++) {
			for(int j = 0; j < n - 1 - i; j++) {
				if(arr[j] > arr[j + 1]) {
					int temp = arr[j];
					arr[j] = arr[j + 1];
					arr[j + 1] = temp;
				}
			}
		}

		for(int val : arr) {
			System.out.println(val);
		}
	}
}

__[016] 버블 정렬 프로그램 1

백준 온라인 져지 1377번 https://www.acmicpc.net/problem/1377

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // 1. 입력 받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        int[] A = new int[N + 1]; // 문제는 1번 인덱스부터 사용
        for (int i = 1; i <= N; i++) {
            A[i] = Integer.parseInt(br.readLine());
        }

        // 2. 버블 정렬 수행
        for (int i = 1; i <= N + 1; i++) {
            boolean changed = false;

            for (int j = 1; j <= N - i; j++) {
                if (A[j] > A[j + 1]) {
                    // swap
                    int temp = A[j];
                    A[j] = A[j + 1];
                    A[j + 1] = temp;
                    changed = true;
                }
            }

            // 3. 교환이 한 번도 없으면 종료
            if (!changed) {
                System.out.println(i);
                break;
            }
        }
    }
}

05-2 선택 정렬 (Selection Sort)

선택 정렬은 현재 위치에 들어갈 값을 선택해서 정렬하는 방식의 알고리즘이다.

매 단계마다 최솟값(또는 최댓값)을 찾아서 맨 앞(또는 맨 뒤)으로 이동시키는 방식으로 동작한다.

구현은 단순하지만, 시간 복잡도가 높아 실전에서는 거의 사용되지 않는다.

---

1. 동작 원리

 

오름차순 정렬 기준 설명

1. 첫 번째 위치에 들어갈 최소값을 찾는다.
2. 그 값을 첫 번째 요소와 교환한다.
3. 두 번째 위치에 들어갈 최소값을 찾는다.
4. 반복한다.

즉, 앞에서부터 하나씩 확정해 나가는 정렬 방식이다.

---

2. 예시

 

배열:
5 3 8 4 2

1단계 (최솟값 2 선택 → 맨 앞으로 이동)
2 3 8 4 5

2단계 (남은 부분 중 최솟값 3 → 그대로 유지)
2 3 8 4 5

3단계 (남은 부분 중 최솟값 4 선택)
2 3 4 8 5

4단계 (남은 부분 중 최솟값 5 선택)
2 3 4 5 8

---

3. 시간 복잡도

경우시간 복잡도

최선	O(N²)
평균	O(N²)
최악	O(N²)

선택 정렬은 데이터 상태와 관계없이
항상 동일한 비교 횟수를 수행한다.

비교 횟수는 다음과 같다.

(N-1) + (N-2) + ... + 1
= N(N-1)/2
≈ O(N²)

---

4. 공간 복잡도

• O(1)
• 추가 메모리를 사용하지 않는 제자리 정렬(In-place Sort)

---

5. 특징

• 구현이 매우 단순함
• 교환 횟수가 적음 (최대 N-1번)
• 안정 정렬이 아님 (Stable Sort 아님)
• 데이터가 많을 경우 비효율적

__[017] 내림차순으로 자릿수 정렬하기

백준 온라인 져지 1427번 https://www.acmicpc.net/problem/1427

import java.io.*;

class Main {
    public static void main(String[] args) throws Exception {

        // 입력 받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input = br.readLine();

        // 자리수 배열로 변환
        int[] arr = new int[input.length()];
        for (int i = 0; i < input.length(); i++) {
            arr[i] = input.charAt(i) - '0';
        }

        // 선택정렬 (내림차순)
        for (int i = 0; i < arr.length - 1; i++) {
            int maxIndex = i;

            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] > arr[maxIndex]) {
                    maxIndex = j;
                }
            }

            int temp = arr[i];
            arr[i] = arr[maxIndex];
            arr[maxIndex] = temp;
        }

        // 결과 출력
        StringBuilder sb = new StringBuilder();
        for (int n : arr) {
            sb.append(n);
        }

        System.out.println(sb);
    }
}