6-1. 정렬(Sorting)

정렬이란?

이름, 학번, 키 등 핵심 항목(key)의 대소 관계에 따라 데이터 집합을 일정한 순서로 줄지어 늘어서도록 바꾸는 작업

• 오름차순(ascending order) 정렬: 키 값이 작은 데이터를 앞쪽에 배치
• 내림차순(descending order) 정렬: 오름차순의 반대

 

 

 

 

 

정렬 알고리즘의 안정성

정렬 알고리즘은 안정된(stable) 알고리즘과 그렇지 않은 알고리즘으로 나눌 수 있다.

• 안정된 정렬: 같은 값의 키를 가진 요소의 순서가 정렬 전후에도 유지되는 것
• 안정되지 않은 알고리즘: 안정된 정렬의 반대

 

 

 

 

 

내부 정렬과 외부 정렬

하나의 배열에서 작업할 수 있는 경우에는 내부 정렬(internal sorting)을 사용, 하나의 배열에서 작업할 수 없는 경우에는 외부 정렬(external sorting)을 사용한다.

 

 

1. 내부 정렬: 정렬할 모든 데이터를 하나의 배열에 저장
2. 외부 정렬: 정렬할 데이터가 너무 많아 하나의 배열에 저장할 수 없는 경우에 사용하는 알고리즘

외부 정렬은 내부 정렬을 응용한 것으로, 작업을 위한 파일 등이 필요하고 알고리즘도 복잡하다.

 

 

 

 

 

정렬 알고리즘의 핵심 요소

• 교환
• 선택
• 삽입

대부분의 정렬 알고리즘은 이 세 가지 요소를 응용