정렬(Sorting)은 순서 집합의 원소들을 어떤 기준으로 배열하는 걸 말합니다. 흐트러져 있는 단어카드를 알파벳 순으로 정리하는 걸 연상하면 되겠습니다. 컴퓨터가 취급하는 자료를 정렬된 상태로 저장하면 찾기도 쉽고 관리하기도 쉬워서 이 정렬은 전산학의 전통적인 문제입니다. 역사도 오래되었고 연구도 많이 되었으며, 따라서 그 해법도 매우 다양합니다. 모든 알고리즘이 그렇듯이 모든 상황에서 압도적으로 성능이 좋은 정렬 방법은 없습니다. 그래서 다양한 정렬 알고리즘에 대해서 익혀야 하는 겁니다. 그리고 동일한 문제를 해결하기 위한 다양한 해결 방법을 익히는 것은 문제 해결의 다양하고 창의적인 접근법을 접할 수 있다는 점에서 매우 흥미로운 주제이기도 합니다.
정렬 문제를 푸는 도구는 "비교"와 "교환" 단 두가지입니다. 비교와 교환을 어떤 순서로 하느냐에 따라 그 성능은 확연히 달라집니다. 어떤 점에서는 아름답기까지 합니다.
이번 장에서는 정렬 문제의 의미에 대해서 먼저 살펴보고 이 정렬 문제를 해결하는 단순하고도 전통적인 선택 정렬, 삽입 정렬, 버블 정렬 등에 대해서 살펴볼 것입니다.
강의 자료
동영상 강의
9.0 정렬의 기본 - 시작 : 이제 본격적인 알고리즘 탐험에 나섭니다. 전통적인 알고리즘 문제인 정렬(Sorting)이 가장 먼저입니다.
9.1 정렬의 개념 : 정렬이 무엇을 다루는 문제인지 우선 살펴봅니다. 정렬 알고리즘은 매우 다양한데 그들을 어떻게 분류할 수 있는지도 알아봅니다.
9.2 선택 정렬 : 선택정렬(Selection Sort)은 가장 직관적인 정렬 방법으로 실제 사람들이 머릿속으로 많이 시뮬레이션 하는 방법입니다. 선택 정렬을 알아보고 구현하고 분석해 봅니다.
9.3 삽입 정렬 : 삽입정렬은 단순하면서도 오버헤드가 적어 쓰임새가 많은 정렬법입니다. 삽입정렬을 알아보고 이를 구현하고 분석해 봅니다.
9.4 버블 정렬 : 모든 알고리즘이 최선은 아닙니다. 버블정렬은 효율적인 알고리즘은 아니지만 예전에 많이 다루어지던 것입니다. 버블정렬의 효율성은 어떤지 구현하고 분석해 봅니다.
9.5 정렬의 성능 분석 : 동일한 조건을 두고 각 정렬법에 대한 실제 실행 시간을 측정해 봅니다. 그 결과가 이론적으로 살펴본 계산량에 부합하는지 검증해 봅니다.
9.9 정렬의 기본 - 결론 : 기본적인 정렬 알고리즘들에 대해 알아 보았습니다. 이에 대한 결론입니다.
관련글 |
- C++로 배우는 알고리즘
- 8장 : 재귀호출
- 10장 : 퀵정렬
댓글 없음:
댓글 쓰기