이 레슨과 관련된 학습 키워드
컴퓨터 과학 & 프로그래밍 — 문제 해결의 도구 → 알고리즘 — 문제 해결의 체계적 접근 → 알고리즘 — 문제 해결의 체계적 접근 → 기초 알고리즘
Learn bubble, selection, insertion, merge, quick, and heap sort with stability analysis and comparison-based lower bound.
정렬은 알고리즘의 가장 기본이면서도 가장 중요한 주제예요.
왜 그렇게 중요할까요?
이진 탐색을 하려면 먼저 데이터가 정렬돼 있어야 해요.
투 포인터 기법도 정렬된 배열에서만 동작하고요.
화면 왼쪽의 Phase 1 영역을 보세요.
기초 정렬인 버블, 선택, 삽입 세 가지가 있어요.
이것들은 O(n²)의 시간 복잡도를 가져요.
실무에서도 정렬은 핵심이에요.
데이터베이스 인덱스가 정렬 기반이고, 검색 결과 순서도 정렬이에요.
가운데 Phase 2를 보시면 고급 정렬이 있어요.
머지, 퀵, 힙 정렬은 O(n log n)을 달성해요.
분할정복이나 힙 구조를 활용하는 거예요.
오른쪽 Phase 3은 분석과 실전이에요.
안정성이란 같은 값의 원래 순서가 유지되는지를 뜻해요.
아래쪽 배열 그림을 보세요.
5, 2, 8, 1, 9, 3이 입력이고, 정렬 후 1, 2, 3, 5, 8, 9가 출력돼요.
이렇게 단순해 보이지만, 어떤 방법으로 정렬하느냐가 성능을 크게 바꿔요.
면접에서도 단골 주제이니 반드시 이해해야 해요.
하단의 세 가지 핵심 질문을 보세요.
시간 복잡도, 안정성, In-place 여부가 정렬 선택의 기준이에요.
이 레슨에서 이 세 가지를 중심으로 여섯 가지 정렬을 비교할 거예요.
선생님: 정렬이 왜 알고리즘의 꽃이라고 불리는지 아세요?
학생: 다른 알고리즘의 전제 조건이 되니까요?
선생님: 맞아요! 이진 탐색도 정렬이 선행되어야 하고, 분할정복 같은 핵심 개념도 정렬을 통해 자연스럽게 배우게 돼요.
학생: O(n²)과 O(n log n)의 차이가 실제로 얼마나 크죠?
선생님: 원소 백만 개일 때 O(n²)은 1조 번, O(n log n)은 약 2천만 번이에요. 5만 배 차이나요.
학생: 그러면 항상 빠른 정렬만 쓰면 되지 않나요?
선생님: 좋은 질문이에요. 안정성이나 메모리 제약 때문에 느린 정렬이 더 나은 경우도 있어요. 차차 배울 거예요.