들어가기 전에

원소들을 일정한 순서로 열거하는 정렬에 대해 살펴보도록 하겠습니다.

학습 목표

정렬의 종류와 정렬 알고리즘을 비교하는 방법을 설명할 수 있습니다.

핵심 단어

• 정렬
• 시간 복잡도

강의 듣기

정렬 소개

앞으로 정렬을 하는 데 쓰이는 알고리즘을 다뤄볼 것입니다. 그리고 이 알고리즘을 다양한 방법으로 비교할 것입니다.

이 수업에서는 숫자들을 순서대로 정렬하는 경우만 다룰 예정입니다. 문자열, object 등을 대상으로 정렬할 수도 있지만 숫자만 사용할 것입니다.

out-of-place 정렬과 in-place 정렬

out-of-place 정렬은 모든 데이터를 자료 구조의 복사본에 옮긴 후 순서대로 배열하여 정렬하는 방법입니다. 그리고 in-place 정렬은 자료 구조를 그대로 두고 그 안에서 요소들의 위치를 바꾸어 정렬하는 방법입니다.

안정 정렬과 불안정 정렬

안정 정렬은 중복된 숫자가 원래 순서를 유지한 상태로 정렬하는 방법입니다. 반대로, 불안정 정렬은 중복된 숫자의 순서를 보장할 수 없습니다.

시간 복잡도

모든 정렬 알고리즘에 대해 최악의 경우, 평균적인 경우, 최선의 경우의 복잡도를 알아볼 것입니다. 최악의 경우는 정렬 전에 큰 수에서 작은 수로 있는 경우, 최선의 경우는 이미 정렬되어 있는 경우입니다. 평균적인 경우는 완전히 임의의 순서로 되어 있는 리스트를 정렬하는 경우를 의미합니다.

생각해보기

1) 일상생활에서 책과 같이 순서가 있는 물건들을 정리할 때, 어떤 정렬 방법을 사용하시나요?