1. 정렬이란?

<aside> 💡 정렬이란? → 물건을 크기순으로 오름차순이나 내림차순으로 나열하는 것

</aside>

• 물건뿐만 아니라 어떤 형태의 것도 서로 비교만 가능하면 정렬할 수 있다.

정렬은 컴퓨터 공학에서 가장 기본적이고 중요한 알고리즘 중의 하나로, 일상생활에서 많이 사용된다.

• ex) 스프레드 시트에서 정렬 기능을 이용해서 데이터를 정렬

• ex) 인터넷 가격 비교 사이트에서 제품을 가격 순으로 나열

• 정렬시켜야 할 대상은 **레코드(record)**라고 불린다.

  • 레코드는 다시 **필드(field)**라고 하는 단위로 나누어진다.
  • 키(key) : 여러 필드 중에서 특별히 레코드와 레코드를 식별해주는 역할을 하는 필드

→ 결국 정렬이란 레코드들을 키값의 순서로 재배열하는 것!

모든 경우에 있어서 최상의 성능을 보여주는 최적 알고리즘은 존재하지 않는다.

→ 따라서, 현재의 프로그램 수행환경에서 가장 효율적인 정렬 알고리즘을 선택해야 한다.

• 정렬 알고리즘을 평가하는 효율성의 기준 : 정렬을 위해 필요한 비교 연산의 횟수, 이동 연산의 횟수
  • 빅오 표기법을 이용해 근사적으로 표현한다.
  • 이동 횟수와 비교 횟수는 서로 비례하지 않는다.