정렬 알고리즘

정렬 알고리즘이란 ?

정렬 : 이름, 학번 , 키 등 핵심 항목의 대소관계에 따라 데이터 집합을 일정한 순서로 나열하는 작업을 말한다.
오름차순(ascending order) 정렬 : 정렬하고자 하는 기준에 따라 가장 작은 값부터 시작하여 정렬하는 방식
내림차순(descending order) 정렬 : 오름차순과 반대로 가장 큰 값부터 시작하여 작은 값으로 정렬하는 방식

---

정렬 알고리즘의 안정성

정렬 알고리즘의 경우 안정된 알고리즘과 안정되지 않은 알고리즘으로 나눌 수 있다.

안정된 알고리즘 : 정렬 기준에 따라 정렬 시 동일한 값을 갖는 요소에 대해서 정렬 전후 순서가 유지되는 알고리즘
안정되지 않은 알고리즘 : 동일한 값에 대해서 정렬 전후 반드시 순서가 보장되지 않는 알고리즘

Do it 자료구조와 함께 배우는 알고리즘 입문 참조

---

내부 정렬과 외부 정렬

내부 정렬 : 정렬할 모든 데이터를 하나의 배열에서 저장할 수 있을 때에 사용하는 알고리즘
외부 정렬 : 정렬할 데이터가 너무 많아서 하나의 배열에 저장할 수 없을 때에 사용하는 알고리즘

---

** 정렬 알고리즘의 핵심 요소는 교환, 선택, 삽입이다.

** 대부분 정렬 알고리즘은 이 3가지 핵심 요소를 응용한 것이다.