[자료구조] 정렬 1. 정렬이란?

우리가 효율적으로 데이터를 저장하고 관리하기 위해서 필요한 것 중 하나가 정렬이다.

정렬은 순서를 기준으로 오름차순 정렬과 내림차순 정렬으로 나눌 수 있는데, 오름차순 정렬은 작은 순서대로 정렬하는 것이고 내림차순 정렬은 큰 순서대로 정렬하는 것이다.

 

정렬시켜야 될 대상을 보통 레코드(record)라고 부르며, 레코드는 여러 개의 필드(field)로 이루어진다. 여기서 정렬이 기준이 되는 필드를 키(key) 또는 정렬 키(sort key)라고 한다.

예를 들어 수많은 경주마(레코드)들을 정렬하고 싶은데… 경주마들은 각각 이름, 키, 나이, 품종 등(필드) 가지각색의 속성들을 가지고 있다 이 중 나는 이름을 기준으로 정렬하고 싶다면, 이름이 정렬 키가 되는 것이다.

---

정렬 장소에 따른 분류

• 내부 정렬: 모든 데이터가 메인 메모리에 올라온 채로 이루어지는 정렬.
  주로 데이터의 수가 많지 않은 경우에 사용된다.
• 외부 정렬: 외부 기억 장치에 대부분의 데이터가 있고, 그 중 일부만을 메모리에 올려 정렬하는 방법.
  대용량 데이터를 정렬하는 데 주로 사용된다.

---

우리는 이번에 내부 정렬을, 그 중에서도 단순한(그러나 비효율적인) 정렬 방법을 먼저 공부할 것이다.
좀 더 고급적인 정렬은 자료구조 탭이 아닌 알고리즘 탭에서… 추후에 서술하도록 하겠다. (23년 1학기 알고리즘 과목을 배우면서….)

정렬을 할 때 알아야 되는 개념으로 안정성(stability)이 있다.
안정성이란 동일한 킷값을 갖는 레코드가 여러 개 존재할 경우, 정렬 후에도 이들의 상대적인 위치가 바뀌지 않는 것을 말한다.

 

 

작성일자: 2023-03-08