[Do it! 알고리즘 코딩 테스트 자바] 버블 정렬과 선택 정렬 - 백준 1377 / 1427(7일차)

1. 버블 정렬 (Bubble Sort)

• 정의: 두 인접한 데이터의 크기를 비교해 swap 연산으로 정렬함.
• 시간 복잡도: O(N^2)
• 특징 (비대칭성과 병목 현상):
  • 오른쪽 이동: 큰 숫자는 조건만 맞으면 한 번의 루프에서 끝까지 빠르게 이동 가능함.
  • 왼쪽 이동 (병목 지점): 작은 숫자는 한 번의 루프에서 아무리 작아도 무조건 왼쪽으로 딱 1칸만 이동함. j와 j+1을 비교해서 j가 더 크면 바꾸는 방식이기 때문임.
  • 결론: 정렬이 완료되려면 모든 숫자가 제자리에 가야 함. 오른쪽으로 가야 할 원소들은 한 번에 이동해 금방 끝나지만, 왼쪽으로 멀리 가야 하는 원소들은 한 번에 한 칸씩밖에 못 가므로 정렬의 속도를 결정하는 병목이 됨.

2. 선택 정렬 (Selection Sort)

• 정의: 대상 데이터에서 최대(혹은 최소) 데이터를 찾아가며 선택적으로 자리를 교환해 정렬함.
• 시간 복잡도: O(N^2)
• 특징: 구현이 직관적이나, 버블 정렬과 마찬가지로 데이터의 개수가 많아질수록 효율이 급격히 떨어짐.

정렬 문제에서의 사고방식

• 정렬 전과 후의 위치(Index)를 비교해 보며 인덱스 변화 관찰하는 습관을 들이기!

 

---

백준 1377번: 버블 소트

1. 주요 오개념 및 시행착오 (Pain Point)

• 단편적 역전 확인의 함정: 인접한 원소의 크기 비교(A[i] > A[i+1])만으로 전체 정렬 횟수를 파악하려 한 점. 이는 특정 원소가 제자리를 찾기 위해 배열을 가로지르는 전체 이동 거리를 반영하지 못하는 오개념임.
• 루프 단위의 진행 간과: 버블 정렬은 한 번의 외부 루프 안에서 여러 번의 교환이 연쇄적으로 일어남. 단순 교환 횟수가 아닌, 원소가 제자리를 찾아가기 위해 필요한 '전체 루프의 반복 횟수'를 구해야 함.

2. 핵심 원리 및 수학적 근거 (Logic & Math)

• 버블 정렬의 비대칭성: 원소가 오른쪽으로 이동할 때는 조건만 맞으면 한 번의 루프에서 제자리까지 끝까지 밀려갈 수 있음. 반면, 작은 숫자가 왼쪽으로 이동할 때는 한 번의 루프에서 정확히 1칸만 이동 가능함.
• 수학적 모델링: 배열 전체가 정렬되기 위해 필요한 루프 횟수는, 가장 멀리서 왼쪽으로 이동해야 하는 원소의 이동 거리와 동일함.
• 최종 결과: 모든 원소가 제자리를 찾은 후, 정렬 완료를 확인하기 위해 마지막으로 실행되는 추가 루프 1회를 더하여 최종 정답은 max(정렬 전 인덱스 - 정렬 후 인덱스) + 1이 됨.

3. 설계 통찰

• 시뮬레이션에서 수학적 특성으로의 전환: 주어지는 N의 크기가 최대 500,000이므로, O(N^2)인 버블 정렬을 직접 시뮬레이션하면 무조건 시간 초과가 발생함.
• 관점의 전환: 알고리즘의 단순 진행 과정을 묻는 문제를, 알고리즘의 구조적 특성(인덱스 변화)을 이용한 O(N log N) 정렬 문제로 우회하여 치환

4. 구현상의 유의점 (Implementation Wisdom)

• 원형 데이터 보존: 배열을 단순히 정렬해버리면 원래의 인덱스 정보를 잃게 되므로, 초기 값과 인덱스를 하나의 객체로 묶어서 저장해야 함.
• 객체 정렬: Comparable 인터페이스를 구현한 커스텀 클래스(Node)를 작성하고, compareTo 메서드를 오버라이딩하여 값 기준 오름차순으로 정렬되도록 객체 지향적으로 설계하는 것이 안전하고 깔끔함.
• Comparable 인터페이스 구현 시 조건 누락 주의: compareTo 메서드 작성 시 두 값이 같은 경우(0 반환)를 누락하고 1과 -1만 반환하게 되면, 자바의 정렬 알고리즘(TimSort)이 요구하는 엄격한 비교 규칙을 위반하게 됨. 이로 인해 런타임 에러(IllegalArgumentException)가 발생하므로, 반드시 0을 반환하는 조건을 포함하거나 단순 뺄셈(this.value - o.value)을 활용하여 명확한 대소 비교 기준을 마련해야 함.

---

백준 1427번: 소트인사이드

• 출력 타입의 오류: 문자열이 아닌 숫자로 출력해야 함(문제 잘 읽기)
• StringBuilder의 활용: 문자열을 조작할 때는 내부 버퍼를 사용하여 문자열을 이어 붙이는 StringBuilder를 사용하고, 마지막에 한 번만 출력(System.out.println(sb))하는 습관을 들이는 것이 훨씬 효율적임.