자료구조 · 알고리즘 기초집LESSON 10

정렬 기초: 비교 정렬과 Comparator 사용법

난이도초급 → 중급 입문

예상 시간40분

선수지식이전 강의

10강. 정렬 기초: 비교 정렬과 Comparator 사용법

1. 이번 강의에서 해결할 문제

랭킹은 점수만 내림차순으로 정하면 동점자의 순서가 불명확합니다. 비교 규칙을 코드로 고정하고 원본 기록 보존 여부도 결정해야 합니다.

2. 학습 목표

3. 핵심 개념

정렬은 원소를 비교 규칙에 따라 순서화합니다. Java의 Comparator는 도메인 객체 밖에서 여러 정렬 기준을 정의하기 좋습니다. 음수·0·양수라는 비교 계약을 지켜야 하며 단순 뺄셈은 정수 overflow 위험이 있습니다. 기록 날짜는 LocalDate처럼 의미가 분명한 타입으로 보관하면 문자열 형식에 기대지 않고 비교할 수 있습니다. List의 표준 정렬은 계약상 안정적이지만 내부 알고리즘 이름을 영구 보장으로 오해하지 않습니다.

4. 단계별 실습

1. 예제 파일 작성

실행 환경: 코드 편집기

실행 위치: C:\dev\game-ranking-algorithms

실행 전 확인: 같은 이름의 파일이 있다면 덮어쓰기 전에 Git diff로 변경 범위를 확인합니다. 선택한 LTS JDK의 java -version과 javac -version이 모두 실행되어야 합니다.

대상 파일: src/RankingSort.java

src/RankingSort.java
import java.time.LocalDate;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class RankingSort {
    record GameRecord(String playerId, int score, int playSeconds, LocalDate playedOn) {}

    public static void main(String[] args) {
        List<GameRecord> original = List.of(
                new GameRecord("P2", 1200, 80, LocalDate.parse("2026-07-03")),
                new GameRecord("P1", 1500, 95, LocalDate.parse("2026-07-02")),
                new GameRecord("P3", 1200, 70, LocalDate.parse("2026-07-01")));
        List<GameRecord> ranking = new ArrayList<>(original);
        Comparator<GameRecord> order = Comparator.comparingInt(GameRecord::score).reversed()
                .thenComparingInt(GameRecord::playSeconds)
                .thenComparing(GameRecord::playedOn)
                .thenComparing(GameRecord::playerId);
        ranking.sort(order);
        ranking.forEach(System.out::println);
    }
}

2. PowerShell에서 컴파일·실행

실행 환경: Windows PowerShell

실행 위치: C:\dev\game-ranking-algorithms

실행 전 확인: src/RankingSort.java가 저장되었고 out 폴더에는 삭제해도 되는 컴파일 결과만 있는지 확인합니다.

대상: src/RankingSort.java와 out 아래 생성되는 class 파일

Windows PowerShell
Set-Location C:\dev\game-ranking-algorithms
New-Item -ItemType Directory -Force .\out | Out-Null
javac -Xlint:all -d .\out .\src\RankingSort.java
java -cp .\out RankingSort

예상 결과: P1이 먼저, 동점 1200점에서는 플레이 시간이 짧은 P3이 P2보다 먼저 출력됩니다.

실행 시간은 PC의 CPU·메모리, JDK 버전, JVM 워밍업, 백그라운드 작업과 입력 분포에 따라 달라질 수 있습니다. 측정값은 같은 조건에서 여러 번 비교하고 Big-O 분석과 함께 해석합니다.

5. 코드와 알고리즘이 동작하는 이유

정렬 키는 점수 내림차순, 시간 오름차순, ID 오름차순 순서로 적용됩니다. 복사본을 정렬해 원본 입력 순서를 보존합니다. 비교 기반 정렬은 일반적으로 O(n log n) 시간이며 복사본 O(n) 공간도 기록해야 합니다.

6. 자주 하는 실수와 해결법

7. 직접 실습

8. 이해 점검 질문 3개

9. 핵심 요약

MINI QUIZ