- 정렬 알고리즘(Sorting algorithm)이란?
원소들을 번호순이나 사전 순서와 같이 일정한 순서대로 열거하는 알고리즘
- 정렬 알고리즘의 결과 조건
- 출력은 비 내림차순(각각의 원소가 전 순서 원소에 비해 이전의 원소보다 작지 않은 순서)이다.
- 출력은 입력을 재배열하여 만든 순열이다.
- 왜 사용하는가?
컴퓨터 분야에서 사용하는 데이터의 경우, 숫자의 순서나 어휘의 순서대로 정렬한 다음 사용해야 되는 경우가 많아 얼마나 효율적으로 정렬하느냐가 문제의 핵심이다.
데이터를 정렬해야 하는 이유는 탐색을 위해서!
→ 데이터가 정렬되어 있다면 이진 탐색이라는 강력한 알고리즘을 사용할 수 있다.
- 이진 탐색(Binary Search)
오름차순으로 정렬된 정수의 리스트를 같은 크기의 두 부분 리스트로 나누고 필요한 부분에서만 탐색하도록 제한하여 원하는 원소를 찾는 알고리즘
