정렬

정렬이란?

---

정렬 알고리즘의 안정성

정렬 알고리즘은 안정된(stable) 알고리즘과 그렇지 않은 알고리즘으로 나눌 수 있다. 안정된 정렬이란 같은 값을 가진 요소의 순서가 정렬 전후에도 유지되는 것을 말한다. 안정되지 않은 알고리즘은 같은 점수인 경우 반드시 학번 순서대로 정렬되지는 않는다.

// 정렬 전
{ 
  0 = 13,
  1 = 9,
  2 = 6,
  3 = 4,
  4 = 6,
  5 = 12
}

// value를 오름차순으로 정렬
// 2,4 의 순서가 유지된다
{
  3 = 4,
  2 = 6,
  4 = 6,
  1 = 9,
  5 = 12,
  0 = 13
}

 

내부 정렬과 외부 정렬

정렬할 모든 데이터를 하나의 배열에 저장할 수 있는 경우에 내부 정렬을 사용하고  정렬할 데이터가 너무 많아서 하나의 배열에 저장할 수 없는 경우에 외부 정렬을 사용한다. 외부 정렬을 구현하려면 작업을 위한 파일 등이 필요하고 알고리즘도 복잡하다.

 

정렬 알고리즘의 핵심 요소

핵심 요소는 교환, 선택, 삽입이며 대부분의 정렬 알고리즘은 이 세 가지 요소를 응용한 것이다.